最近競プロにはまっているますぐれです。解いた問題の思考のログを残しておきたいと思ってこういう記事を書くことにしました。

この記事は自分が考察した流れや、気づいたことなどを記録するためのものです。最短経路で答えにたどり着くわけではないです。(たどり着く場合もあるかもしれません)

今日の問題

D - 連結 / Connectivityです。

問題概要

$N$個の都市が与えられます。都市間の間には$K$本の道路と$L$本の鉄道が存在しています。ここで、ある都市から都市へ道路のみを使って移動できるとき、それらの都市は道路で連結していると定義します。鉄道についても同様です。

各都市について、道路でも都市でも連結な都市の数はいくつあるかを出力してください。

制約

• $2 \le N \le 2 \times 10^5$
• $1 \le L, K \le 10^5$

考察

最初に考えたこと

• 道路か鉄道のいずれかしかない場合はUnionFind木で一瞬で終わる
• しかし、UF木一本では両方につながっているという情報を管理することができない

ならUnionFind木を2本用意してやればうまくいくのでは？

嘘解法までの流れ

• 道路で繋がっていない都市同士は絶対に題を満たさない
• なら、まずはUF木で道路で連結かどうかを調べ、その後その内部で鉄道で連結になっているかを調べれば良さそう
• 計算量的には十分間に合いそう

というわけで最初はこれを実装して提出しました。WAをもらってからしばらく考えるとこれが嘘であることが分かりました。 どこが嘘なのかというと、道路の連結成分をまたいで鉄道でつながる場合というのが考慮できていないため、そのような例で連結している部分を数えきれていない点です。

具体的に言うと、都市$A,B,C$のうち$A$と$C$の間に道路があって、$A$と$B$、$B$と$C$はそれぞれ鉄道でつながっているという場合がダメです。上の解法ではこれを検知することはできません。

解法までの流れ

• ある都市群が連結であることと、UF木の都市群のrootの値が同じであることは同値である
• このことから思考を進めると、道路についてのUF木のrootの値と鉄道についてのUF木のrootの値が同じであればよい、ということに気が付く
• rootの値をペアにして、それが同じ奴を数え上げれば良さそう

これは解説と同じ解法になっています。これで提出してAC。

反省点

• 反例に気づくまでに時間をかけすぎている
• UF木を2本使うということには気づけていたのに、そのrootの値をペアにして管理するという発想があまり出てこなかった

ペアにする、というの難しいですよね。こういう応用的な思考は問題に触れていくとストックが増えていきそうなので、これからもいろんな問題を解いていきたいなあと思います。