概要

荷物列 \(A_1,\dots,A_N\) を番号順のまま \(K\) 個の連続区間に分割するとき、各区間和の最小値をできるだけ大きくする（＝最小区間和の最大化）問題です。

考察

重要な気づき

• 各トラックに割り当てる荷物は「連続」なので、結局は 配列を \(K\) 個の連続区間に分割する問題です。
• 目標は「最小区間和」を最大化することですが、直接「最適な分割」を探すと分割位置が \(K-1\) 個あり組合せが膨大です（素朴探索は不可能）。

判定問題に変換する

「最小区間和の最大値」を直接求める代わりに、次の判定問題を考えます：

ある値 \(x\) を決めたとき、各区間和がすべて \(x\) 以上になるように、配列を \(K\) 個の連続区間に分割できるか？

これができるなら「最小区間和を \(x\) 以上にできる」＝「答えは少なくとも \(x\)」と言えます。

なぜ貪欲で判定できるか

\(A_i \ge 1\)（正の値）なので、左から順に足していき、和が \(x\) 以上になったらそこで区切るのが最善です。

• 早めに区切るほど、残りの要素を後ろの区間に回せるため、作れる区間数を最大化できます。
• よって、この貪欲法で「\(x\) 以上の区間を何個作れるか」を数え、\(K\) 個以上作れれば feasible と判断できます。

具体例

\(A=[2,1,3,2,2],\ K=3,\ x=4\) のとき
左から貪欲に足すと： - \(2+1+3=6 \ge 4\) で1区間目 - 次に \(2+2=4 \ge 4\) で2区間目 - もう残りがないので2区間しか作れず、\(3\) 区間作れない → 不可能

アルゴリズム

1. 二分探索（答えの探索）

答え（最大化したい最小区間和）を \(0\) 〜 \(\sum A_i\) の範囲で二分探索します。

• ある \(mid\) を試し、後述の feasible(mid) が True なら「もっと大きくできるかも」なので lo = mid
• False なら「大きすぎる」ので hi = mid - 1

2. 判定 feasible(x)（貪欲）

左から順に和 s を積み上げ、s >= x になったら区切って区間数 cnt を増やし、s=0 に戻します。
cnt >= K になった時点で True（\(K\) 区間作れた）です。

この方法が正しい理由は、正の数列では「到達したら即区切る」戦略が区間数を最大化し、可否判定に十分だからです。

計算量

• 時間計算量: \(O(N \log(\sum A_i))\)
  （二分探索が約 \(\log(\sum A_i)\) 回、各回で配列を1回走査して \(O(N)\)）
• 空間計算量: \(O(1)\)（入力配列以外は定数）

実装のポイント

• 二分探索の中央値は mid = (lo + hi + 1) // 2 のように 上寄せにすると無限ループを防げます（lo を更新する側の典型）。

• feasible では cnt >= K になったら即 True を返すと少し高速です。

• 上限 hi は最大でも \(\sum A_i\)（全荷物を1台に積んだときの和）で十分です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    total = sum(A)

    def feasible(x: int) -> bool:
        cnt = 0
        s = 0
        for a in A:
            s += a
            if s >= x:
                cnt += 1
                s = 0
                if cnt >= K:
                    return True
        return cnt >= K

    lo, hi = 0, total
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if feasible(mid):
            lo = mid
        else:
            hi = mid - 1

    print(lo)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。