Codeforces Global Round 29 : D. Game on Array

出だしからいまいちで、結果微妙な出来。
https://codeforces.com/contest/2147/problem/D

問題

整数列Aが与えられる。
ここでAがすべて0になるまで、2人ターン制のゲームを行う。

自分のターンでは、プレイヤーはAに含まれる正整数Xを1つ選ぶ。
A中のXの個数だけポイントを得たのち、A中のXをデクリメントする。
両者ポイントを増やすよう最適手を取ると、両者の最終スコアはいくらか。

解法

基本的にある値を選択すると得だと思うと、両者その値を(デクリメントしながら)交互に選択する。
よって、Aのうち偶数のものは、両者に半分ずつポイントを与える結果となる。
奇数のものについては1回を除いてやはり両者に半分ずつポイントを与える結果となる。

あとは「1回を除いて」の部分について、両者個数の多い順に選択するとしてよい。

int T,N,A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll X=0,Y=0;
		map<ll,ll> M;
		FOR(i,N) {
			cin>>A[i];
			if(A[i]%2==0) {
				X+=A[i]/2;
				Y+=A[i]/2;
			}
			else {
				M[A[i]]++;
				X+=A[i]/2;
				Y+=A[i]/2;
			}
		}
		vector<int> V;
		FORR2(a,b,M) V.push_back(b);
		sort(ALL(V));
		reverse(ALL(V));
		FOR(i,V.size()) {
			if(i%2==0) X+=V[i];
			else Y+=V[i];
		}
		cout<<X<<" "<<Y<<endl;
	}
}

まとめ

前半で躓くのつらいな…。