ARC226 B - Bin-ary Packing

二進袋詰め

考え方

最小重量ピッタリのサイズを持つ袋を用意したとして、その袋のサイズを分割して考える。
全ての荷物は重さが $2$ の累乗なので、袋のサイズを $2$ の累乗ごとに分割して考えてよい。

例えばサイズが $13$ の袋が $3$ つある場合は、サイズ $8,4,1$ の袋が $3$ つずつあると考えてよい。
ここに、重さ $2$ のものを $2$ つ入れる場合、$4$ の袋に入れればいいだけである。
全ての荷物は重さが $2$ の累乗なので、この処理方法ができなくなることはない。

よって、袋の最小サイズを求める問題は、以下のように読み替えられる。

- これは、真の袋サイズを $2^i$ 拡張したことに相当する

この言い換えさえできれば、荷物が重い方から順に、以下を実行すればよい。

各テストケースの計算量は $O(M)$。
全テストケースでは $O\left(\sum M\right)$。

入力例1の $1$ つ目のテストケースのみ考える。

入力を受け取る。

n: 2
m: 3
a: {3, 2, 1}

bag は、現在見ている重さ $2^i$ をちょうど入れられる袋の個数を表すものとする。
また、真の袋のサイズを意味する結果用変数も用意し、ともに $0$ で初期化する。

bag: 0
result: 0

まず、i = 2、すなわち重さ $2^2 = 4$ の荷物を考える。
荷物が $1$ 個であるのに対して袋の個数が $0$ なので、袋が $1$ 枚足りない。

$1$ セット追加すると $N \times 1 = 2$ 枚の袋が増えるので、追加するセット数は $1$ となる。
真の袋サイズに $2^2\times1 = 4$ を加え、袋の個数に $2$ を加える。

result: 4
bag: 2

重さ $4$ の荷物を $1$ 個入れるので、袋の個数から $1$ を引く。
その後、残った重さ $4$ 分の袋 $1$ 枚は、重さ $2$ 分の袋 $2$ 枚とみなして使うことにする。

bag: 2

次に、i = 1、すなわち重さ $2^1 = 2$ の荷物を考える。
荷物が $2$ 個であるのに対して袋も $2$ 枚あるので、追加購入する必要はない。

重さ $2$ の荷物を $2$ 個入れるので、袋の個数から $2$ を引く。
袋は残らないので、半分サイズの袋に分けても袋の個数は $0$ のままである。

result: 4
bag: 0

最後に、i = 0、すなわち重さ $2^0 = 1$ の荷物を考える。
荷物が $3$ 個であるのに対して袋が $0$ 枚なので、袋が $3$ 枚足りない。

$1$ セット追加すると $N \times 1 = 2$ 枚の袋が増えるので、必要なセット数は $2$ となる。
真の袋サイズに $2^0 \times 2 = 2$ を加え、袋の個数に $4$ を加える。

result: 6
bag: 4

重さ $1$ の荷物を $3$ 個入れるので、袋の個数から $3$ を引く。

bag: 1

ループの都合上、この後で、重さ $1$ 用の袋を重さ $0.5$ 用の袋 $2$ 枚にする処理が走る。
しかし、結果を入れる変数はもう触らないので、無視してよい。

よって、答えは $6$。

答えや bag は、int 型からはみ出る。
long long 型を用いること。

特になし。