ARC038B 「マス目と駒」

#問題概要
- $H \times W$のマス目をもつボードの左上から右下に向けて先後交互に駒を動かして行き、動かせなくなった方が負け、というゲームで勝つのはどちらかを判断する（[リンク](https://beta.atcoder.jp/contests/arc038/tasks/arc038_b)）.
- 移動できるのは障害物の無いマスで、移動方向は下、右、右下の３パターン.
- $1 \le H, W \le 100$

#最初に考えたこと
- 各マスについてgrundy数を定めていけば良さそう（というかgrundy数でできそうな問題を選んだので"卵先鶏先"）
- 右下から見ていけばそれぞれ一意に定まりそう(これについては以下の考察で)

#考察
##Grundy数とは?
- 詳しい説明は他の文献に譲ります([このページ](http://d.hatena.ne.jp/nanikaka/20120524/1337797626)がわかりやすかったです)

- ざっくり説明すると勝ち確定の状態を(非$0$)、負け確定の状態を($0$)として表現したもの

- あるマスから遷移可能なマスのGrundy数に**含まれない**非負整数の中で最小のもの

- その定め方から非$0$からは必ず$0$に移る遷移が存在し、逆に$0$からは非$0$にしか移れないので、$0$の状態を相手に押し付け続ければ必勝で、逆もまた然り.

##今回の場合に適用すると？

- 右下から列にそって左に見ていき、左端まで到達したら一列上を同様に右から左に走査していく、というのを繰り返していけば、(移動パターンを考えると)すでに確定したGrundy数を上書きする心配がなく、また移動できるマスのGrundy数がまだ確定していないということも起こらない.

- サンプルケース$1$で実践します.

- 確定していない場所は$-1$で初期化しておきます(`#`は障害物).

| 行\列 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|
| 1  |  -1 |  # |  -1 |
|  2 |  -1 | -1 |  -1 |

- $(2, 3)$から見ていく。$(2, 3)$からはどこにも移動できない（つまり"負け"の状態）ので、$(2, 3)$のGrundy数は最小の非負整数である$0$で確定.

| 行\列 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|
| 1  |  -1 |  # |  -1 |
|  2 |  -1 | -1 |  0 | 

- 次は$(2, 2)$に注目.$(2, 2)$からは$(2, 3)$にのみ移動できる.$(2, 3)$のGrundy数は$0$なので、$(2, 2)$のGrundy数は$0$を除いた最小の非負整数である$1$と定まる.

| 行\列 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|
| 1  |  -1 |  # |  -1 |
|  2 |  -1 | 1 |  0 | 

- 次は$(2, 1)$に注目.$(2, 1)$からは$(2, 2)$にのみ移動できる.$(2, 2)$のGrundy数は$1$なので、$(2, 1)$のGrundy数は$0$と定まる.

| 行\列 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|
| 1  |  -1 |  # |  -1 |
|  2 |  0 | 1 |  0 | 

- $1$行目も同様に埋めて行くと、下図のようになる

| 行\列 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|
| 1  |  2 |  # |  1 |
|  2 |  0 | 1 |  0 | 

- $(1,1)$のGrundy数が$0$で無いので、先手必勝

- サンプルケース$2$だと以下のようになるはずです($(1, 1)$のGrundy数が$0$なので後手必勝.)

| 行\列 | 1 | 2 | 3 | 4 |
|:-:|:-:|:-:|:-:|:-:|
| 1  | 0  | 2  | 1  | 0  |
| 2  | 2  | 1  | 0  | #  |
| 3  | 1  | 0  | 2  | 1  |
| 4  | 0  | #  | 1  | 0  |

#解答
- 計算量は$O(H \times W)$

```answer.cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)

const int MAX = 128;
const int INF = 1<<29;

int maze[MAX][MAX], H, W;

//範囲内かをcheckする関数
bool inRange(int y, int x){
    return (0 <= y and y < H and 0 <= x and x < W);
}

void solve(void){
    //input
    cin >> H >> W;
    rep(H, i) rep(W, j) {
        char c;
        cin >> c;
        //障害物はINFでおく（flag代わり）
        if (c == '#') maze[i][j] = INF;
        else maze[i][j] = -1;
    }
    //fill grundy number
    repr(H, y) repr(W, x) {
        if (maze[y][x] == INF) continue;
        set<int> s;
        //自身も参照してしまうが、-1なので問題ない
        rep(2, dy) rep(2, dx) {
            if (inRange(y+dy, x+dx)) {
                if (maze[y+dy][x+dx] == INF) continue;
                s.emplace(maze[y+dy][x+dx]);
            }
        }
        //遷移先のgrundy数を見て、自身のgrundy数を決定
        rep(3, n) {
            if (s.find(n) == s.end()) {
                maze[y][x] = n;
                break;
            }
        }
    }
    /*Debug
    rep(H, i) {
        rep(W, j) {
            printf("%d ", maze[i][j]);
        }
        putchar('\n');
    }*/
    if (maze[0][0]) cout << "First" << endl;
    else cout << "Second" << endl;
}

int main(void){
  solve();
  return 0;
}

```
([リンク](https://beta.atcoder.jp/contests/arc038/submissions/2271034))

#最後に
- 解説を見たら、Grundy数のGの字もなくて驚きました.
- が、どうやら(非$0$)と($0$)のみ見てるっぽい？
- 言われてみると確かにその情報だけで十分だ.
- Nim以外の場合具体的な数字はいらないのか?
- でもまあ`set`とかの練習になったのでよし