概要

\(N\) 台のトラック（各トラックに重量上限と個数上限あり）に \(M\) 個の荷物をできるだけ多く割り当てる問題。トラックと荷物をソートし、貪欲法で最大個数を求める。

考察

重要な気づき

まず、全探索で全ての割り当てパターンを試すのは \(O(N^M)\) 程度になり、制約（\(N, M \leq 2 \times 10^5\)）では到底間に合いません。

ここで貪欲法を考えます。鍵となる観察は以下です：

• 軽い荷物ほど柔軟：重量が小さい荷物は、重量上限 \(E_i\) が小さいトラックにも大きいトラックにも載せられます。
• 重い荷物は制限が厳しい：重量が大きい荷物は、\(E_i\) が十分大きいトラックにしか載せられません。

貪欲の方針

トラックを重量上限 \(E_i\) が小さい順に処理します。各トラックを処理する時点で「載せられる荷物の候補」をプールに追加していきます。

プールからどの荷物を選ぶべきか？ 答えは「最も軽い荷物を優先的に使う」です。

理由：今のトラック（\(E_i\) が小さい）に載せられる荷物は、今後処理するトラック（\(E_i\) がより大きい）にも必ず載せられます。一方、まだプールに入っていない重い荷物は、\(E_i\) が大きい将来のトラックにしか載せられません。したがって、将来のトラックの積載枠を重い荷物のために残すため、今のトラックには軽い荷物を割り当てるのが最適です。

具体例

トラックA（\(E=5, C=2\)）、トラックB（\(E=10, C=1\)）、荷物の重量が \([3, 4, 8]\) の場合：

• トラックA処理時：プールに \(\{3, 4\}\) が入る → 軽い順に2個（\(3, 4\)）を割り当て
• トラックB処理時：プールに \(\{8\}\) が追加 → 1個（\(8\)）を割り当て
• 合計3個配送可能

もしトラックAで重い方を取ると、荷物8がトラックBの枠を奪い、合計が減る可能性があります。

アルゴリズム

1. トラックを \(E_i\) の昇順にソートする
2. 荷物を重量 \(D_j\) の昇順にソートする
3. ソート済み荷物を管理するポインタ pkg_idx を用意する
4. トラックを順に処理：
   • \(D_{pkg\_idx} \leq E_i\) を満たす荷物を全て「利用可能プール」に追加
   • プールから最も軽い \(\min(C_i, |プール|)\) 個を取り出し、配送個数に加算
5. 最終的な配送個数を出力

計算量

• 時間計算量: \(O((N + M) \log M)\)
  • ソート：\(O(N \log N + M \log M)\)
  • 各トラック処理時のプールへの追加：全体で \(O(M \log M)\)（SortedListへの挿入1回が \(O(\log M)\)）
  • プールからの削除：全体で \(O(M)\)（SortedListのスライス削除は削除個数に比例、全体で最大 \(M\) 個削除）
• 空間計算量: \(O(N + M)\)

実装のポイント

• SortedList の活用：Pythonの sortedcontainers.SortedList を使うと、要素の追加が \(O(\log M)\)、先頭からのスライス削除 del available[:take] が効率的に行える。

• ソート順の一致：トラックも荷物も昇順にソートすることで、ポインタを一方向に進めるだけで「載せられる荷物の候補追加」を実現できる（尺取り法的な発想）。

• 個数最大化に特化：荷物の重量の合計制約がないため、個々の荷物が載るかどうかだけを判定すればよく、ナップサック問題のような複雑さは不要。

  ソースコード

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    trucks = []
    for i in range(N):
        E = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        trucks.append((E, C))
    
    D = []
    for j in range(M):
        D.append(int(input_data[idx])); idx += 1
    
    # Greedy approach:
    # Sort trucks by E (weight limit) in ascending order.
    # Sort packages by weight in ascending order.
    # Process trucks in order of increasing E.
    # For each truck, all packages with D_j <= E_i become available.
    # Among available (unassigned) packages, we want to pick the C_i lightest ones
    # (greedy: use lightest packages for this truck, saving heavier ones for trucks with higher E).
    # Actually, we should pick the HEAVIEST available packages that fit, because
    # lighter packages are more flexible (can fit in more trucks).
    # Wait, let me reconsider...
    
    # Actually the optimal greedy: sort trucks by E ascending. For each truck,
    # among all available packages with D_j <= E_i, we should assign the HEAVIEST ones
    # to this truck. Because lighter packages can potentially fit in trucks with smaller E
    # that we haven't... wait, we process in ascending E order, so all future trucks have
    # E >= current E, meaning lighter packages will also fit in future trucks.
    # So we should assign the heaviest available packages (that fit) to the current truck,
    # keeping lighter ones for potentially being used by future trucks (which they'll fit in too).
    # But future trucks also accept heavier packages... 
    
    # Actually, the standard greedy for this type of problem:
    # Sort trucks by E ascending, sort packages by D ascending.
    # For each truck (ascending E), add all packages with D <= E to available pool.
    # Then greedily take the C_i smallest from the pool (to leave heavier for bigger trucks).
    # No wait... we want to maximize count, not minimize waste.
    
    # To maximize the number of packages delivered:
    # Sort trucks by E ascending. Sort packages by D ascending.
    # Maintain a pool of available packages. For each truck, add packages with D <= E.
    # From the pool, take up to C_i packages. Which ones? The lightest, because
    # heavier packages in the pool can only be used by trucks with E >= current E (future trucks),
    # so we should save them. Lighter packages can also be used by future trucks, but
    # by using them now we free up capacity for heavier packages later.
    # Actually since all packages in the pool fit in the current truck AND all future trucks,
    # it doesn't matter which we pick for count maximization... 
    # But packages added later (heavier) only fit in future trucks, not current.
    # So we should use the lightest ones now (they fit everywhere) to save capacity of 
    # future trucks for heavier packages that only fit there.
    # Yes: pick the lightest C_i from the pool.
    
    trucks.sort(key=lambda x: x[0])
    D.sort()
    
    # We need a data structure that supports:
    # - Adding elements
    # - Removing the smallest C_i elements efficiently
    # Use a SortedList and pop from the front
    
    available = SortedList()
    pkg_idx = 0
    total = 0
    
    for E, C in trucks:
        # Add all packages with D <= E
        while pkg_idx < M and D[pkg_idx] <= E:
            available.add(D[pkg_idx])
            pkg_idx += 1
        
        # Take up to C lightest packages
        take = min(C, len(available))
        if take > 0:
            total += take
            # Remove the smallest 'take' elements
            # SortedList supports slicing deletion
            del available[:take]
    
    print(total)

if __name__ == '__main__':
    main()

---

この解説は claude4.6opus-thinking によって生成されました。