概要

長さ配列 \(A_1,\ldots,A_N\) を順番を保ったまま \(K+1\) 個に分割するとき、「各断片長の最大値 \(M\)」を最小化する問題です。
答えとなる \(M\) を二分探索し、ある上限 \(x\) で分割可能かを貪欲に判定します。

考察

重要な気づき

「最大断片長を \(x\) 以下にできるか？」という判定問題を考えると、次が成り立ちます。

• もし \(x\) が十分大きければ分割は可能
• \(x\) が小さすぎると不可能
• つまり「可能/不可能」は \(x\) に対して単調（\(x\) が大きいほど可能になりやすい）

この単調性があるので、最小の \(x\)（＝答え）を二分探索で求められます。

素朴案が難しい理由

切断箇所は \(N-1\) 個あり、そこから \(K\) 個選ぶので組み合わせは \(\binom{N-1}{K}\) 通りです。
\(N \le 2\times 10^5\) では全探索は到底不可能です。

判定をどう作るか（貪欲）

「最大断片長を \(x\) 以下にしたい」とき、左から順に

• 今の断片に追加しても \(x\) を超えないなら追加
• 超えるならそこで切って新しい断片を開始

とするのが最も断片数を少なくする貪欲です。
この方法でできた断片数が \(K+1\) 以下なら、\(x\) で分割可能です。

※問題は「ちょうど \(K\) 回切って \(K+1\) 断片」ですが、断片数が少なめ（\(\le K+1\)）でもOKです。長さはすべて正なので、断片をさらに細かく分割しても各断片長は増えません（最大値も悪化しない）ため、最終的にちょうど \(K+1\) 個に調整できます。

具体例：\(A=[3,1,4,1,5],\ K=2\)（3断片）で \(x=5\) を判定
貪欲に詰めると
- \(3+1=4\)（まだOK）、次の \(4\) を足すと \(8\) でNG → ここで切る（断片長 4） - 次は \(4+1=5\)（OK）、次の \(5\) を足すと \(10\) でNG → 切る（断片長 5） - 最後は \(5\)（断片長 5）
断片数は 3 個で \(K+1=3\) 以下なので可能、となります。

アルゴリズム

1. 答え \(M\) の探索範囲を決める
   
   • 下限 \(lo = \max(A_i)\)（どんな分け方でも最大断片長は少なくとも最大要素以上）
   • 上限 \(hi = \sum A_i\)（切らなければこの長さ）
2. 二分探索で \(x\) を試す
   
   • feasible(x)：最大断片長を \(x\) 以下にして断片数を \(K+1\) 以下にできるか
3. feasible(mid) が真なら上限を下げ、偽なら下限を上げる
4. \(lo=hi\) になった値が最小の達成可能な最大断片長（答え）

判定 feasible(x)（貪欲）： - 断片数 cnt=1、現在の断片和 s=0 - 左から順に、s+a <= x なら s+=a - そうでなければ新断片開始：cnt += 1, s = a - 途中で cnt > K+1 になったら不可能（False） - 最後まで行けたら可能（True）

計算量

• 時間計算量: \(O(N \log(\sum A_i))\)
  （二分探索が \(\log(\sum A_i)\) 回、各回の判定が \(O(N)\)）
• 空間計算量: \(O(N)\)
  （配列 \(A\) を保持）

実装のポイント

• 二分探索の下限は必ず max(A) にする（これより小さい \(x\) は絶対不可能）。

• 判定は「断片数が \(K+1\) 以下ならOK」とするのがコツ（ちょうどでなくてよい理由は考察の通り）。

• \(\sum A_i\) は最大で \(2\times 10^5 \times 10^9 = 2\times 10^{14}\) なので、Python 以外では 64bit 整数が必須です。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    need_segments = K + 1

    lo = max(A)
    hi = sum(A)

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

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

    print(lo)

if __name__ == "__main__":
    main()

---

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