KAIBUNsyo [AtCoder Beginner Contest 206（Sponsored by Panasonic） D]

https://atcoder.jp/contests/abc206/tasks/abc206_d

前提知識

• UnionFind

解説

https://atcoder.jp/contests/abc206/submissions/23624301

以下の解説は、この問題はUnionFindを知らないと理解は難しいので、どこかで学習してきてほしい。
UnionFindを知らなくても別の解法があるかも。

なぜUnionFindか

例えば、1 2 1 4という数列に対して、1を4にしたとすると、4 2 4 4となり、もともとの1と4がまとめられた操作のように見える。
（区別がなくなる）
ここからUnionFindを効果的に使う問題か？という所が自分は考察の始まりとなった。

ちょっと例を出して考えてみる

1 2 3 4を考えてみると、1と4, 2と3が同一になる必要がある。
1-4
2-3
14と23の間については同じになる必要はない。

1 1 1 2 3 4を考えてみると、1と2, 1と3, 1と4が同一になる必要がある。
1-2
1-3
1-4
1と2が同じになるということは結果的に、123が同じになり、1234が同じになることになる。
よって、1234が1つになる、連結になるのに必要な最小回数は？ということになる。

UnionFindに落とし込む

例で見てみると、回文の対応する部分を見て、数字で同じになる関係に辺を貼ってみたときに、
連結関係にある所は最終的に1つの数になるし、連結関係間は操作に何も影響し合わないことが分かる。
なので、回文の対応する部分に辺を貼って連結成分を取り出したときに、連結成分ごとに1つの数にするのに必要な最小の操作回数を計算して総和を取れば答えになる。

最後の問題は各連結成分毎で1つの数にするために必要な最小回数はいくつかという部分である。
操作を思い返すと、毎回の操作で数が1つにまとまっている、つまり、数の種類が1つ減っていることに気が付く。
連結成分にk個の数字が含まれるとき、どんな操作をやっても種類が1つ減るのでk-1個になる。
なので、最小の操作回数を計算するのは、実質かかる操作回数を計算しているだけであり、k個から1個になるにはk-1回操作が必要なので、k-1回が答えとなる。

まとめ

解法をまとめると、回文の対応する数字の組を辺として、UnionFindで連結成分を求める。
各連結成分について、含まれる数字の個数-1の総和を取れば答え。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    UnionFind uf(201010);
    rep(i, 0, N / 2) uf(A[i], A[N - 1 - i]);

    int ans = 0;
    rep(i, 0, 201010) if (uf[i] == i) ans += uf.getValues(i) - 1;
    cout << ans << endl;
}