概要

\(N\) 個の荷物を番号順に \(M\) 台のトラックに分割し、各トラックの積載量の最大値を最小にする問題。その最小値が与えられた値 \(K\) より大きいかどうかを判定する。

考察

この問題は「最大値の最小化」を求める典型的な二分探索の応用問題ですが、今回はその最小値が \(K\) を超えるかどうかだけを判定すればよいです。

重要な観察は、荷物を番号順に連続して分割しなければならないという制約です。つまり、途中で飛ばしたり逆順にすることはできません。この制約により、単純に重い荷物を分散させるといった貪欲法は使えません。

素朴なアプローチとして、ありうるすべての分割方法を試すことを考えると、これは組み合わせ的に非常に多い（\(\binom{N-1}{M-1}\) 通り）ため、現実的ではありません（TLE）。しかし、「ある上限値 \(K\) 以下で荷物を割り振れるか？」という判定問題であれば、前から順にシミュレーションすることが可能です。

具体的には、左から順に荷物を見て、現在のトラックに入れられたら入れ、入れられないなら次のトラックに回す、という貪欲な戦略が最適になります。なぜなら、後ろの荷物を先に詰め込むことで得になることはなく、順番に処理するのが最良だからです。

この判定を関数 can_deliver_within_capacity として実装しています。この関数は、各荷物を順に見ていきながらトラック数が \(M\) を超えないかを確認し、また各荷物の重さが \(K\) を超えていないかも同時にチェックします（\(K\) 以下にできないケースに対応）。

最後に、判定結果によって "No" または "Yes" を出力すれば答えとなります。

アルゴリズム

1. 各荷物を順番に見ていく。
2. 現在のトラックにその荷物を載せられるかを判定：
   • 載せられない場合 → 次のトラックに切り替える。
   • トラック数が \(M\) を超えた時点で不可能と判断。
3. 全ての荷物を割り振ることができた場合 → \(S \leq K\)（No を出力）
4. 割り振れなかった場合 → \(S > K\)（Yes を出力）

この貪欲法による判定は、分割後の各トラックの積載量が \(K\) 以下になるようにシミュレートするものです。

計算量

• 時間計算量: \(O(N)\)
  （各荷物に対して定数時間の操作を行うため）
• 空間計算量: \(O(1)\)
  （入力データを除けば、追加の大きなメモリを使用しない）

実装のポイント

• 各荷物の重さが \(K\) を超えていたら、その時点で False を返すこと（\(K\) 以下の分割がそもそも不可能）。

• トラック数が \(M\) を超えたら直ちに False を返す。

• 最後のトラックに全ての荷物を入れ終えたら True を返す。

  ソースコード

def can_deliver_within_capacity(A, M, K):
    trucks_needed = 1
    current_load = 0
    
    for weight in A:
        if weight > K:
            return False
        if current_load + weight > K:
            trucks_needed += 1
            current_load = weight
            if trucks_needed > M:
                return False
        else:
            current_load += weight
            
    return True

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

if can_deliver_within_capacity(A, M, K):
    print("No")
else:
    print("Yes")

この解説は qwen3-coder-480b によって生成されました。