AGC020 A - Move and Winのメモ
AGCのAは楽しいらしいので解いてみました。
考察
そもそもこのゲーム自体について考察が必要ですが、要するに相手を端っこに追い詰めたら勝ちとなります。もっと言えば、隣接した状態で後手になっていれば勝ちです。隣接したら相手は後退するしかなく、相手が後退したらまた距離を詰めます。これを繰り返せば最終的には相手が動けなくなって勝ちです。
なので、自分の番に相手の隣に移動できたら勝ちです。
簡単なケースから考えてみます。
最初から隣接していた場合はボリスの勝ちです。アリスが先手と決まっているので、アリスは後退するしかありません。
1マス空いていたらアリスの勝ちです。先手のアリスは早速ボリスの隣に移動することで勝ち確定状態となります。
では2マス以上空いていたら？
もしアリスがボリスのほうに寄ったら、ボリスの勝ちになってしまいます。ボリスのターンになったらボリスがアリスに隣接してしまい、次のターンにアリスは後退して負け確定状態に追い込まれます。
ではアリスが初手で後退したらどうなるか？負け確状態から逃れられるのか？
アリスが後退すると、3マス空きます。ボリスが仮にアリスに寄ったとすると、再び2マス空いた状態でアリスのターンになります。同じ状態に戻りました。しかし、アリスが後ろに一歩追い詰められた点が異なります。
このまま後ろに逃げ続けても、全く勝ちの目は生まれないことがわかります。最終的にはそれ以上後退できなくなって前進するしかなくなり、次のターンでボリスに隣接されて負けとなります。
なので前進したら負けという状態でゲームが始まったら、後退しても結局負けということで、初期状態がどうなっているかだけで判定できてしまうことになります。
アリスが後退した後にボリスも後退したらまた別かもしれませんが、2人とも勝つために最適な行動をとる前提なので、前進したら勝つのにわざわざ後退するというケースは考えなくていいことになります。
負けが確定している人の最適な行動ってなんだろう？と思ったのですが、上記の通りでどうあがいても負けなのでどうでもいいということになります。
アリスとボリスの間のマスが何マスになっていても考え方としては同じです。3マスであれば、アリスの勝ちです。アリスが前進して残り2マス。ボリスは前進すると次のターンにアリスに隣接されて負けですが、後退しても3マス空いた状態でアリス先手になり同じことなのでどうあがいても負けです。
要するに、アリスとボリスの間のマスの個数の偶奇で勝敗が決まります。4マスならボリスの勝ち、5マスならアリスの勝ち、というように、偶数ならボリスの勝ちで奇数ならアリスの勝ちです。
なお、そもそも全体が2マスしかなくて2人とも動けない場合はどうなるのか気になったのですが、入力例2がそうなっており、ボリスの勝ちということでした。自分のターンが来たときに動けなかったら負けで、負けなかったほうが（たとえ自分も動けなかったとしても）勝ちということになるんですね。なので先手のアリスが負けと。
この場合は2人の間のマスは0マスで偶数なのでボリスの勝ち、ということで実装には影響ありません。
実装
fun main() {
val (n, a, b) = readLine()!!.split(" ").map { it.toInt() }
if((b - a) % 2 - 1 == 0) {
println("Borys")
} else {
println("Alice")
}
}
いろいろ考えて出した答えですが、実装はシンプルすぎてなぜそれでいいのかコードからは読み取れないですね。なので、このようなメモを書いてみようと思った次第です。
（執筆時間：22分51秒）
Discussion