yukicoder : No.1716 Bonus Nim

地味に手間取った。
https://yukicoder.me/problems/no/1716

問題

変則的なNimを行う。
通常と違うのは以下の点である。

• 山を空にしたプレイヤーは、1枚コインを入手できる。
• 自分の手番を、コイン1枚使ってスキップできる。

山の初期状態が与えられた場合、勝者は先手後手どちらか。

解法

まず、コインが相手より多い状態で自分の手番を迎えられれば勝ち確定である。
山があれば1つ崩すことで相手よりコインが2枚以上多くなるので、相手がどうやっても自分が1枚以上多い状態をキープできる。
山が空になったら、多い分のコインを使い相手を先に身動き取れなくできる。

そうでない場合、もし同じ石の数の山がそれぞれ偶数個だと、後手が先手の真似をすることで後手必勝。
それ以外は先手必勝。どこかで相手が先手の真似をできなくなるため。

int T,N,A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		x=0;
		set<int> S;
		FOR(i,N) {
			cin>>A[i];
			if(S.count(A[i])) S.erase(A[i]);
			else S.insert(A[i]);
		}
		if(N%2) {
			cout<<"Alice"<<endl;
		}
		else {
			if(S.empty()) {
				cout<<"Bob"<<endl;
			}
			else {
				cout<<"Alice"<<endl;
			}
		}
	}
}

まとめ

色々考えすぎてしまった。