ABC206 D 解答
D - KAIBUNsyo（879）
問題
問題文
N 項からなる正整数列 A = (A1, A2, … AN )が与えられます。
以下の操作を 0 回以上何度でも行える時、操作を最小何回行えば、Aを回文にすることができますか？
ある正整数の組 (x, y) を選ぶ。その後、現在 A に含まれる x をすべて y に置き換える。
なお、この問題では、全ての整数 i ( 1≤ i ≤ N ) について、Ai = AN+1−i が成り立つとき、またその時に限って、A が回文であると言います。
制約
入力は全て整数
1 ≤ N ≤ 2 × 10^5
1 ≤ Ai ≤ 2 × 10^5
考察
はじめに本問題では次のことを説明します。
・なぜUnionFindを使うと解けるのか
一方で
・UnionFindとはなんなのか
に関しては詳しく説明しません。ざっくりと流してしまいます。ただ、ライブラリって中で何してるかわかんないけど、それによって得られる結果を適切に使えることが重要だと思います。ですので、UnionFindわかんないけどこの問題が解きたいんだ、という方はぜひ最後までお付き合いいただけると幸いです。
このアルゴリズムを応用したい！となったら中身を覗いてみる、という順番で問題ないかなと思います。
では、なぜUnionFindで解けるのかを説明していきます。
まずは、最小の操作回数という条件は完全に無視してしまいましょう。どんだけ時間がかかってもいいから回文を作る！という意思だけで行動しましょう。次の例を考えます。
例）1 5 3 2 5 2 3 1
これ入力例１です。どうやら２回でできるみたいですが、もっと回数がかかってもいいので簡単にやります。恐らく最も簡単に作れる回文の一つは次なんじゃないでしょうか。
1 1 1 1 1 1 1 1
全部同じ数字にしました。これも立派な回文です。このように全部同じ数字にしてしまえば回文の完成です。これを作るためには３回の操作が必要です。1以外に数字は2,3,5と３種類あるためです。ただこれって全部1にする必要はないですよね。例えばこれも回文です。
1 2 2 2 2 2 2 1
こうすれば2回の操作で回文が作れます。このように少ない回数で回文を作るためには、最終的に何種類の数字にすればよいかを考えることがとっても重要になってきます。
では次の例に移ります。
例）1 2 3 4 1 2 3 4
先ほどと同じように、全部1にしてみましょう。とすると、2→１、3→１、4→１の計3回の計算が必要になります。これも、先と同様に3種類あるためですね。ただ、いい感じに１と２にしてみることを考えましょう。3→２、4→１とすれば２回の操作で回文が作れます。
1 2 2 1 1 2 2 1
では、ここで同じ数字になってしまった（同じ数字になるべき）ってどうして同じになるんですかね。実はこれを考えていくとUnionFindで解ける理由がわかります。
少し変更しまして 例）1 2 5 3 1 2 5 4 で考えます。
同じ数字の関係は次の２つに分けられます。
１）回文となる場所にある数字
２）元の文にて同じ数字
まず１）です。上の例で言いますと、両端の１と４がその一例です。（1 2 5 3 1 2 5 4）回文を作るんですから、この数字を一致させるのが最終目標となります。当然同じ数字になりますね。ということで、1-４は同じ数字になる（しなければならない）ことがわかりました。同様に 1 2 5 3 1 2 5 4 なんかも同じ数字になります（2-5も同じ数字にしましょう）。
次に２）です。問題文の条件を見ますと、
ある正整数の組 (x, y) を選ぶ。その後、現在 A に含まれる x をすべて y に置き換える。
だそうです。ですので、もとの文にて同じ数字は残念ながら最終結果でも同じ数字になります。別の数字に変更する術がないのです。上の例ですと、１なんかが該当します（1 2 5 3 1 2 5 4）
この、１）と２）の条件をつなげていくと、同じ数字になるべき（なってしまう）グループ分けができるんです。ちょっと見てみましょう。まず、１）で1-4は同じとなることが決まりました。同様に1-3も同じ数字になります。ここで、２）にある通り、２つの１を別の数字にすることはできませんので、3-4も同じ数字にせざるを得ないのです。
また、それとは別に2-5は同じ数字になりますね。ただし、1-3-4とは別の数字でも大丈夫です。
これをグラフにすると次のようになります。
グラフの連携しているものが２つ出来上がります。この２つが最終的な回文に現れる数字の種類数となります。
1-3-4を同じ数字（仮に１とします）、2-5を同じ数字（2とする）にするときに、必要な操作回数は先にも述べました通り、2+1＝３となり、これが、最小の操作回数になります。
このように、どの数字が連結しているかを特定してあげることで本問題を解くことが可能となります。グラフの連結判定といえば「Union-Find」ですね。「Union-Find」では上図の3と４のように、友達の友達みたいな関係を簡単に管理することができます。
Union-Findにて同じ数字になるべき頂点をどんどんくっつけていきましょう。最後に連結成分ごとに（その要素数ー１）を足し合わせていけば無事答えが求まります。
説明はおしまいです。後はソースを見ていきましょう。
実装
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;
template<typename T>
struct UnionFind {
vector<int> d;
//コンストラクタ
UnionFind(int n = 0) : d(n, -1) {}
//根の探索と張り替え
int find(int x) {
if (d[x] < 0) return x;
//根のはりかえ
return d[x] = find(d[x]);
}
//根の結合
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
//大きい方に小さい方をくっつける
if (d[x] > d[y]) swap(x, y);
//サイズの更新
d[x] += d[y];
//結合
d[y] = x;
return true;
}
//サイズの取得
int size(int x) { return -d[find(x)]; }
//同じ集合に属しているか
bool same(int x, int y) { return (find(x) == find(y)); }
};
const int M = 2e5;
int main()
{
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
rep(i, n)--a[i];
//出現する数字の最大値でUnionFindを作る。
UnionFind<int> uf(M);
int ans = 0;
rep(i, n)
{
int a1 = a[i];
int a2 = a[n - i - 1];
//同じ数字となるべきものをくっつける
uf.unite(a1, a2);
}
//同じ集合に属するものを管理する
map<int, int> mp;
rep(i, n)
{
//findとすると、集合の根っこ（一番上にある頂点）が求まる
int root = uf.find(a[i]);
//同じ根っこは1回だけしか計算しない
if (mp[root] != 0) continue;
ans += uf.size(root) - 1;
++mp[root];
}
cout << ans << endl;
return 0;
}あとがき
回文の問題をUnionFindにて解いてあげる問題でした。これ一見なんも関係なさそうに見えるのに実はこのアルゴリズムで解けますという、なかなかに素敵な問題でした。私はコンテスト中にはこれに気づくことができずに解くことができませんでした、が解説を見て感動しました。非常に面白い問題だと思います。
問題の条件を言い換えて、典型アルゴリズムにつなげる非常に良い問題だと思いますので、ぜひ一度考えてみることをお勧めします。といいましても、本記事を読んだ後ですと、UnionFindを使うことは知ってしまっているので、どうなんでしょう、とは思いますが。
それでも一度手を動かしてライブラリを使ってみましょう。冒頭でも述べましたが、内部が理解できていなくても大丈夫です。それがライブラリのあるべき姿だと思います。そのうち、内部はどうなっているのかな、と興味がわいてきたタイミングで中を覗いてみると、さらに発見があると思います。それまでは心置きなくコピペしましょう。
この記事が気に入ったらサポートをしてみませんか？