この問題は答えを二分探索することで解くことができます。

以下では、入力で与えられた \(K\) から \(1\) を引き、切る回数を \(K\) とします。

まずは次の判定問題を考えます。

問題1： \(K\) か所を選んで切断することで、長さの最大値を \(X\) 以下にできるか判定せよ。

この問題は次の問題と同値です。

問題2： 長さの最大値が \(X\) 以下になるように切断するとき、切断回数を \(K\) 回以下にできるか判定せよ。

少ない回数の切断で長さの最大値を \(X\) 以下にするためには「丸太を端から見て \(X\) を超える直前の箇所で切る」を繰り返すのが最適です。

よって、この判定問題は \(O(N)\) で解けることがわかりました。

元の問題は答えを二分探索することで、この判定問題に帰着できます。よって、\(O(N\log \sum A_i)\) で解くことができます。

判定問題を解く際、実装によっては \(X < \max A_i\) のケースに注意してください。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  k--;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  auto solve=[&](long long m){
    int cut = 0;
    long long crr = 0;
    for(int i=0; i<n; i++){
      if(crr + a[i] > m){
        cut++;
        crr = 0;
      }
      crr += a[i];
    }
    return cut <= k;
  };

  long long ng = *max_element(a.begin(), a.end()) - 1;
  long long ok = 1e15;
  while(ok - ng > 1){
    long long m = (ok + ng) / 2;
    if(solve(m)){
      ok = m;
    }else{
      ng = m;
    }
  }

  cout << ok << endl;
}

実装例 (Python)

N, K = map(int, input().split())
A = list(map(int, input().split()))
K -= 1

def solve(m):
  cut = 0
  crr = 0
  for a in A:
    if crr + a > m:
      cut += 1
      crr = 0
    crr += a
  return cut <= K

ng = max(A) - 1
ok = 10**15
while ok - ng > 1:
  m = (ok + ng) // 2
  if solve(m):
    ok = m
  else:
    ng = m

print(ok)