概要

丸太を\(K\)箇所で切断して\(K+1\)個の断片に分割するとき、断片の長さの最大値\(M\)を最小化する問題です。

考察

問題を直接解こうとすると、\(N-1\)箇所から\(K\)箇所を選ぶ組み合わせを考える必要があり、計算量が非常に大きくなります。そこで、二分探索を用いて「最大値\(M\)を\(X\)以下にできるか」という判定問題に変換します。\(X\)が大きすぎると切断回数が少なくて済み、\(X\)が小さすぎると多くの切断が必要になります。この性質を利用して、条件を満たす最小の\(X\)を二分探索で見つけます。

アルゴリズム

1. 二分探索の範囲を設定します。左端\(left\)は最大の部品の長さ（1つの部品は分割できないため）、右端\(right\)はすべての部品の長さの合計とします。
2. 各ステップで\(mid = (left + right) // 2\)を計算し、最大断片長を\(mid\)以下にできるか判定します。
3. 判定方法：左から順に部品を加算していき、合計が\(mid\)を超えた時点で切断し、切断回数をカウントします。最終的な切断回数が\(K\)以下（断片数が\(K+1\)以下）なら、\(mid\)は達成可能です。
4. 達成可能なら\(right = mid\)、不可能なら\(left = mid + 1\)として探索範囲を狭め、\(left = right\)になるまで繰り返します。

計算量

• 時間計算量: \(O(N \log(\sum A_i))\)
  • 二分探索の反復回数は\(O(\log(\sum A_i))\)回
  • 各判定は\(O(N)\)で行う
• 空間計算量: \(O(N)\)
  • 入力配列を保存するため

実装のポイント

• 入力読み込みはsys.stdin.readで一括読み込みし、高速化しています。

• 二分探索の終了条件はleft < rightで、最終的にleftが答えになります。

• 判定時に注意する点：最後の断片もカウントするため、ループ後にcount += 1が必要です。

• 切断回数と断片数の関係：\(K\)回切断すると\(K+1\)個の断片ができるため、判定条件はcount <= k + 1となります。

  ソースコード

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:2+n]))
    
    left = max(A)
    right = sum(A)
    
    while left < right:
        mid = (left + right) // 2
        count = 0
        current = 0
        for a in A:
            if current + a > mid:
                count += 1
                current = a
            else:
                current += a
        count += 1
        
        if count <= k + 1:
            right = mid
        else:
            left = mid + 1
            
    print(left)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。