概要

\(N\) 個の荷物を \(K\) 台のトラックに連続した区間として分割し、各トラックの積載量の最小値を最大化する問題です。「最小値の最大化」は二分探索で解くのが定石です。

考察

重要な気づき

この問題は「最小値を最大化せよ」という形式です。このような問題では、答えを仮定して判定問題に帰着させるアプローチが有効です。

具体的には、「全てのトラックの積載量を \(X\) 以上にできるか？」という判定問題を考えます。この判定ができれば、\(X\) を二分探索することで答えが求まります。

判定問題の考え方

「各トラックの積載量を \(X\) 以上にできるか」を判定するには、貪欲法が使えます。

1. 荷物を先頭から順に現在のトラックに積んでいく
2. 積載量が \(X\) 以上になったら、そのトラックは条件を満たしたので次のトラックへ移る
3. 最終的に条件を満たすトラックが \(K\) 台以上作れれば OK

具体例

例えば \(A = [3, 2, 4, 1, 5]\)、\(K = 3\) で、\(X = 5\) を達成できるか考えます。

• トラック1: \(3 + 2 = 5 \geq 5\) → OK、次へ
• トラック2: \(4 + 1 = 5 \geq 5\) → OK、次へ
  
• トラック3: \(5 \geq 5\) → OK

3台で分割でき、各トラックが5以上なので達成可能です。

二分探索の範囲

• 下限: \(0\)（最小値は0以上）
• 上限: \(\lfloor \text{総和} / K \rfloor\)（これより大きいと \(K\) 台で分けられない）

アルゴリズム

1. 二分探索の初期化: \(\text{left} = 0\)、\(\text{right} = \lfloor \text{総和} / K \rfloor + 1\)
2. 二分探索のループ:
   • \(\text{mid} = (\text{left} + \text{right}) / 2\) を計算
   • 「各トラックの積載量を \(\text{mid}\) 以上にできるか」を判定
   • 可能なら \(\text{left} = \text{mid}\)（もっと大きい値も試せる）
   • 不可能なら \(\text{right} = \text{mid}\)（この値は達成できない）
3. 判定関数 can_achieve_min_load:
   • 荷物を先頭から貪欲に積んでいく
   • 積載量が \(\text{min\_load}\) 以上になったらセグメント（区間）を1つ確定
   • 確定したセグメント数が \(K\) 以上なら True

判定の流れ（min_load = 5 の場合）:
荷物: [3, 2, 4, 1, 5]
      ↓
[3,2] → 合計5 ≥ 5 → 区間1確定
[4,1] → 合計5 ≥ 5 → 区間2確定  
[5]   → 合計5 ≥ 5 → 区間3確定
→ 3区間作れたので K=3 に対して OK

計算量

• 時間計算量: \(O(N \log(\text{sum}/K))\)
  • 二分探索が \(O(\log(\text{sum}/K))\) 回
  • 各判定で配列を1回走査するので \(O(N)\)
• 空間計算量: \(O(N)\)
  • 入力配列の保持に必要

実装のポイント

• 判定関数では「\(K\) 台のトラック全てが \(X\) 以上」ではなく「\(X\) 以上の区間を \(K\) 個作れるか」で判定します。最後の区間に余りが出ても、それは前の区間に含めることで対応できます。

• 二分探索では「条件を満たす最大値」を求めるため、条件を満たすとき \(\text{left}\) を更新し、最終的に \(\text{left}\) を答えとします。

  ソースコード

def can_achieve_min_load(A, K, min_load):
    """
    各トラックの積載量が少なくともmin_load以上となるように
    K台以下のトラックで配達できるかを判定する
    """
    truck_count = 1
    current_load = 0
    
    for weight in A:
        current_load += weight
        # 現在のトラックの積載量がmin_load以上になったら次のトラックへ
        if current_load >= min_load:
            truck_count += 1
            current_load = 0
    
    # 最後のトラックがmin_load未満でも、それ以前でK台使い切っていればOK
    # truck_countは「次のトラック」としてカウントしているので、実際に使ったトラック数はtruck_count-1
    # ただし、current_load > 0 の場合は最後のトラックも使っている
    
    # 別のアプローチ：K台で分割できるか
    # min_load以上の区間をK個作れるか
    segments = 0
    current_load = 0
    
    for weight in A:
        current_load += weight
        if current_load >= min_load:
            segments += 1
            current_load = 0
    
    return segments >= K


def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    total_sum = sum(A)
    
    # 二分探索
    # left: 達成可能な最小値の下限
    # right: 達成可能な最小値の上限
    left = 0
    right = total_sum // K + 1
    
    while right - left > 1:
        mid = (left + right) // 2
        if can_achieve_min_load(A, K, mid):
            left = mid
        else:
            right = mid
    
    print(left)


solve()

---

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