TopCoder SRM 837 : Div1 Medium HashingWithBackupTapes

問題設定がややこしい。
https://community.topcoder.com/stat?c=problem_statement&pm=17803

問題

H個のバケツがあり、これらに(b[i]番のバケツにc[i]個物を入れる)という手順のリストが与えられる。
すでにn個物が入ったバケツに物を1個追加するには、(n+1)のコストがかかる。

ここで、全部で最大T回、任意のタイミングでバケツを1つ選び中身を空にすることができる。
ただし、1回以上空にしたバケツについては、そのバケツに全体で物を追加した数yに対し、2*y*ceil(log(y))のコストがかかる。

最適なタイミングでバケツを空にしたとき、総コストの最小値を求めよ。

解法

各バケツについて、0～T回バケツを空にした場合のコストを考える。
あとは、空にする回数がT回以下の範囲で、各バケツの総コストを考えればよい。

各バケツについて、空にする回数を決めたら、そのタイミングは明らかに均等な間隔にするのがベストであり、そのコストは容易に計算できる。

int B[202020];
int C[202020];
ll sum[202020];

ll from[303],to[303];

class HashingWithBackupTapes {
	public:
	long long optimize(int H, int T, int N, int L, vector <int> W, int seed) {
		vector<int> who;
		
		ZERO(sum);
		int i,j;
		FOR(i,H) FOR(j,W[i]) who.push_back(i);
		ll state=seed;
		FOR(i,N) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
			B[i]=who[state%who.size()];
			state = (state * 1103515245 + 12345)%(1LL<<31);
			C[i]=1 + (state%L);
			sum[B[i]]+=C[i];
		}
		
		ZERO(from);
		int x,y;
		FOR(i,H) {
			FOR(j,T+1) to[j]=1LL<<60;
			ll pen=0;
			while(1<<pen<sum[i]) pen++;
			pen=(2*sum[i])*pen;
			FOR(x,T+1) {
				ll sc=0;
				ll a=sum[i]/(x+1);
				ll b=sum[i]%(x+1);
				sc+=b*(a+1)*(a+2)/2+(x+1-b)*(a+0)*(a+1)/2;
				if(x) sc+=pen;
				for(y=0;x+y<=T;y++) to[x+y]=min(to[x+y],sc+from[y]);
			}
			swap(from,to);
			
		}
		ll mi=1LL<<60;
		FOR(i,T+1) mi=min(mi,from[i]);
		return mi;
	}
}

まとめ

同じ内容でももう少し短い問題文にならないかな。