KCS Irregular Contest #001 D

ゲーム

kagamizさんが主催のコンテストに出てみた。
http://kcs.miz-miz.biz/contest/1006/problem_list

問題

日本語なので本文参照。
http://kcs.miz-miz.biz/contest/1006/view_problem/D


要約すると、最後の石を取ったら負けのNim

制約条件

石の個数の和が10^6以下とか

方針

全ての山がサイズ1だったら、偶数なら先手が勝ちで奇数なら後手が勝ち。


サイズ2以上の山が一つあり、残りが全てサイズ1だったら、
先手はサイズ2以上の山から石を全部取るか1個残すかを選べるので、残す山の個数を偶数奇数選べる。
すなわち先手必勝。


サイズ2以上の山があるときは、全てのxorを取って、0に等しければ後手が必ず勝てる。
なぜかというと、サイズ2以上の山があり、xor = 0であるときは、サイズ2以上の山は必ず2つ以上ある。
なので、通常のNimと同じように、先手の手に対してxor = 0に戻す手が取れる。
これをやっていって、先手の手でサイズ2の山が残り1個になったら、上の考察に帰着して後手が勝つ。

ソースコード

int n;
string s;

int main(){
	cin >> n >> s;
	int cnt = 0, one = 0, x = 0;
	vi v;
	rep(i, n){
		if(s[i] == '#'){
			if(cnt) v.pb(cnt);
			cnt = 0;
		}
		else cnt++;
	}
	if(cnt) v.pb(cnt);
	
	if(v.size() == 0 || v[0] == n){
		cout << "Smith" << endl;
		return 0;
	}
	
	rep(i, v.size()){
		if(v[i] == 1) one++;
		x ^= v[i];
	}
	cout << (x == 0 && one != v.size() ||
		one == v.size() && x == 1
		? "Pastel" : "Smith") << endl;
	
	return 0;
}