Codeforces #251 Div2 C. Devu and Partitioning of the Array

CF251に参加。C,Dが順調だったこともあり、全完Div2回過去最高順位で終えることができた。
http://codeforces.com/contest/439/problem/C

問題

N個のdistinctな整数A[i]が与えられる。
この整数群を空でないK個のグループに分割したい。
この時、P個のグループの総和は偶数、K-P個の総和は奇数となるように分割する一例を答えよ。

解法

分割できないのは以下のいずれかの場合。

• A[i]に奇数がK-P個未満しかない。この時K-P個の奇数グループを作れない。
• A[i]に奇数が(K-P)+奇数個ある。この場合、奇数グループはK-P個ちょうどにならず1個奇数が余る。
• A[i]から奇数を(K-P)個取り除くと、P個の偶数を作れない。すなわち残った奇数の半分と偶数の個数を足してPに満たない。

逆にそれ以外の場合は以下のように条件を満たす分割ができる。

• まず奇数のうち(K-P)個を先頭(K-P)グループに1個ずつ分配する。
• 残った奇数を2個ずつペアにしたもの、または偶数を1個で残りのPグループに1つずつ分配する。
• これでもうP個条件を満たすグループができているので、余って未分配の奇数偶数はまとめてどこかのグループに追加する。

int N,K,P;
int A[100001];
vector<int> E,O,R[100001];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>K>>P;
	FOR(i,N) {
		cin>>x;
		if(x%2) O.push_back(x);
		else E.push_back(x);
	}
	x=y=0;
	if(K-P>O.size()) return _P("NO\n");
	if((O.size()-(K-P))%2) return _P("NO\n");
	FOR(i,(K-P)) R[i].push_back(O[x++]);
	for(i=K-P;i<K;i++) {
		if(x<O.size()) R[i].push_back(O[x++]),R[i].push_back(O[x++]);
		else {
			if(y>=E.size()) return _P("NO\n");
			else R[i].push_back(E[y++]);
		}
	}
	while(x<O.size()) R[0].push_back(O[x++]);
	while(y<E.size()) R[0].push_back(E[y++]);
	_P("YES\n");
	FOR(i,K) {
		_P("%d",R[i].size());
		ITR(it,R[i]) _P(" %d",*it);
		_P("\n");
	}
}

まとめ

この問題、意外と本番正答率が低かったようだ。