Codeforces ECR #031 : D. Boxes And Balls

いまいちな出来。
http://codeforces.com/contest/884/problem/D

問題

N色のボールがあり、i色目はA[i]個ある。

ここにN個の箱がある。
初期状態ですべてのボールが1個目の箱に入っている。
以下の処理を行い、i番目の箱にi色目のボールがすべて入っているようにしたい。

• ボールの入っている箱を一つ選び、中身をすべて抜き出す
• 空の箱を2つまたは3つ選び、先ほど抜き出したボールを任意の割り当てで配分する

1個目の処理の抜き出したボールの総数がコストだとする。
コストを最小化せよ。

解法

多くのボールを持つ色は、抜き出し回数を少なくしたい。
つまり、早い段階でそれらの色は指定の箱に納め、以後の処理を行わないようにしたい。

この処理を巻き戻し、N箱にあるボールに対し、逆に箱を3つずつ選んで集めていくことを考える。
そうすると、これはハフマン符号相当の処理に似ていることがわかる。
ハフマン符号は普通二分木で作るが、今回は三分木で同様に数が少ない箱を組み合わせていこう。
ただし最初に２個集める場合と３個集める場合は両方試しておく。

int N;
multiset<ll> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		M.insert(x);
	}
	
	ll ret=1LL<<60;
	FOR(i,2) {
		multiset<ll> M2=M;
		ll tot=0;
		
		if(i==1 && M2.size()>=2) {
			ll a=*M2.begin();
			M2.erase(M2.begin());
			a+=*M2.begin();
			M2.erase(M2.begin());
			M2.insert(a);
			tot+=a;
		}
		
		while(M2.size()>2) {
			ll a=*M2.begin();
			M2.erase(M2.begin());
			a+=*M2.begin();
			M2.erase(M2.begin());
			a+=*M2.begin();
			M2.erase(M2.begin());
			tot+=a;
			M2.insert(a);
		}
		if(M2.size()==2) {
			tot+=*M2.begin();
			M2.erase(M2.begin());
			tot+=*M2.begin();
		}
		ret=min(ret,tot);
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

これは割とすんなり。