torus711 のアレ

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

TopCoder, SRM 622, Division 2, Level 2 : BoxesDiv2

問題概要

 いくつかの飴を持っている。飴には種類があり、i 番目の種類の飴の数は candyCounts[ i ] で与えられる。また、非負整数 i を用いて 2^i と表せる大きさの箱を無限個持っている。
 今、飴を箱に詰めようとしている。手順は次の二段階からなる。
 まず、全ての飴を箱に入れる。ただし、同じ種類の飴は同じ箱に入れなければならず、一つの箱に複数種類の飴を入れてはならない。このとき、箱の大きさは入れようとしている飴の総数以上の値でなければならない。
 次に、飴の入った箱をより大きな箱に入れる。一つの箱に入れられる箱は丁度二つであり、その大きさは入れようとしている箱の大きさの和以上でなければならない。この手順は残っている箱が一つになるまで繰り返される。
 最後に残る箱の大きさとして可能な値の最小値を求めよ。

解法

 まず、飴を箱に入れる段階について考えます。できるだけ小さい箱に入れた方が次の段階に於いて有利になるので、各 a ∈ candyCounts に対して必要な箱の大きさの最小値を求めます。a を非負整数 k を用いて 2^k と表せる場合、これは自明に大きさ 2^k の箱に詰めるのが最適となります。そうではない場合、a に対し 2^k < a < 2^{k+1} となる k が丁度一つ存在します。このとき、2^{k+1} は a 以上の 2 の冪の内最小のものなので、大きさ k^{k+1} の箱に詰めるのが最適となります。k は、a を二進数で表したときに立っているビットの内、最も上位にあるものの位置を、下位桁から 0-based で数えた値と等しくなります。これは __builtin_clz を使うと 31 - __builtin_clz( a ) と書けます。a が 2 の冪でない場合、すなわち __builin_popcount( a ) /= 1 の場合は更に +1 です。これで a に対して最小の箱の大きさを求められるので、candyCounts の要素を全てこの手順で変換すれば、二番目の手順で詰めなければならない箱の大きさの集合 candyCounts' を得られます。
 次に、箱を箱に詰める段階について考えます。この段階では b ∈ candyCounts' は全て 2 の冪になっています。ある二つの箱を選択したとき、その二つの箱を詰めるために必要な箱の大きさの最小値を考えます。選択した箱の内大きい方の大きさを 2^k とすると、その二倍の大きさがあれば他方の箱も詰めることができるので、2^{k+1} の箱に詰めるのが最適となります。つまり、選択した二つの要素の内小さい方が消えて、大きい方は二倍になります。箱を選択する順序ですが、空間を無駄にしないようにすると考えると、同じ大きさの箱同士を優先的に詰めた方が無駄がありません。その後は、大きい要素はできるだけ二倍されない方が結果が良くなるので、より小さい箱から詰めていくのが最適戦略となります。二進数の各桁に対応する大きさの箱が存在するか否かを割り当てたと考えると、前半部分は candyCounts' の総和を計算することで、完了後の箱集合 candyCounts'' を表す整数エンコード表現を得ることができます。また、後半の戦略によって得られる答えは、candyCounts'' の要素数が 1 のとき candyCounts'' の唯一の元に一致し、そうでないときは candyCounts'' の最大元を二倍した値です。結局これは一段回目の手順で a に対する最小の箱の大きさを求めたのと同じ手続きなので、関数化しておけば再利用できます。

コード

#define ALL( c ) (c).begin(), (c).end()

class BoxesDiv2
{
public:
	int findSize(vector <int> candyCounts)
	{
		auto f = []( const int a ){ return  1 << ( 31 - __builtin_clz( a ) + ( __builtin_popcount( a ) != 1 ) ); };
		transform( ALL( candyCounts ), candyCounts.begin(), f );
		return f( accumulate( ALL( candyCounts ), 0 ) );
	}
};