D問題リアルタイム

N個の都市があり、都市間をつなぐ道がM個ある。

それぞれの道には製造年が記録されている。

Q人の国民の所在都市と安全意識（ある年より前に作られた道は通らない）からこの国民が移動できる都市の数を数える問題。

シンプルに考えると、国民ごとにスタート都市から順に移動できる都市を数えていく方法は解ったがO(QM)でTLEだなということで、実装一旦保留して何かうまく解く方法はないか考えたけど何も思いつかず。。

残り時間が30分ぐらいになったので、部分点を取りにO(QM)の方法で実装。

struct, operator<, sortの実装がつっかえることなく実装できるようになってきた。

無事部分点get.

解説動画を見て

道のデータと国民のデータを年順でソートし、道をつなぐ、移動数を取得、を順に処理していくことで、その時点で繋がっている都市を数えるだけというシンプルなやり方が可能になる。

都市をつなぐ処理と、繋がっている都市を数える処理をはやく行える方法があればok.

これを実現するのがUnion Findというデータ構造

といことで、Union FindでO((M + Q)logN)で解くことが可能。

感想。

違うデータ構造のものをソートするという発想ができなかった。

これは事前知識がなくても気付ける部分だと思うので気づきたかった。

グラフの完成系をぼんやりイメージして、そこから何かないかな？と考えていたので気付けなかったと思う。

グラフの状態が経過年ごとに変化していくイメージができれば手がかりが掴めたかも？

UnionFindに関しては知ってないと厳しそう。

抽象化して考えてみると、ノード間の結びつきを全てデータで表現するのではなく、最終的に必要なデータが明確に分かっていれば（今回の場合はある都市が間接的に繋がっている都市の数。具体的に直接どの都市どうしが繋がっているのは知らなくていい）それに応じたデータ構造を考えることができる。

クエリーを明確にした上で、より効率化する方法を考える。（今回の場合は、グループを結びつける際に、大きい方のグループに向かって参照を向けることで、ノード間の参照の深さをミニマムにすることができる。)

実装してみた。

実装に関してはハマる箇所がだいぶ減ってきた。