Codeforces #573 Div1 B. Tokitsukaze, CSL and Stone Game

微妙にコーナーケースがあってややこしい問題。
http://codeforces.com/contest/1190/problem/B

問題

Nimの変形問題。
各自の手番では山の石を1個だけ取ることができる。

手番が来た際に1個も石がないか、取った後同じ石の数の山の対が1組でもあると負けである。
最適手を取ったときの勝者はどちらか。

解法

初期状態で同じ石の山の対があるとややこしい。
細かく場合分けしていこう。

• 石が0個の場合、先手の負け
• 3つ以上同じ石の数の山があると、先手の負け。
• ちょうど2つ同じ石の数の山がある場合、先手はそれを取り除く一択である。
  • 石を1つ取った結果、同じ石の山の組ができたら先手の負け。できない場合、先手後手交換してこの処理を繰り返す
• すべての石の山の数が異なる場合、山の石の数を昇順に並べると、隣接する山の石の差が1になるまで互いに取ることができるので、sum(A[i]-i)の偶奇で決まる。

int N;
ll A[101010];

int win() {
	int i,j,k,l,r,x,y; string s;
	int same=0;
	
	if(A[N-1]==0) return 0;
	FOR(i,N-1) if(A[i]==A[i+1]) {
		same++, j=i;
		if(A[i]==0) return 0;
	}
	
	if(same>1) return 0;
	if(same==1) {
		A[j]--;
		FOR(i,N-1) if(A[i]==A[i+1]) return 0;
		return !win();
	}
	
	ll tot=0;
	FOR(i,N) tot+=A[i]-i;
	return tot%2;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	
	
	if(win()) cout<<"sjfnb"<<endl;
	else cout<<"cslnb"<<endl;
}

まとめ

こういうの本番通るか心配になるよね。