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

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

AtCoder ABC 059 D - Alice&Brown (ARC 072 D) (1D, 青色, 500 点)

ゲーム:アドホックに負けパターンを特定する ゲーム 石取りゲーム AtCoder AtCoder500点 ABC-D ARC-D NoviSteps1D 青色diff 気付き系 数学的帰納法に基づく考察 実験 入力が定数個 Yes/No判定問題

面白かった！！　実験で思いつけるかもしれないし、気づいたら証明したい系。

問題概要

先手と後手が石取りゲームをする。2 個の山があって、最初それぞれ石が X, Y 個積まれている。交互に次の操作をする。

  • 2 個以上の石が積まれている山を 1 つ選ぶ
  • その山の石の個数以下の範囲で任意の偶数 2i を選び、山から 2i 個の石を除去し、 i 個の石を他方の山に積む

先に操作できなくなった方が負けである。双方最善を尽くしたとき、どちらが勝つか？

制約

  • 0 \le X, Y \le 10^{18}

考えたこと

ゲームを解くアプローチとして、

  • DP する
  • 「負けパターン」を何らかの方法で完全に特定する

がある。だが今回は、ゲームの途中過程としてありうる盤面が O(XY) 通りあって、到底 DP できそうにない。

こういうときは、後者の「負けパターンを特定する」というアプローチが有効だ。たとえば Nim は「各山の個数の XOR 和が 0」が負けパターンである。

負けパターンを特定するために、いくつかの盤面の勝敗を求めてみよう。

  • (0, 0)：負け
  • (0, 1)：負け
  • (0, 2)：勝ち（(0, 1) にできるため）
  • (1, 1)：負け
  • (1, 2)：負け
  • (1, 3)：勝ち（(1, 2) にできるため）
  • (2, 2)：負け
  • (2, 3)：負け
  • (2, 4)：勝ち（(2, 3) にできるため）
  • ...

ここまで手を動かすと、次の予想ができた。なお、簡単のために X \le Y とする。

  • X = Y のとき：負け
  • Y - X = 1 のとき：負け
  • Y - X \ge 2 のとき：負け

あとは、これを証明しよう。

証明の方針

ゲームの「負けパターン」を完全に過不足なく特定できたと思えたとき、そのことを証明するためには、次のようにすればよい。

  • 負けパターンである局面から、どの手を打っても、負けパターンではなくなる
  • 負けパターンでない局面からは、上手い手を打つことで、負けパターンにできる

今回は、負けパターンは「 Y - X \ge 1」で過不足ないと考えているので、それを示そう。

負けパターンである局面から、どの手を打っても、負けパターンではなくなること

こっちは簡単だ。

  • X = Y のとき：どっちの山から石をとっても同じなので、簡単のために X の山から A 個の石をとるとする。このとき、2 山の石の個数は X - 2A, X + A となり、その差は 3A (\ge 3) となる
  • Y - X = 1 のとき： X の山から石をとると明らかに 2 山の石の個数の差が拡大するので、 Y の山から石をとる。 A 個の石をとると、2 山の石の個数は X + A, Y - 2A となり、その差は 3A - 1 (\ge 2) となる

というわけで、示された。

負けパターンでない局面からは、上手い手を打つことで、負けパターンにできること

Y - X \ge 2 であるとき、上手く手を打つことで、2 山の石の個数の差を 0 または 1 にできることを示そう。

たとえば、(8, 23) のように、差が 3 の倍数のときは簡単だ。23 の山から 10 個の石をとって、9 の山に 5 個の石を加えると (13, 13) になる。

この例から、概ね Y - X の \frac{2}{3} 倍の個数の石を Y の山から取ればよいと想像がつく。 Y - X を 3 で割った余りで場合分けする。

  • Y - X = 3m と表せるとき： Y の山から 2m 個の石をとって X の山に m 個の石を加えることで、2 山の石の個数はともに X + m 個となる
  • Y - X = 3m + 1 と表せるとき： Y の山から 2m 個の石をとって X の山に m 個の石を加えることで、2 山の石の個数は X + m, X + m + 1 個となる
  • Y - X = 3m - 1 と表せるとき： Y の山から 2m 個の石をとって X の山に m 個の石を加えることで、2 山の石の個数は X + m, X + m - 1 個となる

いずれの場合も示せた。

まとめ

  • |X - Y| \le 1 のとき：後手必勝
  • そうでないとき：先手必勝

コード

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

int main() {
    long long X, Y;
    cin >> X >> Y;

    if (abs(X - Y) <= 1) cout << "Brown" << endl;
    else cout << "Alice" << endl;
}