AIZU ONLINE JUDGE ALDS1_4_D Allocation を解いた記録
問題の概要
\(n\)個の荷物が順番に流れてくる．それぞれの荷物の重さは\(w_{i} (i=0, 1, \dots, n-1\)である．これらの荷物を\(k\)台のトラックに積む．
各トラックには連続する\(0\)個以上の荷物を積めるが，荷物の重さの和が最大積載量\(P\)を超えてはいけない．最大積載量\(P\)は全トラックで共通である．
最大積載量\(P\)の最小値を求めよ．
制約
- \(1 \leq n \leq 10^{5}\)
- \(1 \leq k \leq 10^{5}\)
- \(1 \leq w_{i} \leq 10^{4}\)
- 入力はすべて整数
解法
\(n\)個すべての荷物の重さの総和を\(w_{sum}\)とします．制約より，\(w_{sum} \leq 10^{9}\)です．
荷物が流れてくる順番は変えられないので，荷物の積み方は「トラックの最大積載量を超えない範囲で荷物を積めるだけ積み，積みきれなくなったら次のトラックに荷物を積む」という方法となります．
この方法で荷物を積む場合，最大積載量を\(P\)としたときに荷物を\(k\)台のトラックに積みきれるか否かは\(O(n)\)で判定できます．
よって，\(P=1, 2, \dots, w_{sum}\)として各\(P\)について荷物を\(k\)台のトラックに積みきれるか否かを検査すれば，\(P\)の最小値を求められます．
しかしこの方法では計算量が\(O(nw_{sum})\)となるため，プログラムの実行が制限時間内に終わりません．
ここで，二分探索によって\(P\)の最小値を求めることを考えます．最大積載量\(P\)について，明らかに次の性質が成り立ちます．
- \(P = 0\)のとき，\(P\)は明らかに条件を満たさない（すべての荷物をトラックに積みきれない）
- \(P = w_{sum}\)のとき，\(P\)は明らかに条件を満たす（すべての荷物をトラック1台に積める）
- \(0\)と\(w_{sum}\)の間に，条件を満たさない・満たすが切り替わる場所がある
- \(0\)から条件を満たさない・満たすが切り替わる場所までは常に条件を満たさない．また，切り替わる場所から\(w_{sum}\)までは常に条件を満たす（以下の画像のような感じです）
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 – Qiitaなどでも説明されている通り，このような場面では二分探索を用いて「条件を満たす\(P\)の最小値」を求められます．
二分探索を用いると，荷物を\(k\)台のトラックに積みきれるか判定する回数を\(O(\log w_{sum})\)程度にできます．
荷物を\(k\)台のトラックに積みきれるか否かの判定1回につき\(O(n)\), 判定を行う回数\(O(\log w_{sum})\)より，全体の計算量は\(O(n \log w_{sum})\)となります．これなら制限時間に間に合います．
実装例
二分探索の実装では，いわゆる「めぐる式二分探索」を用いています．この問題のように，答えとなる値を決め打ちして二分探索するとうまくいく場合があります．