概要

\(N\) 個の荷物を順番を変えずに \(M\) 台のトラックに積み分けるとき、すべてのトラックの積載量（重さの合計）を \(K\) 以下にできるかどうかを判定する問題です。

考察

「積載量の最大値を \(K\) 以下にできるか」ということは、「どのトラックも積載量を \(K\) 以下に抑えつつ、\(M\) 台以内のトラックで全ての荷物を運びきれるか」と言い換えることができます。

荷物の順番は変えられないため、先頭から順に「積載量が \(K\) を超えない範囲で、できるだけ多くの荷物を同じトラックに積む」という貪欲法（Greedy）が最適です。限界まで積むことで、後続の荷物を運ぶためのトラックの台数を最も節約できるからです。

素朴なアプローチとして、すべての分割方法を試す（深さ優先探索など）と、分割の仕方は組み合わせ爆発を起こすため、制約の \(N \le 10^6\) では確実にTLE（実行時間超過）になります。しかし、この貪欲法を用いれば、荷物を先頭から1回確認するだけで判定できるため、高速に解くことができます。

また、重要な例外として「1つの荷物だけで重さが \(K\) を超えてしまう」場合は、どのように分けても積載量が \(K\) を超えてしまうため、その時点で不可能と判断できます。

アルゴリズム

1. 必要なトラックの台数を表す変数 count を \(1\) に、現在のトラックの積載量 current_sum を \(0\) に初期化します。
2. 荷物の重さ \(A_i\) を先頭から順に確認します。
3. もし \(A_i > K\) であれば、その時点で不可能であることが確定するため、Yes を出力して処理を終了します。
4. current_sum + A_i > K となる場合、現在のトラックにはもう積めません。そのため、新しいトラックを用意し（count を \(1\) 増やす）、そのトラックの最初の荷物として current_sum = A_i とします。
5. 上記以外の場合、現在のトラックに荷物を積めるため、current_sum に \(A_i\) を加算します。
6. すべての荷物を確認し終えた後、使ったトラックの台数 count が \(M\) より多ければ Yes（不可能）、\(M\) 以下であれば No（可能）を出力します。

計算量

• 時間計算量: \(O(N)\) 各荷物に対して1回の判定と加算を行うだけで済むため、荷物の個数 \(N\) に比例した時間で処理が完了します。
• 空間計算量: \(O(N)\) 入力データを一括でリストとして保持するため、\(N\) に比例したメモリを使用します。

実装のポイント

• 出力の Yes / No に注意: 問題文の指示では「積載量の最大値が \(K\) を超えてしまう（不可能）」なら Yes、「\(K\) 以下にできる（可能）」なら No を出力します。可能・不可能の直感と逆になりやすいため、出力の対応を間違えないようにしましょう。

• 高速な入力: 入力サイズが最大 \(N = 10^6\) と非常に大きいため、Pythonの場合は input() をループで回すのではなく、sys.stdin.read().split() を用いて入力を一括で読み込むことで、I/Oによる実行時間超過（TLE）を防ぐことができます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    M = int(input_data[1])
    K = int(input_data[2])
    
    count = 1
    current_sum = 0
    
    for s in input_data[3:]:
        a = int(s)
        if a > K:
            print("Yes")
            return
        current_sum += a
        if current_sum > K:
            count += 1
            current_sum = a

    if count > M:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。