Codeforces #386 Div2 E. Numbers Exchange

これDiv2でも1750ptぐらいだよなぁ。
http://codeforces.com/contest/746/problem/E

問題

N(偶数)個の整数があり、それぞれA[i]である。
これらの整数を1～Mのいずれかと交換できる。ただし同じ交換先の値は複数回使うことができない。

N個の整数をすべて異なるものにし、かつ偶奇の数を同等にできるか。
できるなら交換回数を最小化せよ。

解法

A中以下の整数は交換しなければならない。

• すでに同じ整数がA中にある。
• 非交換対象で偶奇の一致する整数がすでにN/2個ある。

あとは1～Mのうち、まだA中に含まれておらず、かつ偶奇の数が過半数にならない範囲で、交換しなければいけない整数と差し替えていけばよい。

ll N,K,A,B;
string R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>A>>B;
	
	if(A==B) {
		FOR(i,N/2) R+="GB";
	}
	else if(A<B) {
		if(B>(A+1)*K) return _P("NO\n");
		FOR(i,A+1) {
			FOR(x,B/(A+1)+(i<B%(A+1))) R+="B";
			if(i<A) R+="G";
		}
		
	}
	else if(B<A) {
		if(A>(B+1)*K) return _P("NO\n");
		FOR(i,B+1) {
			FOR(x,A/(B+1)+(i<A%(B+1))) R+="G";
			if(i<B) R+="B";
		}
	}
	cout<<R<<endl;
}

まとめ

うーん。