概要

\(N\) 問の中から配点の合計が \(P\) 以上となるように \(K\) 問を選ぶとき、選んだ問題の難易度（\(B_i\)）の最大値の最小値を求める問題です。配点の大きい問題を優先して選びつつ、難易度をどこまで許容すれば合計 \(P\) 点を達成できるかを効率的に判定する必要があります。

考察

愚直なアプローチとその問題点

\(N\) 問から \(K\) 問を選ぶ組み合わせは \(\binom{N}{K}\) 通りあり、\(N \le 10^5\) では全探索は不可能です。

重要な気づき

「難易度の最大値」を小さく抑えたいので、難易度が低い問題から優先的に使いたい という性質があります。 そこで、問題をあらかじめ難易度 \(B_i\) の昇順に並び替えてみましょう。

難易度が小さい順に問題を 1 つずつ見ていき、「今見ている問題の難易度を最大値として許容する」とします。このとき、これまでに見た問題の中から配点 \(A_i\) が大きい順に \(K\) 問を選べば、配点の合計を最大化できます。 難易度が低い順に調べているため、配点の合計が初めて \(P\) 以上になった瞬間の難易度が、求めるべき「難易度の最大値の最小値」となります。

配点上位 \(K\) 個の効率的な管理

問題を難易度順に 1 つずつ追加しながら、「これまでに見た問題の中で配点が大きい上位 \(K\) 個の合計」を高速に更新したいです。 これは、サイズを高々 \(K\) に保つ最小ヒープ（優先度付きキュー） を使うことで実現できます。

• 新しい問題の配点 \(A_i\) をヒープに追加し、合計値に加算する。
• ヒープの要素数が \(K\) を超えたら、ヒープ内の最小値を取り出して合計値から引く。

これにより、ヒープ内には常に「上位 \(K\) 個の配点」が保持され、それぞれの問題について \(O(\log K)\) で合計値を更新・確認できます。

アルゴリズム

1. 問題を難易度 \(B_i\) の昇順にソートする。
2. 最小ヒープ pq と、ヒープ内の要素の合計 sum を用意する。
3. ソートした問題を先頭から順に走査する：
   • 現在の問題の配点 \(A_i\) を pq に追加し、sum に \(A_i\) を足す。
   • pq のサイズが \(K\) を超えたら、最小の要素（pq.top()）を取り出し、sum から引く。
   • pq のサイズが \(K\) かつ sum >= P であれば、現在の問題の難易度 \(B_i\) を答えとして記録し、ループを終了する。
4. ループが終了しても条件を満たすものがなければ、達成不能として -1 を出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  • 問題のソートに \(O(N \log N)\) かかります。
  • 各問題について優先度付きキューへの挿入・削除を行うため、ループ全体で \(O(N \log K)\) かかります。
  • 全体として \(O(N \log N)\) となり、制約 \(N = 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 問題の配列の保持に \(O(N)\)、優先度付きキューに最大で \(O(K)\) のメモリを消費します。

実装のポイント

• オーバーフローへの注意: 配点の合計値 \(P\) や選んだ配点の和 sum は最大で \(10^{14}\) に達するため、32-bit 整数型ではオーバーフローします。C++ の場合は long long 型を使用してください。

• 最小ヒープの利用: C++ の std::priority_queue はデフォルトで最大値を取り出す「最大ヒープ」のため、std::greater を指定して「最小ヒープ」として宣言します。これにより、サイズが \(K\) を超えたときに最も配点の小さい不要な問題を \(O(\log K)\) で捨てることができます。

  ソースコード

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    long long p;
    if (!(cin >> n >> k >> p)) return 0;

    struct Problem {
        long long a;
        long long b;
    };

    vector<Problem> probs(n);
    for (int i = 0; i < n; ++i) {
        cin >> probs[i].a >> probs[i].b;
    }

    sort(probs.begin(), probs.end(), [](const Problem& x, const Problem& y) {
        return x.b < y.b;
    });

    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long sum = 0;
    long long ans = -1;

    for (int i = 0; i < n; ++i) {
        pq.push(probs[i].a);
        sum += probs[i].a;
        if ((int)pq.size() > k) {
            sum -= pq.top();
            pq.pop();
        }
        if ((int)pq.size() == k && sum >= p) {
            ans = probs[i].b;
            break;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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