概要

\(N\) 個の荷物を連続する区間として \(M\) 台のトラックに分けるとき、各トラックの積載量（区間の合計）の最大値を最小化した値 \(S\) が \(K\) より大きいかを判定する問題です。これは「最大値を \(K\) 以下にできるか？」という判定問題に帰着でき、貪欲法で効率的に解けます。

考察

問題の言い換え

\(S > K\) かどうかを聞かれていますが、これは次の問いと同値です：

「すべてのトラックの積載量を \(K\) 以下に抑えつつ、\(M\) 台以内のトラックで全荷物を運べるか？」

• 運べるなら \(S \leq K\)（No）
• 運べないなら \(S > K\)（Yes）

素朴なアプローチの問題点

すべての分け方を列挙しようとすると、分割点の選び方は \(\binom{N-1}{M-1}\) 通りあり、\(N\) が \(10^6\) のとき到底間に合いません。

重要な気づき：貪欲法が最適

「最大積載量を \(K\) 以下にしたい」という制約のもとでは、各トラックにできるだけ多くの荷物を詰め込む貪欲法が最適です。

具体的には、先頭から順に荷物を見ていき、現在のトラックに追加しても合計が \(K\) を超えないなら追加し、超えるなら新しいトラックを使います。この方法で使うトラック数が最小になります。

なぜ貪欲が最適か？ 前のトラックに余裕を残して次のトラックに荷物を回しても、使うトラック数が減ることはありません。前のトラックに詰められるだけ詰めた方が、後ろのトラックにとって有利になります。

アルゴリズム

1. 変数 current_sum（現在のトラックの積載量）を \(0\)、trucks_needed（必要なトラック数）を \(1\) で初期化する。
2. 荷物を \(A_1, A_2, \ldots, A_N\) の順に走査する：
   • もし \(A_i > K\) なら、1個の荷物だけで \(K\) を超えるので、どう分けても不可能 → Yes を出力して終了。
   • もし current_sum \(+ A_i > K\) なら、新しいトラックを使う：trucks_needed を \(1\) 増やし、current_sum \(= A_i\) にする。
   • そうでなければ、current_sum に \(A_i\) を加算する。
3. 走査終了後、trucks_needed \(\leq M\) なら \(K\) 以下に収まる分け方が存在するので No、そうでなければ Yes を出力する。

具体例

\(N=5, M=3, K=6, A=[3, 2, 4, 1, 2]\) の場合：

荷物	current_sum	判定	trucks_needed
\(3\)	\(3\)	\(0+3 \leq 6\) → 追加	\(1\)
\(2\)	\(5\)	\(3+2 \leq 6\) → 追加	\(1\)
\(4\)	\(4\)	\(5+4 > 6\) → 新トラック	\(2\)
\(1\)	\(5\)	\(4+1 \leq 6\) → 追加	\(2\)
\(2\)	\(7\)	\(5+2 > 6\) → 新トラック	\(3\)

\(3 \leq 3\) なので No（分け方：\([3,2],[4,1],[2]\)、最大積載量 \(5 \leq 6\)）。

計算量

• 時間計算量: \(O(N)\)（荷物を一度走査するだけ）
• 空間計算量: \(O(N)\)（配列 \(A\) の格納）

実装のポイント

• 単独の荷物が \(K\) を超える場合の処理: \(A_i > K\) の荷物が1つでもあれば、その荷物を含むトラックは必ず \(K\) を超えるため、即座に Yes を返す。この判定を忘れると誤答になる。

• \(K\) の値が最大 \(10^{15}\) と大きいため、Python では問題ないが、C++ などでは long long を使う必要がある。

• この問題は「二分探索 + 貪欲判定」で \(S\) そのものを求める典型問題の判定部分だけを切り出した形になっており、二分探索パートの理解への足がかりとなる良問です。

  ソースコード

def solve():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Check if we can split into M groups with max sum <= K
    # Greedy: pack as many items as possible into each truck without exceeding K
    current_sum = 0
    trucks_needed = 1
    for a in A:
        if a > K:
            print("Yes")
            return
        if current_sum + a > K:
            trucks_needed += 1
            current_sum = a
        else:
            current_sum += a
    
    if trucks_needed <= M:
        print("No")
    else:
        print("Yes")

solve()

---

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