Codeforces #659 Div1 B. GameGame

問題名、いいネタがなかったのかな…。
http://codeforces.com/contest/1383/problem/B

問題

N要素の数列Aが与えられる。
これらを用いて2人でゲームを行う。

両者自分のターンでは、数列の要素を1つ抜き出し、その分自身のスコアにxorする。
先手後手最適手を取ったとき、勝者はどちらか。

解法

全要素のxorの値をXとすると、XのMSBを奇数個取った方が勝ちになる。
とすると状態として、
(先手の取得済みのMSBの偶奇, 後手の取得済みのMSBの偶奇, 数列中上記MSBの立った残要素数, 数列中上記MSBの立たない残要素数)
を考えると、メモ化再帰でO(N^2)で解ける。
ただ、実際は、残要素数はO(N)通り列挙する必要はなく、こちらも偶奇だけ覚えておけばよい。

int T;
int N;
int A[101010];

int memo[2][2][4][2];

int hoge(int x,int y,int k,int r) {
	if(memo[x][y][k][r]>=0) return memo[x][y][k][r];
	int ret=0;
	if(k && hoge(y,x^1,k-1,r)==0) ret=1;
	if(r && hoge(y,x,k,r-1)==0) ret=1;
	
	//cout<<x<<y<<k<<r<<" "<<ret<<endl;
	return memo[x][y][k][r]=ret;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(memo);
	memo[1][0][0][0]=1;
	memo[0][1][0][0]=0;
	FOR(x,2) FOR(y,2) FOR(k,4) FOR(r,2) if((x+y+k)%2) hoge(x,y,k,r);
	
	
	cin>>T;
	while(T--) {
		cin>>N;
		int x=0;
		FOR(i,N) {
			cin>>A[i];
			x^=A[i];
		}
		
		if(x==0) {
			cout<<"DRAW"<<endl;
		}
		else {
			y=1;
			while(y*2<=x) y*=2;
			
			int num=0;
			FOR(i,N) if(A[i]&y) num++;
			
			if(hoge(0,0,num%4,(N-num)%2)) {
				cout<<"WIN"<<endl;
			}
			else {
				cout<<"LOSE"<<endl;
			}
			
		} 
		
	}
}

まとめ

Aよりこちらの方がすんなりだった。