概要

各トラックは「重さが \(E_i\) 以下の荷物を最大 \(C_i\) 個載せられる」という条件なので、トラックを「重さ制限付きの枠（スロット）を \(C_i\) 個持つ箱」とみなし、荷物をできるだけ多く枠に割り当てる最大個数を求めます。

考察

重要な気づき

• 制約は「荷物 1 個ごとの重量 \(D_j \le E_i\)」だけで、合計重量の制約はないです。
• よってトラック \(i\) は「上限 \(E_i\) の枠を \(C_i\) 個提供する」と考えられます（枠同士は同じ制約）。
• すると問題は
  各荷物（重さ \(D_j\)）を、上限が \(D_j\) 以上の枠に 1 つずつ入れる
  という最大マッチング（ただし枠は同じ上限のものが複数ある）になります。

素朴な方法が厳しい理由

例えば各荷物について「入れられるトラックを探して空きがあるか確認」などを愚直にやると、 - 荷物 \(M\) 個それぞれにトラック \(N\) 個を見ると \(O(NM)\) で到底間に合いません（最大 \(4\times 10^{10}\)）。 - 優先度付きキューや multiset で管理しても、「どのトラックに入れるか」を都度選ぶ設計にすると実装が重くなりがちです。

どう解決するか（貪欲の方向性）

重い荷物ほど入れられる枠が限られます。
そこで 荷物を重い順に処理し、入れられる枠があれば即座に入れる のが自然です。

この順序が重要で、重い荷物を後回しにすると、軽い荷物が枠を先に使ってしまい、重い荷物が入らなくなる可能性があります。

さらにこの問題では、重い順に見ていけば - 「今の荷物 \(w\) を載せられる枠」は \(E_i \ge w\) の枠すべて - 次に出てくる荷物はそれ以下の重さなので、使い残した枠は将来も使える

つまり「どのトラックの枠を使ったか」の区別をする必要がなく、使える枠の総数 avail だけを持てば十分です。

アルゴリズム

1. トラックを \((E_i, C_i)\) のペアとして用意し、\(E_i\) の降順にソートする。
2. 荷物の重さ \(D_j\) も降順にソートする。
3. 荷物を重い順に 1 つずつ見ていく（重さを \(w\) とする）。
   • まだ処理していないトラックのうち、\(E_i \ge w\) を満たすものをすべて「使用可能」とし、その個数枠 \(C_i\) を avail に加える。
   • avail > 0 なら、この荷物はどれかの枠に入れられるので avail -= 1 して答えを 1 増やす。
4. 最後に数えた個数が最大配送数。

具体例： - トラック: \((E,C)=(10,1),(6,2)\)、荷物: \([9,6,6,5]\) - 荷物を重い順に処理
- 9：\(E\ge9\) の枠は 10 の1個 → avail=1 → 使って avail=0, ans=1
- 6：\(E\ge6\) の枠に 6 の2個追加 → avail=2 → 使って avail=1, ans=2
- 6：avail=1 → 使って avail=0, ans=3
- 5：追加枠なし、avail=0 → 入れられず ans=3

計算量

• 時間計算量: ソートにより \(O((N+M)\log(N+M))\)、走査は \(O(N+M)\)
• 空間計算量: 入力配列とソート用に \(O(N+M)\)

実装のポイント

• trucks と items をどちらも降順ソートし、トラック側はポインタ ti で「条件 \(E_i \ge w\) を満たす範囲」を前から順に一度だけ進めます（二重ループにならない）。

• avail は「今の荷物を載せられる枠の残数」なので、枠を 1 つ使うたびに avail -= 1 します。

• \(N,M \le 2\times10^5\) なので Python では入出力がボトルネックになり得ます。提示コードのように sys.stdin.buffer.read() で高速に整数を読み取ると安定します。

  ソースコード

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)

trucks = [(next(it), next(it)) for _ in range(N)]
items = [next(it) for _ in range(M)]

trucks.sort(key=lambda x: x[0], reverse=True)
items.sort(reverse=True)

avail = 0
ans = 0
ti = 0

for w in items:
    while ti < N and trucks[ti][0] >= w:
        avail += trucks[ti][1]
        ti += 1
    if avail > 0:
        avail -= 1
        ans += 1

sys.stdout.write(str(ans) + "\n")

---

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