TopCoder SRM 568 Div1 Easy BallsSeparating

またしょうもないミスでEasyを落とした。
Mediumは今回難しくてどうにもならなかったし…。
http://community.topcoder.com/stat?c=problem_statement&pm=12398

最大50個の箱に赤青黄色の玉が1～100万個ずつ入っている。
これらの玉を箱の間で動かして各箱は１色の玉して入らないようにしたとき、動かす玉の数を最小化する問題。

考え方は２つあって、DPで解く方法と、赤・青・黄色を集める箱を先に３つ決める方法。
今回は箱の数がN<=50と小さいのでこちらで。

赤・青・黄色を集める箱を決めた場合、各箱にあるそれ以外の色の玉は動かさないといけないので、動かす玉の数にカウントする。
それ以外の箱は、数の少ない２色の玉を動かせば残り１色になるので、そのように２色の玉の数をカウントする。

赤・青・黄色の箱の決め方がN^3通り、その際の動かす玉の数のカウントがO(N)なので、併せてO(N^4)。
N<=50なのでこれでも100msで終わった。

下の問題、最小値を求めるときに初期値を1<<30にしているけど、本番1<<25にしていた…。
この問題、最大で100万個/色/箱×2色×50箱で1億になるので、1<<27ないとダメなのよね…。
なんとしょうもないミス…。
おかげでチャレンジで落とされた。

class BallsSeparating {
	public:
	int N;
	int minOperations(vector <int> red, vector <int> green, vector <int> blue) {
		int rr,gg,bb,i;
		N=red.size();
		
		if(N<3) return -1;
		
		int mi=1<<30;
		FOR(rr,N) FOR(gg,N) FOR(bb,N) {
			if(rr==gg || rr==bb || gg==bb) continue;
			int r=0;
			FOR(i,N) {
				if(i==rr) r+= green[i]+blue[i];
				else if(i==gg) r+= red[i]+blue[i];
				else if(i==bb) r += red[i]+green[i];
				else{
					r += red[i]+green[i]+blue[i]-max(red[i],max(blue[i],green[i]));
				}
			}
			mi=min(mi,r);
		}
		
		return mi;
	}
};

まとめ

最大値を見誤るとかつまらなすぎる…。
int型の仮置き最大値には1<<30か1e9を使うとよさそうね。