けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題概要

マス  1, 2, \dots, N と区切られた  N マス上でゲームする。

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

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

制約

  •  2 \le N \le 100
  •  1 \le A \lt B \le N

考えたこと

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

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

初期状態で  B-A が偶数のとき

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

初期状態で  B-A が奇数のとき

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

コード

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

#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;
}