Codeforces #451 Div2 E. Squares and not squares

なんか最近CF Div2回が多いですね。
http://codeforces.com/contest/898/problem/E

問題

N要素(偶数)の整数列が与えられる。
各要素にいくつか値を増減し、半分を平方数、残り半分を非平方数にしたい。
増減量の総和の最小値を求めよ。

解法

まずN個を平方数と非平方数に分けよう。
N/2個より多い方から少ない方に移動させるので、必要増減量を求めて短い方から取ればよい。

必要な増減量の最小値は下記の通り。

• 平方数→非平方数 : 元の値が0なら2加算、それ以外は1加算
• 非平方数→平方数 : 元の値より大きい方と小さい方いずれかの平方数に寄せる。

int N;
int A[202020];

vector<int> S[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>x;
		y=sqrt(x+0.1);
		if(y*y==x) {
			if(x==0) S[0].push_back(2);
			else S[0].push_back(1);
		}
		else S[1].push_back(min((y+1)*(y+1)-x,x-y*y));
	}
	
	ll ret=0;
	if(S[0].size()>S[1].size()) {
		sort(ALL(S[0]));
		FOR(i,S[0].size()-N/2) ret+=S[0][i];
	}
	else {
		sort(ALL(S[1]));
		FOR(i,S[1].size()-N/2) ret+=S[1][i];
	}
	
	cout<<ret<<endl;
	
}

まとめ

これはDiv2とはいえEにしては簡単なような。