NIKKEI Programing Contest-E:Weights on Vertices and Edges
良問だと思ったので記事にすることにした。Cさえなければ....。
解法
こういう重み付きの辺を追加/削除して連結成分が...という問題は，辺が一本もない状態から，一定の順番で辺を追加していくことを考えることで道が開けることがある。
頂点の辺が0本のグラフから，辺の重みが小さい順に辺を追加していくことを考えてみる。このときに，連結成分の重みをもちながら連結していく必要があるが，これはUnion-Findにちょっと書き足せばできる(コード参照)。さて，ある辺
を追加したときにできた連結成分
が，問題の条件を満たしたとしよう。すると，辺の重みが小さい順に追加していったという仮定から，この連結成分
に属するすべての辺は，問題の条件を満たす。つまり，
に含まれる辺は残してもよいことになる。このようにして，辺を追加していきながら，条件を満たす連結成分の集合
がわかる。これらの和集合に属する辺たちを残しておけば，条件を満たすグラフが作れる。では，残すべき辺たちはどのようにして調べることができるだろうか。Union-Findしながら，重複をはじきつつ辺の数を数えるのは難しく見える。
ここで，の見方を変えてみる。辺
の重みを
と書くと，
は，「
から重みが
の辺のみを使っていくことができる頂点の集合」であることがわかる。つまり，
を求めるためには，
が結ぶ頂点から適当にdfsやらbfsやらをするだけでよいことがわかる。本当に求めたいのは
の和集合で，何も考えずにやると
かかってしまうが，
のうち，
の大きい順に調べていけば，
かつ
のとき，
になるので，
で終わる。
以上のことより，次のようなアルゴリズムを考える。
- まず，重みの小さい辺から順にグラフに追加していく。もし，この辺
を追加したことによってできた連結成分が条件を満たすなら，
- 上の作業が終わったら，リストに追加した辺のうち，重みの大きいものから
を求め，残すべき辺の数を数える。
が答え。
最後に，このアルゴリズムが正しい解を返すことを確認しよう。まず，グラフの重みが最大の辺が条件を満たさないなら，その辺は削除されなければならない(1の正当化)。満たす場合，その辺と同じ連結成分に属する他の辺も条件を満たすので，その連結成分については辺を削除する必要がない(2の正当化)。この議論に沿った手続きを再帰的に行っているのが上のアルゴリズムであり，正当性がわかる。(解説の通り帰納法で書いた方がすっきりするかも？)
提出
Submission #4117234 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019
- Union-Findのsという配列が，連結成分の重みをもっている。
- 2に使う辺の管理だが，小さい順にリストに追加して，大きい順に取り出すので，stackを用いるのが楽だと思った。
Cでハマってしまい本番はこの問題を詰め切れず，本選出場も逃したが，観戦権は得ることができた。よろしくお願いします。(誰に対して言ってるんだろう...。)
