最終更新: 2021-03-24T16:47+0900
解いたあとで他の人の Ruby での解答を見たらバリエーションがいくつか見られた。
これが一番多かったと思う。公式解説に書かれている通りの手順。
これは Ruby で最速の qib さんの提出 #20369253 (191 ms) の解法。
公式解説にはこう書かれている。
マス i と j の距離を d(i,j) として，マス i の色は d(1,i) ≦ d(N,i) ならば黒，そうでなければ白となる．結論としてマス 1 とマス N の 2 点から幅優先探索や深さ優先探索などを行うことで O(N) でこの問題を解くことが可能である．
解法１はたしかに解説通りの手順ではあるが、解答にあたり具体的な距離まで知りたいわけではなく、距離の大小関係だけ知れれば十分なのだ。
解法２の手順は(スタート地点からの距離を測定する)幅優先探索に則っているのだが、一見すると１手につき１マスしか塗れないゲームのルールに反しているように見えるのが難しい。同じことは解法１にも言えて、「マス i の色は d(1,i) ≦ d(N,i) ならば黒，そうでなければ白となる
」が納得できるかどうかに尽きるのだけど、解法２の手順がなまじゲームに似ているせいで考えてしまう。
フェネックとすぬけくんの行動原理として想定したのは公式解説のものと同じ。見立てだけが異なる。どういう見立てだったか。
フェネック(すぬけくんでもいいが便宜上フェネックを選ぶ)のスタート地点を木の根と定めて、すぬけくんのスタート地点の深さを知る。すぬけくんは移動可能範囲を広げるために根に向かって移動する。フェネックはすぬけくんの移動可能範囲を狭めるためにすぬけくんに向かって移動する。出会うのは中間の深さ。すぬけくんは根に向かって移動できなくなった地点を根としてその子孫ノードだけを塗ることができる(だから一直線に根(フェネックのスタート地点)を目指していた)。
結局のところこの問題は一本の辺を見つけ出す問題だった。頂点集合をフェネック側、すぬけくん側に分ける辺がどれかを見つける問題だった。
その手順として幅優先探索(解法１)とその応用(解法２)と深さ優先探索(解法３)とダイクストラ法(未紹介)と、いろいろな方法があって、実行速度の差があった。同じ線形時間でも１回なめるだけで済ませられるのか、２回か、３回か。
今日@2021-03-23 たまたま取り組んだこの問題が同じ方針で解けそうだった。
２地点から深さ優先探索で陣取りをしていって、中央付近でにらみ合って、それからどれだけ相手陣へ侵攻(自陣へ後退)できるかを数えれば答えになりそうだった。
きっちりと隙を見せない after_contest に撃ち落とされましたとさ。
競技プログラミングをするフレンズ @kyopro_friends
サーバル「ABC148F『Playing tag on tree』にafter_contestを追加したよ！ 不等式に等号を入れるか入れないかを間違ってるコードが落ちるようになったはずだから確認してみてね」https://t.co/jcHP4lHFhg
不等号などなかった。先攻後攻を入れ替えたのと、自陣へ逃げ込もうとしてうっかり中立地帯へ迷い込まないように道を塞いだ。
当初方針のまま after_contest に対応したが、どうにも不自然に頑張ったようなコードになってしまった。この問題に関しては、想定解法通りに２通りの距離表を見比べて答えを選び出すのが良かっただろう。
ところで ABC148 はオンタイムで参加していた。A-D まで灰 diff で、E 問題に至ってもギリギリ緑という低難度回。F 問題でやっと水 diff 中位だったらしい。当時１時間を残していながら解けなかったのがこの F 問題。何を考えて解けなかったか。
木の上で追いかけっこをする２人がすれ違うことができない、ということが認識できていなかった。だから偶奇が適切な部分木を選んで逃げ込むことで追跡が躱せるような気がしていた。それじゃあこの但し書きが嘘になるのにね。「なお、ゲームは必ず終了することが証明できます。
」 そんなん考えたら青 diff 上位の「DFS Game」より難しくなるってのにね。