概要

\(N\) 個の荷物を番号順に連続して \(K\) 台のトラックに割り当て、各トラックの積載量の最小値を最大化する問題。

考察

この問題では、荷物を番号順に連続して区切って \(K\) 個のグループに分ける必要があり、各グループの合計値（積載量）の最小値を最大化することが目的です。

素朴な方法として、すべての区切り方を試すのは組み合わせが多すぎて計算量的に無理があります（例えば \(_{N-1}C_{K-1}\) 通り）。また、貪欲に小さいところから区切っていくのも、最適解にならないことがあります。

重要な観察は「ある値 \(x\) について、すべてのトラックの積載量が \(x\) 以上であるような分割ができるかどうか」という判定問題を考えると、これは比較的効率的に解けることです。そして、この判定問題が YES となる最大の \(x\) こそが求めたい答えになります。

このような「最大化問題を判定問題に言い換えて二分探索する」テクニックは典型的で、「二分探索の答えの最大化」と呼ばれます。

具体的には： - 答えの上限は全体の合計を \(K\) で割った値程度（全トラックに均等に割り振った場合） - 下限は \(0\) とすることができます - この範囲で「積載量の最小値を \(x\) 以上にできるか？」を二分探索で調べます

判定関数 is_possible(x) では、前から貪欲に合計が \(x\) 以上になるごとに区切りを入れていきます。最終的に区切り数が \(K\) 以上であれば OK です。

アルゴリズム

1. 二分探索の範囲を設定：left = 0, right = sum(A) // K + 1
2. mid = (left + right) // 2 として、is_possible(mid) を判定
3. 条件を満たせば left = mid、そうでなければ right = mid
4. right - left == 1 になったら left が答え

判定関数 is_possible(min_load)

• 前から順に荷物を加算していき、合計が min_load 以上になったら区切りを入れる（カウントアップ）
• 最後に区切った数が \(K\) 以上なら OK

計算量

• 時間計算量: \(O(N \log(\sum A_i))\)
  • 二分探索の各ステップで \(O(N)\) の判定を行う
  • 探索範囲は最大で \(\sum A_i\) 程度なので、\(\log\) がつく
• 空間計算量: \(O(1)\)
  • 追加のデータ構造を使用していない

実装のポイント

• is_possible 関数内で、最後に残ったグループが min_load 未満でも、それはカウントに入れない（次のトラックがないので）
• right の初期値は少し大きめに取ると安全（sum(A) // K + 1 など）
• 判定部分は前から貪欲にシミュレートすれば良い

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    def is_possible(min_load):
        count = 0
        current_sum = 0
        for a in A:
            current_sum += a
            if current_sum >= min_load:
                count += 1
                current_sum = 0
        return count >= K

    left = 0
    right = sum(A) // K + 1

    while right - left > 1:
        mid = (left + right) // 2
        if is_possible(mid):
            left = mid
        else:
            right = mid

    print(left)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。