概要

この問題は、与えられたトラックの積載制限（重量上限 \(E_i\)、個数上限 \(C_i\)）のもとで、最大で何個の荷物を配送できるかを求める最大マッチング問題です。

制約が \(N, M \leq 2 \times 10^5\) と大きいため、効率的な貪欲法（Greedy）と、荷物の使用状況を高速に管理するデータ構造（Union-Find）を組み合わせることで、制限時間内に正解を導きます。

---

考察

1. 貪欲法の割り当て戦略

どのように荷物とトラックをマッチングさせれば、配送数を最大化できるでしょうか？ 以下の2つの直感的なアプローチを組み合わせることで、最適な貪欲法が成り立ちます。

1. トラックの処理順序：重量上限 \(E_i\) が大きいトラックから優先して処理する 重量上限が小さいトラックは、軽い荷物しか運べず、選択肢が限られています。一方で、重量上限が大きいトラックは、重い荷物も軽い荷物も運ぶことができます。 したがって、選択肢の広い「重量上限が大きいトラック」から順に決定していくのが最適です。

2. 荷物の選択：そのトラックに積める荷物のうち、できるだけ重いものを優先して積む あるトラック \(i\)（重量上限 \(E_i\)）に荷物を積む際、条件を満たす（\(D_j \leq E_i\)）荷物の中でできるだけ重い荷物を優先して選びます。 なぜなら、軽い荷物をここで消費してしまうと、後続の「重量上限が小さいトラック」が積める荷物がなくなってしまうからです。重い荷物を大容量のトラックで引き受けることで、軽い荷物を制限の厳しいトラックのために温存できます。

2. ナイーブ（素朴）な実装とその限界

この貪欲法をそのまま実装することを考えます。 1. 荷物の重さの配列 \(D\) を昇順にソートする。 2. トラックを重量上限 \(E_i\) の降順にソートする。 3. 各トラックについて、二分探索で \(E_i\) 以下の最大の荷物を見つける。 4. そこから左（軽い方向）へ向かって、まだ使われていない荷物を \(C_i\) 個探索し、使用済みのマークをつける。

しかし、すでに使用された荷物をスキップしながら左へ探索する操作を愚直に行うと、最悪の場合（すべてのトラックが同じ荷物の範囲を走査する場合など）、1回の探索に \(O(M)\) かかってしまいます。 全体で \(O(NM)\) の計算量となり、最大 \(2 \times 10^5 \times 2 \times 10^5 = 4 \times 10^{10}\) 回の計算が必要になるため、実行時間制限（TLE）に引っかかります。

3. Union-Find による高速化

「すでに使用された要素をスキップして、次に利用可能な要素を高速に見つける」という問題は、Union-Find（素集合データ構造） を用いて高速化できます。

荷物のインデックスを \(1\) から \(M\) とします。 Union-Find の各要素 \(i\) の親（代表元）を、「インデックス \(i\) 以下の荷物のうち、まだ使用されていない最大のインデックス」 と定義します。初期状態では、すべての荷物が未使用なので、parent[i] = i です。

荷物 \(i\) を使用した（トラックに積んだ）とき、その荷物はもう使えなくなります。そこで、 parent[i] = find(i - 1) と更新（マージ）します。これにより、次回以降にインデックス \(i\)（またはそれ以降の既に使用されたインデックス）が参照された際、Union-Find の find 関数を呼び出すだけで、自動的に「左隣にある、まだ使用されていない最大のインデックス」へ一瞬でジャンプできるようになります。

---

アルゴリズム

1. 初期化とソート

   • 荷物の重量配列 \(D\) を昇順にソートします。
   • 実装の都合上（1-based indexing のため）、先頭にダミーの \(0\) を追加します。
   • トラックのリストを重量上限 \(E_i\) の降順にソートします。
   • サイズ \(M + 1\) の Union-Find を用意します。parent[i] = i と初期化します（ただし parent[0] = -1 とし、これ以上左に荷物がないことを示します）。

2. トラックの走査と貪欲な割り当て 各トラック \((E_i, C_i)\) について、以下の処理を行います。

   • 二分探索（bisect_right）を用いて、重量が \(E_i\) 以下となる最大の荷物のインデックス idx を求めます。
   • curr = find(idx) として、実際に使用可能な（まだ使われていない）最大の荷物のインデックスを取得します。
   • curr >= 1 かつ、このトラックの積載上限 \(C_i\) に達していない間、以下を繰り返します：
     1. 荷物 curr をこのトラックに割り当てる（答えのカウントを \(+1\) する）。
     2. 荷物 curr を使用済みにするため、parent[curr] = find(curr - 1) とマージする。
     3. 次の未使用の荷物へ移動する：curr = parent[curr]。
     4. このトラックに積んだ個数を \(+1\) する。

3. 出力

   • 最終的な配送数の合計を出力します。

---

計算量

• 時間計算量: \(O((N + M) \log (N + M))\)

  • 荷物のソートに \(O(M \log M)\)、トラックのソートに \(O(N \log N)\) かかります。
  • 各トラックについて、二分探索に \(O(\log M)\) かかります（全体で \(O(N \log M)\)）。
  • Union-Find の操作（find）は、経路圧縮を伴うため、ほぼ定数時間 \(O(\alpha(M))\) で動作します。各荷物は高々1回しか使用されないため、マージ操作の総回数は最大でも \(M\) 回です。
  • したがって、全体の時間計算量は \(O(N \log N + M \log M)\) となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N + M)\)

  • トラックの情報を格納する配列に \(O(N)\)、荷物の配列 \(D\) および Union-Find の parent 配列に \(O(M)\) のメモリを使用します。

---

実装のポイント

• ダミー要素の挿入 荷物配列 \(D\) の先頭に 0 を追加して 1-based indexing にしています。これにより、二分探索で条件を満たす荷物が存在しない場合に idx = 0 となり、Union-Find の find(0) が -1（使用不可）を返すため、境界値の例外処理をシンプルに記述できます。

• 経路圧縮（Path Compression） Union-Find の find 関数内で経路圧縮を行うことで、木の高さを低く保ち、探索クエリを \(O(\alpha(M))\) に抑えています。再帰によるコールスタックのオーバーヘッドを避けるため、ループを用いた非再帰（反復的）な実装がなされており、Python においても高速に動作します。

  ソースコード

import sys
from bisect import bisect_right

def solve():
    # 入力を一括で取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    ptr = 2
    trucks = []
    for _ in range(N):
        E = int(input_data[ptr])
        C = int(input_data[ptr+1])
        trucks.append((E, C))
        ptr += 2
        
    D = [int(x) for x in input_data[ptr : ptr + M]]
    D.sort()
    
    # 1-based indexing のためにダミーの 0 を先頭に追加
    D = [0] + D
    
    # トラックを重量上限 E の降順にソート
    trucks.sort(key=lambda x: x[0], reverse=True)
    
    # Union-Find の初期化
    # parent[i] は i 以下のインデックスで、まだ使用されていない最大の荷物のインデックスを指す
    parent = list(range(M + 1))
    parent[0] = -1
    
    def find(i):
        curr = i
        while curr >= 0 and parent[curr] != curr:
            curr = parent[curr]
        # 経路圧縮
        while i >= 0 and i != curr:
            nxt = parent[i]
            parent[i] = curr
            i = nxt
        return curr

    ans = 0
    for E, C in trucks:
        # E 以下の最大の荷物のインデックスを二分探索
        idx = bisect_right(D, E) - 1
        if idx <= 0:
            continue
        
        count = 0
        curr = find(idx)
        # トラックの容量 C に達するか、積める荷物がなくなるまで貪欲に割り当てる
        while curr >= 1 and count < C:
            ans += 1
            count += 1
            # 使用した荷物のインデックスを、その左隣の未使用のインデックスにマージする
            parent[curr] = find(curr - 1)
            curr = parent[curr]
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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