CADDi 2018:D - Harlequin(500)

問題

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_b

N つの山があり、それぞれ石が a_i 個ある。以下のルールでプレーヤーAとBが順番にゲームをする。Aが先手である。

  • それぞれの山から 1 個以上石を取り除く。一度に選ぶ山はすべて異なる山である必要がある。

山から最後の石を取り除いたプレーヤーが勝利となる。どちらが勝利するか?

制約

  •  1 \le N \le 10^5
  •  1 \le a_i \le 10^9

考え方

実験をする。実験のポイントとしては「まずは簡単に(手で)結果が求められるケースから考えてみる。それでダメならプログラムを書いて複雑な場合を考えてみる」のが良さそうということがわかった。いきなり N=3, 4, \cdots のケースは考えずに N=2 のケースで考えてみるのが良い。

(0, w), (h, 0), (1, 1), \cdots の場合は先手が勝つかどうかすぐに分かるので、その結果を元にそれぞれの状態を考えていくことができる。

10 \times 10 マスで考えてみよう。以下のような実験のコードを書くことができる。1(W) が先手が勝つ場合、0(L) が先手が負ける場合とする。

       final int WIN = 1, LOSE = 0;
        public void solve(int testNumber, MyInput in, PrintWriter out) {

            int[][] game = new int[10][10];
            fill(game, -1);

            game[0][0] = WIN;
            game[1][1] = WIN;
            for (int i = 1; i < 10; i++) {
                game[0][i] = i % 2 == 1 ? WIN : LOSE;
                game[i][0] = i % 2 == 1 ? WIN : LOSE;
            }

            for (int h = 1; h < 10; h++) {
                for (int w = 1; w < 10; w++) {
                    if (game[h][w] != -1) continue;
                    if (game[h-1][w-1] == 0 || game[h-1][w] == 0 || game[h][w-1] == 0) {
                        game[h][w] = WIN;
                    } else {
                        game[h][w] = LOSE;
                    }
                }
            }

            print(game, out);
        }

結果としては以下のような図になる。

f:id:d_tutuz:20181223094435p:plain
実験の結果の図

そうすると、初期状態としてそれぞれの山の石の数がともに偶数だった場合のみ後手が勝利し、それ以外の場合は先手が勝利することが推測できそうである。

Submission #3852333 - CADDi 2018

どこに着目して考察するべきだったか

簡単なケース  N=2 に着目して勝敗を考えてみるべきであった。小さいケースで実験してみると見通しがよくなりそう。

何がバグっていたか

難しい実装にはならないだろうなぁ、、、と思いながら偶奇がすべて一致している場合は勝つかなぁ...と適当に考えていたのが良くなかった。

得た知見

以下のような考え方もあるみたいである。

類題

雑記

なんとか本番中に通せてよかった...