概要

\(N\) 個の部品からなる丸太を \(K\) 箇所で切断して \(K+1\) 個の断片に分けるとき、断片の長さの最大値を最小化する問題です。答えで二分探索する典型的な手法で解くことができます。

考察

重要な気づき：「答えを決め打ちする」

この問題は「最大値を最小化せよ」という形をしています。このタイプの問題では、答えの値 \(M\) を先に決め打ちして、それが達成可能かどうかを判定するという発想が非常に有効です。

具体的には、次の判定問題を考えます：

「各断片の長さが \(M\) 以下になるように、\(K\) 回以下の切断で分割できるか？」

この判定ができれば、\(M\) の値を二分探索で効率的に求められます。

素朴なアプローチではなぜダメか

切断箇所の選び方は \(\binom{N-1}{K}\) 通りあり、\(N\) が大きいと全探索は到底間に合いません。

判定問題の貪欲解法

「最大長 \(M\) 以下」で分割できるかの判定は、貪欲法で \(O(N)\) でできます。左から部品を順に足していき、合計が \(M\) を超えたらそこで切断し、新しい断片を始めます。この方法で必要な切断回数が \(K\) 以下なら「達成可能」と判定します。

具体例

\(A = [3, 5, 4, 7, 3]\), \(K = 2\) のとき：

• \(M = 10\) を試す → \([3,5]\)(合計8), \([4]\)で次に7を足すと11 > 10なので切断 → \([4,\,]\)切断して\([7,3]\)(合計10) → 切断2回 → OK
• \(M = 9\) を試す → \([3,5]\)(8), \([4]\)に7を足すと11 > 9 → 切断, \([7]\)に3を足すと10 > 9 → 切断 → 切断3回 → NG

よって答えは \(10\) です。

アルゴリズム

1. 二分探索の範囲を決める

   • 下限 \(lo = \max(A)\)（どんなに分割しても1つの部品は分割できない）
   • 上限 \(hi = \sum A\)（まったく切断しない場合の長さ）

2. 二分探索

   • \(mid = \lfloor (lo + hi) / 2 \rfloor\) に対して判定関数 can_split(mid) を呼ぶ
   • 達成可能なら \(hi = mid\)（もっと小さい値も可能かもしれない）
   • 達成不可能なら \(lo = mid + 1\)（もっと大きい値が必要）
   • \(lo = hi\) になったらそれが答え

3. 判定関数 can_split(max_len)

   • 左から部品を順に足していき、合計が max_len を超えたら切断回数を1増やして合計をリセット
   • 単独の部品が max_len を超えていたら即 False
   • 最終的に切断回数が \(K\) 以下なら True

計算量

• 時間計算量: \(O(N \log S)\)（\(S = \sum A_i\)）
  • 二分探索のループが \(O(\log S)\) 回、各ループ内の判定が \(O(N)\)
• 空間計算量: \(O(N)\)（配列 \(A\) の格納）

実装のポイント

• 二分探索の下限を \(\max(A)\) にすることで、判定関数内で「単独の部品が max_len を超える」ケースは初回チェック以降発生しませんが、安全のためガード条件を入れています。

• 貪欲法では「合計が max_len を超えたら切断」という処理で、切断後の新しい断片は超過を引き起こした部品から始めます（current = a）。

• sys.stdin.read() を使った高速入力により、大きな入力でもTLEを回避しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    def can_split(max_len):
        cuts = 0
        current = 0
        for a in A:
            if a > max_len:
                return False
            current += a
            if current > max_len:
                cuts += 1
                current = a
        return cuts <= K
    
    lo = max(A)
    hi = sum(A)
    
    while lo < hi:
        mid = (lo + hi) // 2
        if can_split(mid):
            hi = mid
        else:
            lo = mid + 1
    
    print(lo)

solve()

---

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