公式

B - Bin-ary Packing 解説 by snuke

荷物の重さの総和を \(W\) とします。

答えを二分探索し、答えを \(X\) 以下にできるか、すなわち容量 \(X\) の袋 \(N\) 個に全ての荷物を入れることができるかを判定します。

荷物を重い順に見ます。 重さ \(2^i\) の荷物に注目している時、空き容量が \(C\) の袋は以下の \(2\) 種類の袋に分割して構いません。

  • 容量 \(2^i\) の袋 \(\lfloor C/2^i \rfloor\) 個
  • 容量 \(C \bmod 2^i\) の袋 \(1\) 個
証明

$i$ についての帰納法で示します。

$i=0$ のとき、残る荷物の重さは全て $1$ なので明らかです。

$i\gt 0$ とします。元の袋に重さ $2^i$ の荷物が $k$ 個入っていたとすると、$k\le\lfloor C/2^i\rfloor$ なので、分割後も入れられます。

残る荷物の重さは $2^{i-1}$ 以下です。容量 $2^i$ で分割してから $2^{i-1}$ で分割しても、直接 $2^{i-1}$ で分割しても結果は同じであるため、帰納法の仮定を使うことができます。


常に容量の種類が \(2\) 種類以下となるため、同じ容量の袋をまとめながらシミュレーションすることで \(O(M \log W)\) で解くことができます。

投稿日時:
最終更新: