AtCoder ARC #131 : C - Zero XOR

本番完全には証明せず出してしまった…。
https://atcoder.jp/contests/arc131/tasks/arc131_c

問題

distinctな正整数からなる整数列Aを用いた2人制ゲームである。

各人のターンでは、Aのうち1要素を取り除く。
自身のターン後、Aの各要素のxorが0となれば勝ちである。
互いに最適手を取るとき、勝者はどちらか。

解法

• A中に初手で勝てる値があれば、先手必勝。
• そうでなければ、|A|が奇数なら先手、|A|が偶数なら後手必勝。

奇数なら先手必勝であることを示す。
Aの2要素をx,yとし、残りのxorをzとする。
z=0の時、先手がxかyを取ると後手が反対を取って勝利してしまう。
このような(x,y)は複数あるかもしれないが、|A|は奇数なので、絶対にそうならない値が1つはある。
先手がそれを選べば、後手は次の手番で勝利することはできず、|A|が2個減った状態でまた先手の番になる。
最終的に|A|=1になるので先手が勝つ。

int N;
int A[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int xo=0;
	FOR(i,N) {
		cin>>A[i];
		xo^=A[i];
	}
	FOR(i,N) {
		if(A[i]==xo) {
			cout<<"Win"<<endl;
			return;
		}
	}
	
	if(N%2==0) {
		cout<<"Lose"<<endl;
	}
	else {
		cout<<"Win"<<endl;
	}
	
}

まとめ

2人勝負ゲーは確証を持てないことも多くて、提出がなかなか怖いね。