問題概要

  • $H \times W$のマス目をもつボードの左上から右下に向けて先後交互に駒を動かして行き、動かせなくなった方が負け、というゲームで勝つのはどちらかを判断する(リンク).
  • 移動できるのは障害物の無いマスで、移動方向は下、右、右下の3パターン.
  • $1 \le H, W \le 100$

最初に考えたこと

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

考察

Grundy数とは?

  • 詳しい説明は他の文献に譲ります(このページがわかりやすかったです)

  • ざっくり説明すると勝ち確定の状態を(非$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;
}

(リンク)

最後に

  • 解説を見たら、Grundy数のGの字もなくて驚きました.
  • が、どうやら(非$0$)と($0$)のみ見てるっぽい?
  • 言われてみると確かにその情報だけで十分だ.
  • Nim以外の場合具体的な数字はいらないのか?
  • でもまあsetとかの練習になったのでよし
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.