JOI夏季セミナーに通りました。JOI公式ホームページによると倍率3.9倍だったらしいので嬉しいです。 申し込みは2017年と2019年の2回行い、今回が初めての通過です。
ところで、非春合宿erで通過したのが10人らしいですがまだ自分含め5人しか見つけていないので少し心配になっています......
スペースが余ったので最近解いた問題について書きます。
AGC005-C Tree Restoring
問題概要
数列が与えられるので、各頂点からの最遠点が
であるような木が存在するか判定せよ。
解法
木の直径に注目するときれいに解けます。
頂点P→QとQ→Pの距離は等しいので、の最大値と同じ値を持つ要素は少なくとも2つあるはずです。そうでなければ答えはNoです。
ここで、
の最大値を
と置きます。
さて、このパスを考えると、パス上の頂点について距離は
となるはずです。このようなパスが構築できなければNoです。
ここから、残った頂点をパスに併合します。最遠点が
になるような頂点はパス上の距離
の頂点につなぐと条件を満たします。そのような頂点がなければNoです。
あとはこれをイイ感じに確かめればよいです。
