TopCoder SRM 609 Div1 Medium PackingBallsDiv1

Div1 MediumはDiv2 Mediumの上位互換問題。
500人以上Submitという最近のMediumでは平易な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12994

問題

K色のボールがある。それぞれの色のボールの個数はX[i]である。
これらを幾つかの箱に分類して入れたいが、箱に入れる際以下のルールがある。

• １つの箱に入るボールのは1～K個の範囲である。
• １つの箱に入るボールは、全て同じ色か、全て異なる色である。

全てのボールを入れるのに必要な最小の箱の数を答えよ。

解法

K色のボールを１個ずつ１つの箱に入れるのと、1色のボールをK個１つの箱に入れるのはどちらもK個分のボールを分類できる。
よって、まず各色K個より多い分は「１つの箱に同色のボールを入れる」のルールに従いX[i]/K個分の箱を使ってそこに全部入れてしまおう。

後は残りのボールを同色で箱に詰めるか異なる色で箱に詰めるかを最適化しなければならない。
まずX[i]%Kの値を昇順ソートしておく。

ソート後、各iについてX[i]個分の箱まで異なる色のボールを詰めると、残り(i+1)～(K-1)色の分はそれぞれ同色ボールを詰めた箱を準備することになり、必要な箱はX[i]+(K-i-1)となる。
各iについて総当たりし、X[i]+(K-i-1)の最小値を取ればよい。

計算量はX[i]のソートでO(K logK)。

ll X[100011];

class PackingBallsDiv1 {
	public:
	int minPacks(int K, int A, int B, int C, int D) {
		int i,x;
		ll tot=0;
		X[0]=A;
		FOR(i,K) X[i+1] = (X[i]*B+C)%D+1;
		
		FOR(i,K) tot+=X[i]/K,X[i]%=K;
		sort(X,X+K);
		if(X[K-1]==0) return tot;
		ll tot2=100000000;
		FOR(i,K) tot2=min(tot2,X[i]+(K-i-1));
		
		return tot + tot2;
	}
};

まとめ

Div1 Mediumとしては簡単な問題。