手番のプレイヤーがマスに色を塗ることができなかったとき、敗者となります。フェネックとすぬけくんが最適に行動したとき勝者はどちらか判定してください。考えたこととりあえずグラフ書いて全辺重み1として最短経路の情報を使うのかな〜と思いましたが、それではどの点を選んでいけばいいのかわかりません。そこでこのゲームに勝つには相手の行ける点を潰すように動けばいいんだな、と考えました。相手が行ける点ってどこだろうと考えた時に、相手のスタート地点からの距離が近いほど相手が行ける点指数が高いんじゃないかと考えました。証明はしていませんが軽く手を動かしてみても正しく動いたので一回これを実装してみようとなりました。実装としては単純でダイクストラで点1と点nからの距離を求めておき実際にシミュレートしてやれば良いです。オーダーとしてはダイクストラのO(nlogn)がボトルネックなのでそれになります。提出してみるとACでした。解答どうやらO(n)で解ける方法があるらしい。グラフが木であることに注目すると点1から点nへのルートは一通りであり、そのルートを支配していくのがお互い最良の戦術になる、ということです。これは僕の考えた「相手の行けるところを潰す」とも合致していて、要するに相手に近づいていけばいいわけなので確かにそうだと言う感じです。木の特徴をもっとしっかり抑えて注目するべきでした。上」を読みましたAtCoderでABC066を解きましたゲーマーsatake京都府在住大学生です。