TopCoder SRM 676 Div1 Medium BoardEscape、Div2 Medium BoardEscapeDiv2

あまり自信なかったけど解けて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=14085
https://community.topcoder.com/stat?c=problem_statement&pm=13299

問題

R*Cの2次元グリッドを用いたゲームを行う。
各グリッドは移動可能マス・移動不可能マス・出口のいずれかで構成される。
また初期状態でいくつかの移動可能マスにはトークンが置かれている。
初期状態で各トークンはパラメータKを持つ。

このゲームは2名で交互に手番が回ってくるゲームである。
それぞれの手番では以下の動作を行う。

• グリッド上のトークンのうち、隣接マスに移動可能なトークンがあれば1つ選択して移動させる。移動可能なトークンが無ければその手番の負け。
• 移動先マスが出口ならそのトークンを取り除く。
• そうでない場合、そのトークンのパラメータをデクリメントする。パラメータが0になったらそのトークンを取り除く。

両者最適手を取った場合、勝者はどちらか。

解法

Grundy[行][列][残パラメータ] := その位置・パラメータにおけるGrundy数
として全マス残パラメータの小さい順にGrundy数を求めればNimに持ち込める。

Div2はKが100以下なのでそれで良い。
Div1はKが大きいので全パラメータについて上記を求めることはできない。
ただ、以下の2点よりR*Cより大きいKかつ偶奇の等しいもの同士はGrundy数は等しいと考えることができる。(厳密な証明はしていない)

• 各マスから最遠の出口までの距離はO(R*C)。なのでそれ以上のKに対しては出口による影響を受けてGrundy数が変化することはない。
• 2マスを交互に移動すればKを2個減らせるので、上記出口までの距離以上のKに対してはKを2減らしてもGrundy数が変化することはない。

よって残パラメータがR*C+2程度までの範囲でGrundy数を求めれば十分。

int gr[55][55][2600];

class BoardEscape {
	public:
	string findWinner(vector <string> s, int k) {
		int H=s.size();
		int W=s[0].size();
		int y,x,i,j;
		
		ZERO(gr);
		for(i=1;i<=2500;i++) {
			FOR(y,H) FOR(x,W) {
				if(s[y][x]=='E') gr[y][x][i]=0;
				else if(s[y][x]=='.' || s[y][x]=='T') {
					int mex[6]={};
					FOR(j,4) {
						int dd[4]={0,-1,0,1};
						int ty=y+dd[j];
						int tx=x+dd[j^1];
						if(tx<0 || tx>=W || ty<0 || ty>=H) continue;
						if(s[ty][tx]=='#') continue;
						mex[gr[ty][tx][i-1]]=1;
					}
					while(mex[gr[y][x][i]]) gr[y][x][i]++;
				}
			}
		}
		
		if(k>2500) k=2400+(k-2500)%2;
		int ret=0;
		FOR(y,H) FOR(x,W) if(s[y][x]=='T') ret ^= gr[y][x][k];
		
		if(ret==0) return "Bob";
		return "Alice";
	}
}

まとめ