CSAcademy Unfair Game

csacademy.com

＜問題＞
AlexとBenでゲームをします。
つの整数が与えられて、AlexとBenは次のような行動を交互にとります。(Alexが先手)
Atex:１つ以上の整数を選び、和を自分の得点に足す
Ben:１つの整数を選び、和を自分の得点にたす。
どちらかが、最後の整数を選んだらゲーム終了です。
Alexは自分の得点を最大化、BenはAlexの得点を最小化させるように行動するとき、
Alexの得点はいくらになるか。

＜解説＞
Alexは初手で、０以上の整数をすべてとります。
残った負の整数に対して、ソートして、大きい方から偶数番目・奇数番目のどちらかをとっていくことになるので、シミュレーションします。
0以上の数があるのとないのとでは、初手で偶数番目・奇数番目の調整をする動きがかわります。
ある場合は、負の数を１つもとらないor負の数を１つとることで調整します。
ない場合は、負の数を１つとるor負の数を２つとることで調整します。

＜コード＞

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	bool all_negative = true;
	int n;
	cin >> n;
	vll a(n);
	rep(i, n)cin >> a[i];
	vll b;
	ll ans = 0;
	rep(i, n) {
		if (a[i] < 0) {
			b.pb(a[i]);
		}
		else {
			ans += a[i];
			all_negative = false;
		}
	}
	
	sort(ALL(b));
	reverse(ALL(b));
	if (!all_negative) {
		int tmp1 = 0;
		for (int i = 0; i < b.size(); i += 2)tmp1 += b[i];
		int tmp2 = 0;
		for (int i = 1; i < b.size(); i += 2)tmp2 += b[i];
		P(ans + max(tmp1, tmp2));
	}
	else {
		int tmp1 = 0;
		for (int i = 0; i < b.size(); i += 2)tmp1 += b[i];
		int tmp2 = b[0];
		for (int i = 1; i < b.size(); i += 2)tmp2 += b[i];
		P(max(tmp1, tmp2));
	}
	return 0;
}

＜感想＞
テストケースをみて、最小の数以外すべてとる戦法にこだわってしまった・・・。