Looksery Cup 2015 C. The Game Of Parity

問題のレベル的にはE,F以外は解けるべきだったんだよな…ていうかこの問題設定何やねん…石取りゲームにすればええやん…

問題

Problem - 549C - Codeforces

解法

とりあえずゲーム木考えるのはアリだと思いますが状態量がn*nになり,今回の問題の制約では間に合いません。

じゃあどないすんねんってことですが,よく考えると最後に町を焼き払える人が最後に偶奇を変更できるのでかなり有利です。もう一方の人は,最後の人が焼き払える町を一意にする以外には勝ち目がありません。

ということで大まかな方針としては,最後に町を焼き払う人,およびkの偶奇で場合分けするだけです。

それぞれの場合にどのようにするかはコードを見てください。

ただし,n=kの時はどちらの意思にも関係なく勝敗が決まるので特別に場合分けしなければならないことに注意。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
	const string S = "Stannis", D = "Daenerys";
	int n, k;
	cin >> n >> k;
	int odd = 0, even = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a%2) odd++;
		else even++;
	}
	if (n == k) {
		// 奇数ならSの勝ち
		if (odd%2) cout << S << endl;
		// 偶数ならDの勝ち
		else cout << D << endl;
	} else {
		int turn = (n-k)/2;
		// last=0:Dが最後 last=1:Sが最後
		int last = (n-k)%2;
		if (last == 0) {
			if (k%2 == 1) {
				if (turn >= even) {
					cout << S << endl;
				} else {
					cout << D << endl;
				}
			} else {
				cout << D << endl;
			}
		} else {
			if (k%2 == 1) {
				if (turn >= odd) {
					cout << D << endl;
				} else {
					cout << S << endl;
				}
			} else {
				if (turn >= odd || turn >= even) {
					cout << D << endl;
				} else {
					cout << S << endl;
				}
			}
		}
	}
    return 0;
}