問題概要
それぞれ色が異なる K 種類のボールがあり、色 i のボールは X[ i ] 個ある。これらのボールをパッケージに分割したい。一つのパッケージには 1 〜 K 個のボールが含まれ、加えて以下の二つの条件の内いずれかを満たす。
- normal set である : パッケージに含まれるボールの色が全て同じ
- variety set である : パッケージは同じ色のボールを含まない
最小でいくつのパッケージに分割することができるか、求めよ。
解法
まず、全てのボールが K 個以上あるとき、全てのボールを含む variety set を K 個作ることと、K 個のボールを含む normal set を全ての色から作ることは同じ結果となります。いずれの操作にしても、できるだけ多くのボールをとった方が残りのボールが少なくなって得なので、全てのボールが K 個以上ある間は、K 個ずつ取り除いてよいことになります。
上記の操作を終えてなお K 個以上存在する色が残っているとき、K 個のボールを含む normal set として取り出した方が得になります。これは、同じ結果を得るために variety set として取り出すより操作回数が少なくなるためです。上記操作の特性から K 個以上残っている色は K - 1 色であるので、それら全ての色から K 個取り出すために作らなければならない normal set は K - 1 個です。一方、variety set で K 個ずつ取り出すためには K 個のパッケージを作らなければならないことから妥当であることがわかります。
ここまでの操作で、全てのボールの数は K 個未満となっています。残りのボールから構成される variety set の数の候補は、いずれかのボールの残り数のどれかです。というのも、variety set を構成するときにできるだけ多いボールを取っていくとすると、いずれのボールの残数でもない数になるケースは存在しないからです。variety set の数を決めたとき、全てのボールの数が K 未満であることから、variety set の数より大きい残数をもつボールの種類数だけ、normal set を構成する必要があります。ボールの残数を降順ソートしたときの i 番目 ( 0-indexed ) のボールの数を variety set の数と仮定したとすれば、normal set の数は i + 1 個であることが分かります。variety set の数毎に最小パッケージ数を計算して最小を求め、上記二つの操作によるパッケージ数を足し合わせたものが答えとなります。
最初の二つの操作のオーダーは であり、最後の手順では仮定した variety set の数あたり、
で手数を計算できるます。一番時間が掛かるのはソートの部分であり、全体でのオーダーは
となるので Time Limit にも間に合います。
コード
typedef long long LL; typedef vector<int> VI; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( v, c ) for ( auto &v : c ) #define ALL( c ) (c).begin(), (c).end() class PackingBallsDiv1 { public: int minPacks( int K, int A, int B, int C, int D ) { VI X( K ); X[0] = A; REP( i, 1, K ) { X[i] = ( LL( X[ i - 1 ] ) * B + C ) % D + 1; } int res1 = 0; { const int m = *min_element( ALL( X ) ); res1 += m; FOR( x, X ) { x -= m; res1 += x / K; x %= K; } } int res2 = INT_MAX; sort( ALL( X ), greater<int>() ); REP( i, 0, K ) { res2 = min( res2, X[i] + i ); } return res1 + res2; } };
