概要

おいしさと高さが異なる \(N\) 個の果物と、使える高さが制限された \(M\) 回の収穫チャンス（脚立）があります。各脚立は1回しか使えず、その高さ以下の位置にある果物を1つ収穫できます。このとき、収穫できる果物のおいしさの合計を最大化する問題です。

---

考察

この問題は、「どのおいしい果物を、どの脚立を使って回収するか」を最適に決める問題です。価値を最大化したいので、貪欲法（Greedy）の適用を考えます。

1. どの果物から優先して決めるべきか？

得られるおいしさの合計を最大化したいので、当然「おいしさ（\(V_i\)）が大きい果物」から優先的に確保したいです。したがって、果物をおいしさの降順（大きい順）に並べ替えて、上から順に収穫できるか判定していくのが自然です。

2. 条件を満たす脚立が複数あるとき、どれを使うべきか？

ある果物（高さ \(D_i\)）を収穫することを考えます。この果物を収穫するために使える脚立は、高さが \(D_i\) 以上（\(L_j \geq D_i\)）のものすべてです。 もし候補となる脚立が複数ある場合、「条件を満たす脚立のうち、最も高さが低い（\(D_i\) に最も近い）もの」を使うのが最適になります。

なぜなら、必要以上に高い脚立をここで使ってしまうと、後から出てくる「もっと高い位置にある（しかしおいしい）果物」を収穫するための貴重な高い脚立が失われてしまうからです。低い脚立を優先して消費することで、高い脚立を未来のために温存することができます。

3. 高速に処理するためのデータ構造

「ある値 \(D_i\) 以上の最小の要素を検索し、それを削除する」という操作を高速に行う必要があります。 配列やリストを使うと、検索や削除に \(O(M)\) の時間がかかってしまい、全体で \(O(N \times M)\) となり実行時間制限に間に合いません（TLE）。

そこで、要素の追加・二分探索・削除をすべて \(O(\log M)\) で行える平衡二分探索木（C++の std::multiset）を使用します。

---

アルゴリズム

1. 果物の情報を、おいしさ \(V_i\) の降順にソートします。
2. 脚立の高さ \(L_j\) をすべて std::multiset に追加します。
3. おいしい果物から順に、以下の処理を行います。
   • multiset の中から、果物の高さ \(D_i\) 以上となる最小の脚立を二分探索（lower_bound）で探します。
   • 条件を満たす脚立が見つかった場合：
     • その果物を収穫することにし、おいしさ \(V_i\) を合計に加算します。
     • 使用した脚立を multiset から削除します。
   • 見つからなかった場合：
     • その果物は諦めて次の果物に進みます。
4. 最終的なおいしさの合計を出力します。

---

計算量

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

  • 果物のソートに \(O(N \log N)\) かかります。
  • \(M\) 個の脚立を multiset に挿入するのに \(O(M \log M)\) かかります。
  • 各果物について、multiset での二分探索と削除（最大 \(M\) 回）を行うのに、1回あたり \(O(\log M)\) かかるため、全体で \(O(N \log M)\) です。
  • 制約 \(N, M \leq 2 \times 10^5\) において、全体の計算量は約 \(10^7\) 回の演算となり、実行時間制限に余裕で間に合います。

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

  • 果物の情報を格納する配列に \(O(N)\)、脚立の情報を管理する multiset に \(O(M)\) のメモリを使用します。

---

実装のポイント

• std::multiset の検索方法: multiset で二分探索を行う際は、必ずメンバー関数である L.lower_bound(val) を使用してください。汎用関数である std::lower_bound(L.begin(), L.end(), val) を使用すると、イテレータの性質上 \(O(M)\) の時間がかかってしまい TLE になります。

• 重複要素の削除: multiset から要素を削除する際、L.erase(val) のように値を直接指定すると、その値を持つすべての要素が削除されてしまいます。今回は使った脚立を「1つだけ」削除したいため、必ず L.erase(it) のように検索で見つかったイテレータを渡して削除するようにします。

  ソースコード

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

using namespace std;

struct Fruit {
    long long d;
    long long v;
    // おいしさの降順でソートするための比較演算子
    bool operator<(const Fruit& other) const {
        return v > other.v;
    }
};

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<Fruit> fruits(n);
    for (int i = 0; i < n; ++i) {
        cin >> fruits[i].d >> fruits[i].v;
    }

    multiset<long long> L;
    for (int j = 0; j < m; ++j) {
        long long l;
        cin >> l;
        L.insert(l);
    }

    // おいしさの降順にソート
    sort(fruits.begin(), fruits.end());

    long long total_v = 0;
    for (const auto& fruit : fruits) {
        // 高さ fruit.d 以上の脚立のうち、最も高さが低いものを選択する
        auto it = L.lower_bound(fruit.d);
        if (it != L.end()) {
            total_v += fruit.v;
            L.erase(it); // 使用した脚立を削除
        }
    }

    cout << total_v << "\n";

    return 0;
}

---

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