AtCoder AGC 020 A - Move and Win (灰色, 300 点)

シンプルだけど、すごい好き

• 問題へのリンク
• editorial

問題概要

マス と区切られた マス上でゲームする。

Alice は最初マス に、Bob は最初マス にいる。交互に左右どちらかに動かす。ただし「マスの外」や「相手のいるマス」には動かせない。

先に動かせなくなった方が負けである。双方最善を尽くしたとき、どちらが勝つか (引き分けの場合はその旨を報告)？

制約

• 
• 

考えたこと

相手を端に追い詰めることができれば勝てることがわかる。そしてこの手の問題はパリティ (偶奇性) を考えるのが相場と決まってる。

のパリティに注目すると、双方がどのようにプレイしたとしても、毎ターンごとにパリティが入れ替わることがわかる。よって

初期状態で が偶数のとき

必ず Alice が手番を終えるタイミングで が奇数になる。よって Alice 目線では、Bob がどんな動きをしようとも Bob に迫っていくことで、いつかは という状態にできる。その状態になったら Bob は後ろに下がることしかできないので、端に追い詰めて Alice が勝てる。

初期状態で が奇数のとき

必ず Bob が手番を終えるタイミングで が奇数になる。よって先ほどと同様に、Bob 目線では、Alice がどんな動きをしようとも Bob に迫っていくことで勝てる。

コード

実は は全然関係なかったね。引き分けも起こらない。計算量は 。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    if ((B-A)%2 == 0) cout << "Alice" << endl;
    else cout << "Borys" << endl;
}