Union-Find の理解がひと段落したので，今更だが ABC120 を振り返る．
A - Favorite Sound
所要時間 3 分．少し変に考えてしまって時間をロスしてしまった．
// ABC120_A #include <iostream> #include <algorithm> using namespace std; using ll = long long; int main() { // input(sunippets: inpv, inpn) ll A, B, C; cin >> A >> B >> C; // calculation cout << min(C, B/A) << "\n"; // C より大きい回数は必要ない return 0; }
B - K-th Common Divisor
所要時間 8 分ちょい．問題文をよく読みましょうの最たる例．「K 番目に大きい数」は「上から K 番目に大きい数」．「2 番目に大きい数」と言われたら「上から 2 番目に大きい数」．
#include <iostream> using namespace std; using ll = long long; int main() { // input ll A, B, K; cin >> A >> B >> K; // calculation ll mn = min(A, B), n = 0; for (ll i = mn; i >= 1; --i) { if (A%i == 0 && B%i == 0) ++n; if (n == K) { cout << i << "\n"; return 0; } } return 0; }
C - Unification
所要時間 6 分半．問題を見るや否やスタックを使ったシミュレーションで解いた．以下の記事の解法がそのまま使えた．また，愚直にシミュレーションしなくても，全ての操作が終わった後に 0 or 1 のみ残ることを考えれば，（総数が小さい方）× 2 をすれば答えが出る．シミュレーション系は最後の状態を考えるのが大事になることが多い．
スタックによる解法（シミュレーション）
// ABC120_C #include <iostream> #include <string> #include <stack> using namespace std; using ll = long long; int main() { // input(sunippets: inpv, inpn) string S; cin >> S; // calculation stack<char> st; st.push(S[0]); ll res = 0; for (ll i = 1; i < S.size(); ++i) { if (st.empty()) { st.push(S[i]); } else if (st.top() != S[i]) { // 1 と 0 が合わさったら st.pop(); res++; } else { st.push(S[i]); } } cout << res*2 << "\n"; return 0; }
0，1 をカウントする解法
// ABC120_C #include <iostream> #include <string> #include <algorithm> using namespace std; using ll = long long; int main() { // input(sunippets: inpv, inpn) string S; cin >> S; // calculation // 最終的に 0, 1 どちらかだけになる ll zero = 0, one = 0; for (ll i = 0; i < S.size(); ++i) { if (S[i] == '0') ++zero; else ++one; } cout << min(zero, one)*2 << "\n"; return 0; }
D - Decayed Bridges
解けなかった問題．本番中はひたすら「競プロ グラフ 辺 壊す」とかで検索していたが見当はずれで，どうやら Union-Find の典型だったらしい．名前は何度か目にしたことがあったが，中身を全く知らなかったので勉強するいい機会になった．
まず，この問題で得た知見を以下に示す．
- グラフを扱う問題において，辺を壊す処理は難しい．「難しい」というのは，壊した後の連結性の判定などの処理が計算時間的に難しいという意味（DFS，BFS，ワーシャルフロイド法などでは，制約が大きい時に連結性の判定に使えない）．
- 逆に，繋ぐ処理は簡単．繋ぐ処理のみを行なっていって，ある頂点が連結であるかどうかは Union-Find で簡単に求められる．
- クエリを逆に読む（最終状態からクエリを遡る）と問題を解くヒントになりうる．
- 差分を更新する（状態が連続する場合（この問題では「順に橋が壊される（繋がれる）」）は，前後の差分を上手く利用して計算を短縮する）．漸化式のイメージ？
以上 4 つの知見が得られた．特にシミュレーションを最後の状態まで行なった後に一つずつ遡るというのは考察の典型になってくれそうな気がするので覚えておきたい．
解法
まず，最後のクエリが与えられた状態からスタートすることを考える．最終クエリが与えられた状態では全ての辺が壊れており，全ての頂点が孤立している．そして，時間を巻き戻すようなイメージで，クエリを逆読みしながら Union-Find を使って頂点を繋げていく．その過程で不便さが少しずつ解消されていく．
解消される不便さは，併合される木の根が異なるとき，
（頂点 1 の size）×（頂点 2 の size）
で計算できる．これは頂点同士の不便さが木の併合によって一挙に解消されるからである．例えば，
(1, 2), (3, 4)
という二つの木があるとき，この時点で不便な組み合わせは
(1, 3), (1, 4), (2, 3), (2, 4)
の （一方の頂点数）×（他方の頂点数）＝ 2 × 2 である．同じ根に属する頂点同士を繋げるときは，不便さは特に解消されないので更新しない．以上の過程をコードに落とし込む．
// ABC120_D #include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; using ll = long long; #define REP(i, N) for (ll i = 0; i < N; ++i) #define pll pair<ll, ll> #define F first #define S second class UnionFind { public: vector <ll> par; // 各元の親を表す配列 vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化) // Constructor UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) { for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } void init(ll sz_) { siz.assign(sz_, 1LL); // assign: 再代入 par.resize(sz_); // resize: 再確保 for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } // Member Function // Find ll root(ll x) { // 根の検索 while (par[x] != x) { x = par[x] = par[par[x]]; // x の親の親を x の親とする } return x; } // Union(Unite, Merge) bool merge(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; // merge technique（データ構造をマージするテク．小を大にくっつける） if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } bool issame(ll x, ll y) { // 連結判定 return root(x) == root(y); } ll size(ll x) { // 素集合のサイズ return siz[root(x)]; } }; int main() { // input ll N, M; ll node1, node2; cin >> N >> M; vector<pll> A(M); for (ll i = 0; i < M; i++) { cin >> node1 >> node2; --node1, --node2; A[i].F = node1; A[i].S = node2; } // calculation vector<ll> ans(M); ans[M-1] = (N*(N-1))/2; // 全ての頂点が孤立している状態 UnionFind uf(N); for (ll i = M-1; i >= 1; --i) { node1 = A[i].F, node2 = A[i].S; if (uf.issame(node1, node2)) { ans[i-1] = ans[i]; } else { // 根が異なるとき，それぞれのサイズの積（頂点の組み合わせ）を引く． ans[i-1] = ans[i] - (uf.size(node1) * uf.size(node2)); uf.merge(node1, node2); } } REP(i, M) { cout << ans[i] << "\n"; } return 0; }
反省
B 問題に詰まったものの早解き 3 完（20 分以内）が出来たので良かった．C 問題に関して，解けなかった問題として以前記事にした問題の解法がそのまま出たので，自分のアウトプットが少しは役に立ってくれて良かったという気持ち．
今回歯が立たなかったクエリの逆読みや，Union-Find に関してはこれから「典型」にしていけるように練習していきたい．シミュレーションでは最終状態を考えて遡っていくと解くためのヒントになるというのは色々な問題に適用できそうなので特に覚えておきたい（2 回目）．
