622.1

久し振りに普通のセットに見えたが、簡単だとそういう扱いになるのだろうか？

250

N都市間の接続状況が与えられる。任意の二都市間の移動を最短路ですることを考えるとき、同じ距離の場合はランダムに道が選択されるとして、使用される回数の最大値がK以上の道を答えよ、という問題。

取り敢えず二都市間の最短路を計算しておいて、各道を使うか否かを全探索する。これで4乗ループになる。

幅優先で全探索して、使う道を、という風にやると多分TLEするはず。

500

木が与えられるので、できるだけ少ない本数の枝を切って、全部の部分木において、一番遠い点間の距離が指定された値以下になるようにしたい。そのときの本数を答えよ、という問題。

DPやるだけ。自分よりも遠くに関しては、制約を満たしてさえいれば、一番遠いノード以外は気にならなくなる。なので、それ以外を除去して適当に計算していく。

900

見てない。