概要

この問題は、与えられた \(N\) 台のトラックに、できるだけ多くの荷物を割り当てる最大マッチング問題です。トラックの重量上限と個数制限、および荷物の重量という制約のもとで、配送できる荷物の最大個数を求めます。

---

考察

重要な気づき

この問題は、貪欲法（Greedy Algorithm）を用いて最適解を求めることができます。

直感的に、「制限の厳しいトラック」から優先的に、「制限を満たす中で最も軽い（＝後のトラックに残しても価値が低い）荷物」を割り当てていくのが最適です。

具体的には、以下の性質に着目します。 1. トラックの重量上限 \(E_i\) が小さいものほど、積める荷物の選択肢が狭いため、優先的に処理すべきです。 2. 荷物の重量 \(D_j\) が小さいものほど、多くのトラックに積める汎用性があるため、できるだけ温存し、重い荷物（汎用性が低いもの）を優先して消費したいところです。しかし、重量制限の厳しいトラックには軽い荷物しか積めません。

したがって、以下の手順で割り当てを行うことで、全体として最大の個数を配送できます。 - トラックを重量上限 \(E_i\) の昇順にソートする。 - 荷物を重量 \(D_j\) の昇順にソートする。 - 重量上限が小さいトラックから順に、「そのトラックに積載可能（重量が \(E_i\) 以下）な、まだ使われていない最も軽い荷物」を、積載容量 \(C_i\) の限界まで割り当てる。

なぜこの貪欲法が正しいのか？

トラック \(i\) に積載可能な荷物の集合を考えます。 トラック \(i\) よりも後に処理されるトラック \(i'\) は、重量上限が \(E_{i'} \geq E_i\) を満たします。 これは、トラック \(i\) に積載可能な荷物は、すべて後のトラック \(i'\) にも積載可能であることを意味します。

したがって、トラック \(i\) にどの荷物を割り当てても、後のトラックが利用できる「荷物の個数」に与える影響は同じです。それならば、まだ割り当てていない荷物のうち、最も軽い方から \(C_i\) 個を割り当てて消費してしまっても、後のトラックの選択肢を不利にすることはありません。

---

アルゴリズム

ソートされたトラックと荷物に対して、2ポインタ（尺取り法）を用いて効率的に割り当てを行います。

1. ソート:

   • トラックを重量上限 \(E_i\) の昇順にソートします。
   • 荷物を重量 \(D_j\) の昇順にソートします。

2. ポインタの準備:

   • \(L\): まだどのトラックにも割り当てられていない、最も軽い荷物のインデックス（初期値 \(0\)）。
   • \(R\): 現在のトラック \(i\) の重量上限 \(E_i\) 以下である荷物の右端の境界（初期値 \(0\)）。

3. シミュレーション: 各トラック \(i\)（\(0\) から \(N-1\)）について、以下を行います。

   • \(D[R] \leq E_i\) を満たす限り、ポインタ \(R\) を進めます。
   • この時点で、トラック \(i\) に積載可能な「未割り当ての荷物」は、インデックスが \([L, R - 1]\) の範囲にある荷物です。その個数は \(R - L\) 個です。
   • トラック \(i\) に実際に積む個数 \(k\) は、トラックの容量制限 \(C_i\) と、利用可能な荷物の個数の最小値になります。 $\(k = \min(C_i, R - L)\)$
   • 答え（配送できる荷物の総数）に \(k\) を加算します。
   • 軽い方から \(k\) 個の荷物が消費されたため、ポインタ \(L\) を \(k\) だけ進めます（\(L \leftarrow L + k\)）。

---

計算量

時間計算量

• ソート:
  • トラックのソート: \(O(N \log N)\)
  • 荷物のソート: \(O(M \log M)\)
• 2ポインタによる走査:
  • 各トラックに対する処理の中で、ポインタ \(R\) は全体を通して最大 \(M\) 回しか右に進みません。
  • ポインタ \(L\) も同様に全体を通して最大 \(M\) 回しか進みません。
  • したがって、走査部分は \(O(N + M)\) 時間で動作します。

全体の時間計算量は \(O(N \log N + M \log M)\) となり、制約の \(N, M \leq 2 \times 10^5\) に対して十分高速に動作します。

空間計算量

• トラックの情報を格納する配列に \(O(N)\)、荷物の重量を格納する配列に \(O(M)\) のメモリを使用します。

全体の空間計算量は \(O(N + M)\) です。

---

実装のポイント

• ポインタ \(R\) の単調増加性: トラックが重量上限 \(E_i\) の昇順にソートされているため、トラック \(i\) で \(D[R] \leq E_i\) を満たした \(R\) は、次のトラック \(i+1\) に対しても必ず \(D[R] \leq E_{i+1}\) を満たします。そのため、トラックごとに \(R\) を \(0\) からやり直す必要はなく、前回の位置からそのまま進めることができます。これにより全体の計算量が \(O(NM)\) から \(O(N+M)\) へと劇的に改善されます。

• オーバーフローの防止: 積載可能な荷物の個数上限 \(C_i\) や、最終的な答え ans は、値が大きくなる可能性があるため、C++では long long 型を使用してオーバーフローを防いでいます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Truck {
    long long E;
    long long C;
    bool operator<(const Truck& other) const {
        return E < other.E;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<Truck> trucks(N);
    for (int i = 0; i < N; ++i) {
        cin >> trucks[i].E >> trucks[i].C;
    }

    vector<long long> D(M);
    for (int i = 0; i < M; ++i) {
        cin >> D[i];
    }

    sort(trucks.begin(), trucks.end());
    sort(D.begin(), D.end());

    long long ans = 0;
    int L = 0;
    int R = 0;
    for (int i = 0; i < N; ++i) {
        while (R < M && D[R] <= trucks[i].E) {
            R++;
        }
        int available = R - L;
        long long k = min(trucks[i].C, (long long)available);
        ans += k;
        L += k;
    }

    cout << ans << "\n";

    return 0;
}

---

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