Looksery Cup 2015 : C. The Game Of Parity

凡ミスもったいないなぁ。
http://codeforces.com/contest/549/problem/C

問題

2人で交互に行うゲームがある。

N要素からなる整数列A[i]がある。
2人は自分のターンに、数列から要素を1個取り除く。
数列の要素がK個になったらゲーム終了。

残された要素の和が偶数なら後手、奇数なら先手勝利である。
両者最適手を取る場合、勝者はどちらか。

解法

A[i]の具体的な値は関係なく、偶奇しかこの問題は関係しない。
よって最初にA[i]中の偶奇の数を数え上げよう。

N==Kの時はコーナーケースで、初期状態の偶奇で決まる。
それ以外の場合、最後の1手の際に偶奇両方の要素が1個以上ある場合、最後の1手を行う側は要素の和の偶奇をどちらにもできるので勝利確定である。
よって、最後の1手を取れない側は、最後までに偶奇どちらかを使い果たす戦略を取らない限り勝利できない。

以下全体のターン数をT=N-Kとする。

• 後手が最後の手番の場合(T%2==0)
  • 先手が勝利するには、最終的に奇数の要素が奇数個、偶数の要素が0個でなければならない。
  • よって、偶数要素が先手のターン数T/2以下で、かつKが奇数の場合のみ、先手が偶数を取りきる戦略で勝利可能。それ以外は後手必勝。
• 先手が最後の手番の場合(T%2==1)
  • 後手が勝利するには、奇数要素を最後までに取りきるか、もしくはKが偶数かつ偶数要素を取りきらなければならない。
  • よって、奇数要素が後手ターン数T/2以下であるか、もしくはKが偶数かつ偶数要素がT/2以下なら後手勝利可能。それ以外は先手必勝。

int N,K,D;
int O,E;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x;
		if(x%2) O++;
		else E++;
	}
	D=N-K;
	
	if(D==0) {
		if(O%2) _P("Stannis\n");
		else _P("Daenerys\n");
	}
	else if(D%2==0) {
		if((E<=D/2 && K%2==1)) _P("Stannis\n");
		else _P("Daenerys\n");
	}
	else {
		if(O<=D/2 || (E<=D/2 && K%2==0)) _P("Daenerys\n");
		else _P("Stannis\n");
	}
}

まとめ

他の2人ゲームと異なり、最後の1手を取るのがどちらか、で分岐が分かれるのが面白い。