ARC072-D：Alice&Brown(500)

問題

https://beta.atcoder.jp/contests/arc072/tasks/arc072_b

考え方

実験すると解が見えてくる。負けるマスを 、勝つマスを で表すことにする。ゲームの条件より明らかに である。

• 勝敗判定 マスからマスに移動するときに、少なくとも 1 つの負けるマスに移動できるマスは勝つマスである。一方、負けるマスに移動できないマスは負けるマスである。

マス から移動できるマスは または であるから、すべてのマスに対して移動可能な範囲のマスに移動して勝敗判定を確かめれば良い。

実験用コード

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

            int H = 20, W = 20;
            int[][] mat = new int[H][W];
            for (int i = 0; i < mat.length; i++) {
                Arrays.fill(mat[i], -1);
            }

            mat[0][0] = LOSE;
            mat[0][1] = LOSE;
            mat[1][0] = LOSE;
            mat[1][1] = LOSE;
            mat[2][0] = WIN;
            mat[0][2] = WIN;

            for (int k = 3; k <= H+W; k++) {
                for (int h = 0; h <= k; h++) {
                    int nh = h, nw = k-h;
                    boolean win = false;

                    for (int i = 1; i <= nh/2; i++) {
                        int mh = nh - i*2;
                        int mw = nw + i;
                        if (mh < 0 || mh >= H || mw < 0 || mw >= W) continue;
                        if (mat[mh][mw] == 0) {
                            win = true;
                            break;
                        }
                    }

                    for (int i = 1; i <= nw/2; i++) {
                        int mh = nh + i;
                        int mw = nw - i*2;
                        if (mh < 0 || mh >= H || mw < 0 || mw >= W) continue;
                        if (mat[mh][mw] == 0) {
                            win = true;
                            break;
                        }
                    }

                    if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
                    mat[nh][nw] = win ? WIN : LOSE;
                }
            }
            print(mat, out);
        }

実験用コードの出力結果

0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0

ポイント

• ゲームは後ろから

類題

• B - マス目と駒