AtCoder GC020 A: Digit Sum 2

問題

https://beta.atcoder.jp/contests/agc020/tasks/agc020_a

解法

各自がとるべき戦略を考えるにあたり、まずはどのような状態で勝敗が確定するかを考えます。

勝敗が確定するのは、以下のように片方が端っこに追いやられた状態で、次のターンがまわってくる場合です。

この状態でAliceが次のターンだとAliceの負けになります。

さらにこの1ターン前の状態、2ターン前の状態を考えると以下のようになります。

このように1ターン前の状態をたどっていくと、「隣接した状態になると次のターンの人の負けが確定する」ことがわかります。

次に初期状態でのAliceとBorysの間のマスの数について考えます。

AliceとBorysの間のマスの数が1であれば、最初にBorys側に移動すれば隣接状態となるためAliceの確定します。

AliceとBorysの間のマスの数が2の場合、AliceがBorys側に移動すれば次のターンでBorysが隣接してくるとAliceの負けが確定します。よって、Borysと反対側に移動することになり間のマスの数は3になります。そうすると、BorysはAlice側に移動してくるので、再び間のマスの数は2に戻ります。これを繰り返すことになるため、最終的にAliceは端っこに追い詰められて負けてしまいます。よって、Aliceは必ず負けます。

AliceとBorysの間のマスの数が3の場合、最初にAliceがBorys側に移動すると、AliceとBorysの間のマスの数は2になります。これは上記の「AliceとBorysの間のマスの数が2の場合」の逆になるため、今度はBorysが必ず負けます。

上記のように初期状態の両者の間のマスの数を考えていくと、

間のマスの数が奇数の場合、Aliceの勝ち 間のマスの数が偶数の場合、Borysの勝ち

であることがわかります。

実装

n,a,b = gets.chomp.split.map(&:to_i)
puts (b-a)%2==0 ? "Alice" : "Borys"