読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 609, Division 1, Level 2 : PackingBallsDiv1

問題概要

 それぞれ色が異なる 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 の数毎に最小パッケージ数を計算して最小を求め、上記二つの操作によるパッケージ数を足し合わせたものが答えとなります。
 最初の二つの操作のオーダーは O( K ) であり、最後の手順では仮定した variety set の数あたり、O( 1 ) で手数を計算できるます。一番時間が掛かるのはソートの部分であり、全体でのオーダーは O( K \log K ) となるので 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;
	}
};