概要

\(N\) 個の区間からなるロープを \(K\) 本に分割するとき、最も長いロープの長さを最小化する問題です。「最大値の最小化」は二分探索の典型問題です。

考察

問題の性質に注目

この問題は「最大値を最小化せよ」という形式です。このような問題では、答えを決め打ちする二分探索が有効です。

素朴なアプローチの問題点

\(K-1\) 箇所の切る場所を全探索しようとすると、\(N-1\) 箇所から \(K-1\) 箇所を選ぶので \(\binom{N-1}{K-1}\) 通りあり、\(N\) や \(K\) が大きいとTLEになります。

発想の転換

「最大の長さが \(X\) 以下となるように分割できるか？」という判定問題を考えます。

• \(X\) が大きすぎる → 簡単に分割できる（Yesになりやすい）
• \(X\) が小さすぎる → 分割できない（Noになる）

この判定がYesとなる最小の \(X\) を二分探索で見つけます。

判定方法（貪欲法）

「最大長 \(X\) 以下で \(K\) 本以下に分割できるか？」は、貪欲法で \(O(N)\) で判定できます。

具体例：\(A = [3, 5, 4, 7, 6, 2]\), \(K = 3\), \(X = 12\) の場合 1. 区間を左から順に見ていく 2. 現在のロープに追加しても \(X\) を超えなければ追加 3. 超えるなら、そこで切って新しいロープを開始

\([3, 5, 4]\) → 合計12 ≤ 12 なのでOK
\([7]\) を追加すると 12 + 7 = 19 > 12 なので切る
\([7, 6]\) → 合計13 > 12 なので切る（でも7は単独で入れないといけない）
…という流れで判定します。

アルゴリズム

1. 二分探索の範囲を設定

   • 下限 \(\text{left} = \max(A)\)：どんなに頑張っても、最大の区間1つ分は必要
   • 上限 \(\text{right} = \sum A\)：全体を1本にした場合の長さ

2. 二分探索を実行

   • \(\text{mid} = (\text{left} + \text{right}) / 2\) を計算
   • 最大長 \(\text{mid}\) で \(K\) 本以下に分割できるか判定
     • できる → 答えは \(\text{mid}\) 以下、\(\text{right} = \text{mid}\)
     • できない → 答えは \(\text{mid}\) より大きい、\(\text{left} = \text{mid} + 1\)

3. 判定関数（貪欲法）

   • 左から順に区間を見て、現在のロープに追加
   • \(X\) を超えたら、そこで切って本数を +1
   • 最終的な本数が \(K\) 以下なら分割可能

計算量

• 時間計算量: \(O(N \log S)\)
  • \(S = \sum A_i\)（最大 \(10^{14}\)）
  • 二分探索が \(O(\log S)\) 回、各判定に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列 \(A\) を保持するのみ

実装のポイント

• 判定関数で、単一の区間が \(X\) より大きい場合は即座に False を返す

• 貪欲法では、現在の合計に追加して超えるなら「そこで切る」という処理を行う

• 二分探索の終了条件は left < right、答えは left（= right）に収束する

• Pythonでは整数のオーバーフローを気にする必要がないため、大きな値でも安心

  ソースコード

def can_divide(A, K, max_len):
    """最大長がmax_len以下でK本以下に分割できるかチェック"""
    count = 1
    current_sum = 0
    
    for a in A:
        if a > max_len:
            return False
        if current_sum + a > max_len:
            count += 1
            current_sum = a
        else:
            current_sum += a
    
    return count <= K

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 二分探索
    # 最小値: 最大の区間の長さ（これより小さくはできない）
    # 最大値: 全区間の合計（1本にする場合）
    left = max(A)
    right = sum(A)
    
    while left < right:
        mid = (left + right) // 2
        if can_divide(A, K, mid):
            right = mid
        else:
            left = mid + 1
    
    print(left)

solve()

---

この解説は claude4.5opus によって生成されました。