Educational Codeforces Round 22 C. The Tag Game
木の2個の頂点にAさん及びBさんがいる。AさんがBさんを追いかけ、BさんはAさんから逃げるという目的で行動を最適化するとき、AさんがBさんに追いつく手数を求めよ。その場にとどまるのもありとし、Bさんが先手とする。
Aさん及びBさんがいる地点からの距離を全列挙する。この時、木の性質としてある2個の地点間の最短距離はただひとつのルートしかいない、という性質を使うと、ある頂点pに於いて、d(A, p) > d(B, p) であれば、その頂点にBさんは来ることが可能になる。なぜならそこまでの経路上の点qに於いて、d(A, q) <= d(B, q)という点があったとすると、先述の性質によりqはB-p間の最短経路上の点になりえず、Bさんがまっすぐそこに向かえばqは通らないからである。
なので、Bさんとしてはd(A, p) < d(B, p) であるような点のうち、最長の点に行くという行動を取るのが最適になり、Aさんはそこにまっすぐ向かい追いついた時点でゲーム終了となる。O(N)。
コーナーケースとして、初期位置からAとBが重なっている場合は0になる。
