問題

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