概要

ロープを区間ごとに切ってちょうど \(K\) 本に分割し、最も長いロープの長さを最小化する問題。

考察

この問題では、ロープを \(K\) 本に分割したときの「最も長いロープの長さ」を最小にすることが目的です。
素朴な方法として、すべての切り方を試すことが考えられますが、区間数 \(N\) が最大 \(10^5\) であるため、組み合わせ爆発により現実的ではありません。

重要な観察は、「最も長いロープの長さの最小値」に対して二分探索が使えるということです。
つまり、「ある長さ \(X\) 以下にできるか？」という判定問題を解くことができれば、二分探索によって最小の \(X\) を求めることができます。

判定関数 can_split では、貪欲法を用いてロープを順にグループ分けしていきます。現在のグループに区間を追加しても長さが \(X\) を超えないなら追加し、超えるなら新しいグループを作ります。もしグループ数が \(K\) を超えたら、その \(X\) では無理だと判定します。

このように、最適化問題を「Yes/No」の判定問題に落とし込むことで、効率的に解くことができます。

アルゴリズム

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

   • 最小値：最も長い単一区間の長さ（max(A)）
   • 最大値：全区間の合計長（sum(A)）

2. 二分探索を行う：

   • 中央値 mid を取り、「長さ mid 以下で \(K\) グループに分割可能か？」を判定関数 can_split で確認。

3. 判定関数 can_split：

   • 各区間を先頭から見ていき、現在のグループに加えても長さが mid を超えないかチェック。
   • 超える場合は新しいグループを作り、グループ数をカウント。
   • グループ数が \(K\) を超えたら False、すべて処理できれば True を返す。

4. 探索範囲を更新しながら最小の mid を求める。

計算量

• 時間計算量: \(O(N \log(\text{sum}(A)))\)
• 空間計算量: \(O(1)\) （入力を除く）

実装のポイント

• 二分探索の範囲に注意：left = max(A)、right = sum(A)

• can_split 内で、区間一つが max_len を超えていたら即座に False を返すこと（例外処理）

• 貪欲に区間をまとめる際に、現在の和とグループ数を正しく管理すること

  ソースコード

def can_split(A, K, max_len):
    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
            if count > K:
                return False
        else:
            current_sum += a
    return True

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:]))

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

if __name__ == "__main__":
    main()

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