値ではなく、成立する境界を探す
荷物の重さが1、2、3、4、5の順に並んでいます。順番を変えず、一日に載せる重さが容量Cを越えないよう、三日以内に送り切る最小のCを求めます。配列の中から特定の値を探す問題ではありません。容量という答えの候補へ「この容量で三日以内に終わるか」と質問し、成立する最初の整数を探します。荷物は分割せず、一つの荷物を別の日へまたがらせません。
容量が増えれば、以前の積み方をそのまま使えるため、必要な日数が増えることはありません。成立しない候補の後に成立する候補が並ぶという単調性が、答えの二分探索の出発点です。候補が数値であるだけでは二分探索できません。条件を緩めたのに成立しなくなる場面がないかを、実際の問題の契約から確認してください。
一つの容量を判定する
容量6なら、最初の日に1、2、3を載せ、二日目に4、三日目に5を載せられます。容量5では1と2、次に3、次に4、最後に5となり四日必要です。判定は順に荷物を見て、次を載せると容量を越える場合だけ日を進めます。説明用の入力では6が成立し、5が成立しないため、境界は6です。実装が返した数値だけでなく、この隣接する二条件を確認します。
順序を固定した非負の荷物では、各日に可能な限り載せる貪欲な判定が使えます。最初の日を早く切り上げても、後の日へ残る荷物は減らず、有利にはなりません。この理由を省き、何となく詰め込む判定を置くだけでは、外側の二分探索が正しくても問題全体の正しさは保証できません。判定の妥当性と境界探索の妥当性を二段階で説明します。
| 容量 | 一日ごとの荷物 | 3日以内か |
|---|---|---|
| 5 | [1,2] / [3] / [4] / [5] | いいえ:4日 |
| 6 | [1,2,3] / [4] / [5] | はい:3日 |
探索区間に答えを閉じ込める
空でない入力では、最も重い荷物の重さをlo、全荷物の合計をhiとします。一つの荷物すら載らない容量は候補から除けます。一方、合計が載るなら一日で終えられるため、Dが正ならhiは成立します。lo自体が成立している場合もあるので、loを常に不成立の番兵とみなす実装とは違います。ここでは答えが閉区間lo以上hi以下へ入っているという不変条件を使います。
midが成立すれば、答えはmid以下にあります。midも答えの候補なのでhi=midです。不成立ならmid以下を捨て、lo=mid+1とします。lo<hiで反復するため、区間の長さは毎回小さくなり、同じmidを無限に試しません。境界の約束を別の二分探索の書き方から部分的に借りると、答えを捨てる誤りや停止しない誤りが入りやすくなります。
小さな全探索で確かめる
掲載コードは負の重さとD<1を拒否し、空の荷物列には容量0を返します。重さ0は許します。重さが非負なので、空でない入力でも全てゼロならlo=hi=0となり、そのまま答えです。days関数は容量へ入らない荷物があれば、成立しないと判定できる十分大きい日数を返します。通常の探索ではloを最大重量にしているため、この枝へ入る容量を選びません。
検査では長さ1〜5、各重さ0〜2の列と複数の日数を作り、最大重量から合計まで一つずつ容量を試す参照解へ一致させます。全探索の候補範囲を小さく保てるので、境界だけでなく途中の値も比較できます。大きな入力で一回正しい数値が出た結果より、小入力を広く検査した記録と不変条件の説明を組み合わせる方が、変更時の判断材料になります。
from itertools import product
def days(weights,capacity):
used=1;load=0
for w in weights:
if w>capacity:return len(weights)+1
if load+w>capacity:used+=1;load=0
load+=w
return used
def capacity(weights,D):
if D<1 or any(w<0 for w in weights):raise ValueError('invalid inputs')
if not weights:return 0
lo=max(weights);hi=sum(weights)
while lo<hi:
mid=(lo+hi)//2
if days(weights,mid)<=D:hi=mid
else:lo=mid+1
return lo
assert capacity([1,2,3,4,5],3)==6
for n in range(1,6):
for weights in product(range(3),repeat=n):
for D in range(1,4):assert capacity(weights,D)==next(c for c in range(max(weights),sum(weights)+1) if days(weights,c)<=D)
assert capacity([],3)==0
print('example minimum=6; exhaustive small-capacity checks passed')
判定の費用も掛け合わせる
候補の整数幅をUとすると、二分探索の判定回数はO(log(U+1))です。一回のdaysは全荷物を走査するためO(n)で、全体はO(n log(U+1))になります。O(log n)と書いてしまうと、荷物数と容量の候補幅を混同します。最大値と合計を求める準備のO(n)も含め、通常の固定幅整数での比較・加算を基準にした評価であることを説明します。
入力を巨大な任意精度整数に広げるなら、加算や比較の桁数も費用へ関係します。固定幅の言語では、合計やmidの計算のオーバーフローも検討します。また、判定を途中でD日超過した時点で打ち切る工夫はできますが、最悪の場合の走査上限が変わるとは限りません。実装上の早期終了による観測と、入力全体に対する漸近的な上限を分けて記録してください。
単調性が失われる条件を見抜く
同じ容量で送れるかに加え、「各日の使用量がちょうど容量と等しいこと」という条件を付けると、容量を増やすほど常に有利とは限りません。合計と日数の関係で成立する値が飛び飛びになるため、最初の成立点を一方向の境界として扱えません。また、配送会社の料金が容量帯で変わる最安値を探す問題は、容量の最小化と同じではありません。目的関数と成立条件を分離します。
荷物の並べ替えを許した場合も、外側の単調性が残る一方、順番に詰めるdaysが正しい最小日数を返すとは限りません。たとえば大きい荷物を後ろへ置いたために空きが残ることがあります。元の問題へ条件を足したり外したりするときは、判定関数の証明から見直してください。二分探索のコードを変える必要がなくても、判定の中身をそのまま流用できるとは限りません。
成立判定を境界だけでなく検査する
最小値を返す実装の検査では、答えが成立し、その一つ下が範囲内なら成立しないことも確認できます。ただし、判定関数自体を間違えたまま両方へ使えば、二つの検査が同じ誤りを共有します。小入力では荷物の区切り位置を全て列挙するなど、別の方法で実際の最小日数を照合する検査も考えます。掲載例の全容量探索は境界ループの検査に役立ち、判定の証明は貪欲な詰め方の説明で補います。
要件を変更した際は、どの部分を再検証すべきかを分けます。日ごとに異なる容量や、特定の組合せを同じ日に置けない条件が増えれば、単純なdaysの妥当性は引き継げません。境界探索、成立判定、入力の正規化という三つの責務を分けておけば、変更で影響した仮定を追いやすくなります。
成立する隣の候補も示す課題
課題は重さ2、2、3、日数2について、最小容量とその一つ下の判定を示すことです。解答は容量4で、初日に2と2、次の日に3を載せます。容量3では2、2、3が別の日になり三日必要です。したがって4は成立し3は不成立です。答えだけを書く代わりに、成立の具体的な積み方と、不成立を判定する履歴を両方示してください。
追加課題は日数を1へ変えることです。解答は合計7で、容量6では一日に全て載りません。日数を3以上へ緩めると最大重量3まで下がります。日数の変更が最小容量をどちらへ動かすかを予想し、コードの結果と照合します。候補の境界、不変条件、一回の判定、全体の費用を別々に説明できれば、この例以外の答えの二分探索へ進む準備ができます。