AtCoder ARC #219 : D - Grid Game

こっちもサクッと解けて良かった。
https://atcoder.jp/contests/arc219/tasks/arc219_d

問題

N*Nのグリッドがあり、(r,c)のマスにはA(r,c)個の石がある。
ここで２人でターン制のゲームを行う。
各自の手番では以下を行う。

• 一番左上マス以外で、石が１個以上あるマスを選ぶ。そこから石を1個以上K個以下のいくつかを選び、左か上のマスに移動する。
• 自分の手番で石を移動できない場合、負けとなる。

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

解法

左上マスまでの距離が偶数のマスについて、石の数を問わずGrundy数は0となる。
これは最初にどちらかが石を動かしたとき、相手がそれらを同じ数動かすことを考えるとわかる。

奇数のマスについて、Grundy数はA(r,c) % (K+1)となるので、それらのxorを取ろう。

int T,N,K;
ll A[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		int nim=0;
		FOR(y,N) FOR(x,N) {
			cin>>A[y][x];
			A[y][x]%=(K+1);
			if((y+x)%2==0) A[y][x]=0;
			nim^=A[y][x];
		}
		if(nim) cout<<"Alice"<<endl;
		else cout<<"Bob"<<endl;
	}
}

まとめ

今日のAWCはこの部分問題だったね。