概要

与えられた丸太を \(K\) 箇所で切断し、分割後の断片の長さの最大値 \(M\) を最小化する問題。

考察

この問題では、丸太をいくつかの断片に分割するときに、「最も長い断片ができるだけ短くなる」ように切断する必要があります。素朴な方法として、全ての可能な切断の組み合わせを試すことを考えられますが、\(N\) が最大 \(2 \times 10^5\) であり、組み合わせは非常に多いので現実的ではありません（計算量的にTLEになります）。

重要な観察は、「断片の長さの最大値 \(M\) の最小値を求めたい」という最適化問題は、二分探索によって効率的に解けるということです。つまり、「ある値 \(x\) 以下の最大断片長で分割可能かどうか？」という判定問題を繰り返し解くことで、最小の \(M\) を求めることができます。

この判定問題自体は貪欲法で解けます。左から順に部品を足していき、次に足すと上限 \(x\) を超えるならその時点で切る、という操作を繰り返します。切る回数が \(K\) 回以内であればOK、そうでなければNGです。

このように、「最小化する値を二分探索で求め、条件判定は貪欲法で行う」という典型的なテクニックが使える問題です。

アルゴリズム

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

   • 最小値：最も長い単一の部品（どの断片も少なくともこれ以上にはならない）
   • 最大値：全ての部品の合計（全部つなげたもの）

2. 二分探索を実施

   • mid を「断片の最大長の上限」として、その値で分割可能か判定
   • 判定関数 is_possible(max_len) は、貪欲に断片を作っていき、必要な切断回数が \(K\) 以下かどうかを確認

3. 貪欲な分割判定

   • 左から累積和を取るように部品をグループにまとめていく
   • 和が max_len を超えそうになったらそこで切る
   • 切った回数が \(K\) 以下ならOK

4. 最終的な答えを出力

計算量

• 時間計算量: \(O(N \log(\text{sum}(A)))\)
  • 二分探索の範囲は最大 \(10^{14}\) 程度なので、\(\log\) はせいぜい50程度
  • 判定関数内で配列を1周する処理が \(O(N)\)
• 空間計算量: \(O(N)\)
  • 入力配列の保持に \(O(N)\)

実装のポイント

• 二分探索の範囲を正しく設定すること（left = max(A), right = sum(A)）

• 切断回数のカウントを正確に行うこと（最初の断片はカット不要）

• 入力を高速に読み込むため、sys.stdin.readなどを用いると安心

  ソースコード

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(max_len):
        # 各断片の長さがmax_len以下になるように切る
        cuts = 0
        current_sum = 0
        for a in A:
            if current_sum + a > max_len:
                cuts += 1
                current_sum = a
                if cuts > K:
                    return False
            else:
                current_sum += a
        return True

    left = max(A)
    right = sum(A)
    while left < right:
        mid = (left + right) // 2
        if is_possible(mid):
            right = mid
        else:
            left = mid + 1
    print(left)

if __name__ == "__main__":
    main()

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