概要

区間ごとの長さが決まっているロープを境目で切って \(K\) 本に分けるとき、「最も長いロープの長さ」を最小化する問題です。
答え（最大長の最小値）を二分探索し、ある上限で分割可能かを貪欲に判定します。

考察

重要な気づき

「分割後の各ロープの長さがすべて \(x\) 以下にできるか？」という判定問題を考えます。

• もし上限 \(x\) で分割できるなら、より大きい上限 \(x' \ge x\) でも必ず分割できます（条件が緩くなる）。
• 逆に \(x\) で無理なら、より小さい上限では当然無理です。

つまり、判定結果は \(x\) に対して 単調性（false → true に一度だけ切り替わる）を持ちます。
この性質があるので、最小の「true になる \(x\)」を二分探索で求められます。

素朴な方法が難しい理由

切り方（\(K-1\) 箇所の切断位置）を全探索すると、組合せは \(\binom{N-1}{K-1}\) 通りもあり、\(N \le 10^5\) では到底間に合いません。

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

上限 \(x\) が与えられたとき、左から順に区間を足していき、

• 現在のロープに次の区間を足しても \(x\) 以下なら足す
• 超えるならそこで切って新しいロープを開始

とするのが最適（＝必要なロープ本数を最小化）です。
この貪欲で作った本数が \(K\) 本以下なら「\(x\) で可能」と言えます（余った分は切らずにまとめればよいので、ちょうど \(K\) 本にすることも可能です）。

具体例

\(A=[2,3,4,2],\ K=2\) とし、上限 \(x=6\) を判定すると：

• 2 + 3 = 5（まだOK）
• 次の 4 を足すと 9 で超える → 切る（1本目は 5）
• 2本目は 4 + 2 = 6

2本で収まるので可能（true）。
一方 \(x=5\) だと 2+3=5、次は切って 4、次の 2 を足すと 6 で超えるのでまた切って合計3本になり不可能（false）。

アルゴリズム

1. 探索範囲を決める
   
   • 下限 \(lo = \max(A)\)（どんな切り方でも、区間1つは必ずどこかのロープに入り、それより短くはできない）
   • 上限 \(hi = \sum A\)（切らなければ1本でこの長さ）
2. 判定関数 can(x) を作る
   
   • 貪欲に左から詰めていき、必要なロープ本数 cnt を数える
   • cnt > K になったら不可能（false）
   • 最後まで行けたら可能（true）
3. can(x) の単調性を利用して、\([lo, hi]\) で二分探索
   
   • can(mid) が true なら hi = mid
   • false なら lo = mid + 1
4. 探索が終わった lo が答え

計算量

• 時間計算量: \(O(N \log(\sum A))\)
  （判定が \(O(N)\)、二分探索が \(\log(\sum A)\) 回）
• 空間計算量: \(O(1)\)（入力配列を除く）

実装のポイント

• 二分探索の初期値は lo = max(A), hi = sum(A) とする（範囲が正しく狭まる）。

• 判定の貪欲では「超えたら切る」を徹底し、cnt > K の時点で早期 return すると高速です。

• K 本「以下」で作れれば良い点が重要です（余分に切らなければ本数は増やせないため、cnt <= K ならちょうど \(K\) 本に調整可能）。

  ソースコード

import sys

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

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

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

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

    print(lo)

if __name__ == "__main__":
    main()

---

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