Codeforces #182 Div1. A. Yaroslav and Sequence

この回は本番A,B解いてそこそこの順位。
http://codeforces.com/contest/301/problem/A

問題

自然数Nに対して2N-1要素の数列が与えられる。
ここで、この数列中任意のN要素を選び、符号を反転させる、という処理を任意の回数行える。
数列の要素の和を最大化し、その値を答えよ。

解法

N個の要素を符号反転させ、次に最初に選んだN個のうち１個だけ差し替えると、任意の２要素の符号を反転させることができる。
よって、マイナス符号の要素の数を維持したまま、マイナス符号が着く要素を交換することができる。

後は、処理を繰り返してマイナス符号の数を最少化すればよい。
マイナス要素がK個あるとき、マイナス要素K個からi個、プラス要素(2N-1-K)個から(N-i)個選択することで、マイナスの数を(K-1)+(N-i)個にすることができる。
上記処理をDFSでマイナス要素数が最小化するまで繰り返せばよい。

int N;
vector<int> V;

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	
	N=GETi();
	V.clear();
	y=0;
	FOR(i,2*N-1) {
		x=GETi();
		if(x<0) y++;
		V.push_back(abs(x));
	}
	sort(V.begin(),V.end());
	
	int hoge[1000];
	ZERO(hoge);
	
	queue<int> q;
	q.push(y);
	hoge[y]=1;
	
	while(!q.empty()) {
		int k=q.front();
		q.pop();
		
		FOR(i,N+1) {
			if(i>k || N-i > 2*N-1-k) continue;
			if(hoge[k-i+N-i]==0) {
				hoge[k-i+N-i]=1;
				q.push(k-i+N-i);
			}
		}
	}
	
	int mi=-1, sum=0;
	FOR(i,2*N-1) {
		if(hoge[i]==1) mi=1;
		sum += mi*V[i];
	}
	
	_P("%d\n",sum);
	
	return;
}

まとめ

A問題の割に長くなった。
任意の２要素の符号反転が可能なことから、マイナスな数は0個か1個になるはずだけどもっと簡単に書けないかな…。