概要

荷物列を順序を保ったままちょうど \(M\) 個の連続区間に分けたとき、「各区間和の最大値」の最小値 \(S\) が \(K\) を超えるか（\(S>K\)）を判定します。

考察

重要な気づき

「最大積載量を \(K\) 以下にできるか？」という判定問題に言い換えます。

• ある分け方で 各トラックの積載量（区間和）がすべて \(K\) 以下にできる
  \(\Rightarrow S \le K\)（答えは No）
• どんな分け方でも どこかのトラックが \(K\) を超える
  \(\Rightarrow S > K\)（答えは Yes）

さらに条件は「ちょうど \(M\) 台」ですが、\(A_i \ge 1\)（正の重さ）なので、

• \(K\) 以下で運べる分割が \(M\) 個以下で作れるなら、区間を途中で分割して個数を増やしても（連続性を保ったまま）各区間和は小さくなるだけなので、ちょうど \(M\) 個にもできる。

よって「ちょうど \(M\) 個」は次に置き換えられます：

\(K\) 以下で運べるために必要な最小トラック数が \(M\) 以下か？

素朴に全探索できない理由

分割位置は \(N-1\) 箇所から \(M-1\) 個選ぶため、組合せは \(\binom{N-1}{M-1}\) と爆発します。\(N \le 10^6\) では不可能です。

解決方針

「最大積載量を \(K\) 以下にする」ための 最小トラック数は、左から順にできるだけ詰める貪欲法で求まります。

• 今のトラックに次の荷物を載せても和が \(K\) 以下なら載せる
• 超えるなら新しいトラックを開始する

この方法は、各トラックを可能な限り重くするため、トラック数を最小にします。

また、もしある荷物が \(A_i > K\) なら、その荷物単体ですら \(K\) を超えるので即座に不可能（\(S > K\)）です。

アルゴリズム

1. 入力を読む。
2. もしどれかの荷物について \(A_i > K\) なら Yes を出力して終了。
3. cnt=1（使用トラック数）、s=0（現在のトラックの積載量）で開始。
4. 荷物を左から順に見ていき、
   • \(s + A_i \le K\) なら s += A_i
   • そうでなければ新しいトラックに切り替え、cnt += 1, s = A_i
5. 最終的に cnt <= M なら \(S \le K\) なので No、そうでなければ Yes。

例

\(A=[4,2,3,4]\), \(M=2\), \(K=6\) のとき： - 1台目: \(4+2=6\)（限界まで詰める） - 次の \(3\) は載らないので 2台目へ: \(3\) - 次の \(4\) は \(3+4=7\) で超えるので 3台目が必要
よって最小トラック数 cnt=3。\(3 > M(=2)\) なので Yes（\(S>K\)）。

計算量

• 時間計算量: \(O(N)\)（1回なめるだけ）
• 空間計算量: \(O(1)\)（配列を保持せず逐次処理可能）

実装のポイント

• \(N \le 10^6\) なので、Pythonでは高速入力が重要です。コードでは sys.stdin.buffer.read() から整数をパースして高速化しています。

• 和や \(K\) は最大で \(10^{15}\) 程度になり得るため、オーバーフローの心配がない Python の整数を使えば安全です。

• cnt <= M のとき「ちょうど \(M\) 台」にできることは、荷物の重さが正であるため区間分割で個数を増やしても最大和が増えない、という性質に依存します。

  ソースコード

import sys

def int_iter():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

it = int_iter()
N = next(it)
M = next(it)
K = next(it)

cnt = 1
s = 0

for _ in range(N):
    a = next(it)
    if a > K:
        print("Yes")
        sys.exit(0)
    if s + a <= K:
        s += a
    else:
        cnt += 1
        s = a

print("No" if cnt <= M else "Yes")

---

この解説は gpt-5.2-high によって生成されました。