AtCoder Beginner Contest 206（Sponsored by Panasonic） [ D - KAIBUNsyo ]をPythonでUnionFindを使って解く
ABC206でできなかった問題をやってみる。
解説
はまやんさん解説、snukeさん放送を参考に、Union Findで解くパターンでやってみる。
入力例１の数列にUnion Findをかけて木構造を作ると次のような木構造ができる。
要素は2, 3, 5の3つ。
要素数-1が変更する回数になるので、2回。
木構造が二つできるようなパターンもありえる。
木構造が違う要素は、回文のペアにない。
ココがこの問題のUnion Findを用いるポイント。
要素数3の木と、要素数2の木があるので変更する回数は
3 - 1 + 2 - 1 = 3回
となる。
実装
Union Findの実装はコピペで、ココから。
