yukicoder : No.1613 Rush and Remove

実験ゲーか。
https://yukicoder.me/problems/no/1613

問題

H*Wのグリッドにおいて、いくつかのマスに駒が置かれている。
ここで2人のターン制ゲームを行う。

自分のターンでは、駒を1つ選ぶ。
その位置が(i,j)であるとき、(i',j)...(i-1,j)の間に駒がないようなi'＜iを選び、(i',j)...(i-1,j)に駒を置いたうえで(i,j)の駒を消す。
駒が1つもないときは負けである。

両者最適手を取るとき、勝者はどちらか。

解法

実験してみると、各列を駒のありなしで2進数の値とみなすと、その値のmod 3がGrundy数となる。
なのでその値をもとめてxorを取るとよい。

int H,W;
string S[303];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>H>>W;
	
	int nim[303]={};
	
	FOR(y,H) cin>>S[y];
	for(y=H-1;y>=0;y--) {
		FOR(x,W) {
			nim[x]=nim[x]*2%3;
			if(S[y][x]=='o') nim[x]++;
		}
	}
	
	int xo=0;
	FOR(x,W) xo^=(nim[x]%3);
	if(xo==0) {
		cout<<"Second"<<endl;
	}
	else {
		cout<<"First"<<endl;
	}
}

まとめ

本番実験せずに通した人いるのかな。