F. Minimum Maximum Distance
解説ツイートなどを見てAC。
コンテスト中は、「木ではなく一直線の場合は三分探索で良さそう。三分探索を木上に拡張できる方法はないか？」と考えて困っていた。
そのせいで問題への考察を怠っていた気がする。
今回は、印がついている頂点のうち考えるべきものが絞れることに気付かなくてはいけなかった。端の頂点しか考えなくて良い。
「端」というのが何かというと、印がついている頂点たち（とその間の頂点）を結ぶ木を作ったとき、その直径になっている頂点だけ調べれば良いということ（というか、直径/2の切り上げが答えである）。
言われてみれば当然に思えるのに、結構時間をかけても気付けなかった。
0 件のコメント:
コメントを投稿