#問題概要
- $H \times W$のマス目をもつボードの左上から右下に向けて先後交互に駒を動かして行き、動かせなくなった方が負け、というゲームで勝つのはどちらかを判断する（リンク）.
- 移動できるのは障害物の無いマスで、移動方向は下、右、右下の３パターン.
- $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とかの練習になったのでよし