概要

\(N\) 個の荷物を番号順（連続した区間）で \(K\) 台のトラックに分割し、各トラックの積載量の合計のうち「最小値」を最大化する問題です。

考察

「最小値の最大化」というキーワード

競技プログラミングにおいて、「最小値の最大化」や「最大値の最小化」を求める問題は、二分探索（Binary Search）と相性が非常に良いという特徴があります。

この問題で「最小値を \(X\) 以上にできるか？」という判定問題を考えてみましょう。もし \(X\) を大きくしすぎると条件を満たす分割ができなくなり、逆に \(X\) を小さくすれば容易に達成できます。このように結果が単調性（ある値を境に可能・不可能が切り替わる性質）を持つため、二分探索で最適な \(X\) を効率よく探すことができます。

判定問題：積載量の最小値を \(X\) 以上にできるか？

この判定は、端から順番に荷物を積んでいく貪欲法（Greedy Algorithm）で解くことができます。

1. 荷物を 1 番目から順に見ていき、現在のトラックの積載量の合計が \(X\) 以上になるまで荷物を追加し続けます。
2. 合計が \(X\) 以上になった瞬間、そのトラックの荷物を確定させ、次のトラックに移ります。
3. この手順を繰り返し、最終的に \(K\) 個以上の区間（トラック）が作れれば、最小値を \(X\) 以上にすることが「可能」と判断できます。

※ \(K\) 個以上の区間が作れた場合、余った荷物は最後のトラックにすべて含めてしまえば、そのトラックの積載量は \(X\) 以上を維持できるため、問題ありません。

アルゴリズム

1. 二分探索の範囲を設定する
   • 最小値の下限 low を \(1\)、上限 high を全荷物の重さの合計（\(\sum A_i\)）とします。
2. 二分探索を行う
   • 中央値 \(mid = (low + high) // 2\) を計算します。
   • 「すべてのトラックの積載量を \(mid\) 以上にできるか？」を貪欲法で判定します。
   • 可能な場合: もっと大きな値も達成できるかもしれないので、答えを \(mid\) に更新し、low = mid + 1 として探索を続けます。
   • 不可能な場合: \(mid\) が大きすぎるため、high = mid - 1 として探索範囲を下げます。
3. 最終的な答えを出力する
   • 探索が終わったときの ans が、達成可能な最大値となります。

計算量

• 時間計算量: \(O(N \log(\sum A_i))\)
  • 二分探索の反復回数は、荷物の重さの総和を \(S\) とすると \(O(\log S)\) です。
  • 各探索ステップでの判定（貪欲法）に \(O(N)\) かかります。
  • \(N=10^5, \sum A_i \approx 10^{14}\) 程度であれば、\(\log(\sum A_i)\) は \(50\) 弱であり、十分実行時間制限内に収まります。
• 空間計算量: \(O(N)\)
  • 荷物の重さを保持するリストのサイズに依存します。

実装のポイント

• 高速な入出力: Pythonの場合、荷物の個数 \(N\) が \(10^5\) と多いため、sys.stdin.read().split() を使って一括で読み込むと実行時間を短縮できます。

• 二分探索の境界: low と high の更新条件を間違えないように注意しましょう。

• 判定条件の早期終了: 貪欲法のループ内で、区間数が \(K\) に達した時点で True を返して終了することで、わずかに高速化できます。

  ソースコード

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストにする
    # 大量の入力データを高速に処理するための手法です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 荷物の個数, K: トラックの台数
    N = int(input_data[0])
    K = int(input_data[1])
    # A: 各荷物の重さのリスト
    A = list(map(int, input_data[2:]))
    
    # 二分探索の範囲を設定
    # 各トラックの積載量の最小値として達成可能な最大値を探索します
    # 最小値の下限は1（各荷物の重さが1以上のため）、上限は全ての荷物の重さの合計をKで割った値です
    low = 1
    high = sum(A) // K
    ans = 1
    
    # 二分探索のメインループ
    while low <= high:
        mid = (low + high) // 2
        
        # midが0の場合は、最小値を1として扱う（制約上ansは1以上になるため）
        if mid == 0:
            low = 1
            continue
        
        # 判定問題: 全てのトラックの積載量をmid以上にできるか？
        # 欲張り法を用いて、重さの合計がmid以上になるように荷物を区切っていき、
        # K個以上の区間が作れるかを確認します。
        count = 0
        current_sum = 0
        possible = False
        
        for weight in A:
            current_sum += weight
            if current_sum >= mid:
                count += 1
                current_sum = 0
                # すでにK個以上の区間が見つかった場合は、残りの荷物を最後のトラックに
                # 含めることができるため、このmidは達成可能と判断してループを抜けます。
                if count >= K:
                    possible = True
                    break
        
        if possible:
            # mid以上の積載量を確保できる場合、より大きな値を試みる
            ans = mid
            low = mid + 1
        else:
            # mid以上の積載量を確保できない場合、より小さな値を試みる
            high = mid - 1
            
    # 結果を出力
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。