概要

難易度の低い問題から順に候補を増やし、その中で配点が高い \(K\) 問の合計を管理します。この合計が初めて \(P\) 以上になったときの難易度が答えです。

考察

難易度の上限を決めると、配点の高い問題を選べばよい

選ぶ問題の難易度をすべて \(x\) 以下にするとします。この条件で配点の合計を最大にするには、難易度が \(x\) 以下の問題の中から、配点が高い順に \(K\) 問を選ぶのが最適です。

したがって、難易度の最大値を \(x\) 以下にできる条件は、次の \(2\) つです。

• 難易度が \(x\) 以下の問題が \(K\) 問以上ある。
• その中で配点が高い \(K\) 問の合計が \(P\) 以上である。

配点の高い \(K\) 問を選んでも合計が足りなければ、ほかの選び方でも条件を満たせません。

難易度の低い順に調べる

すべての \(K\) 問の組合せを調べる方法では、最大で \(\binom{N}{K}\) 通りを確認する必要があり、間に合いません。

そこで、問題を難易度の昇順に並べ、先頭から順に候補へ追加します。現在の問題の難易度を \(b\) とすると、それまでに追加した問題の難易度はすべて \(b\) 以下です。

ただし、追加のたびに候補全体を配点順に並べ直すのも非効率です。必要なのは配点が高い \(K\) 問だけなので、これらを最小ヒープで管理します。

最小ヒープで配点上位 \(K\) 問を維持する

最小ヒープは、格納した値の最小値を素早く取り出せるデータ構造です。

新しい配点を追加して要素数が \(K\) を超えたら、最小の配点を取り除きます。これにより、ヒープには常に「これまでに見た問題のうち、配点が高い最大 \(K\) 問」が残ります。

例えば \(K=2\) で、難易度順に配点 \(4,7,6\) が現れた場合、保持する配点は次のようになります。

• \(4\) を追加：\(\{4\}\)
• \(7\) を追加：\(\{4,7\}\)、合計 \(11\)
• \(6\) を追加し、最小の \(4\) を削除：\(\{6,7\}\)、合計 \(13\)

合計も追加・削除に合わせて更新すれば、毎回計算し直す必要はありません。

アルゴリズム

1. 各問題を \((B_i,A_i)\) の組として保存し、難易度の昇順にソートします。
2. 配点を管理する空の最小ヒープと、その要素の合計 sum を用意します。
3. ソートした問題を先頭から順に処理します。現在の難易度を \(b\)、配点を \(a\) として、次を行います。
   • ヒープに \(a\) を追加し、sum に \(a\) を加えます。
   • ヒープの要素数が \(K\) を超えたら、最小値を取り除き、sum からも引きます。
   • ヒープの要素数が \(K\) で、かつ sum が \(P\) 以上なら、\(b\) を出力して終了します。
4. 最後まで条件を満たさなければ、\(-1\) を出力します。

正しさの説明

ヒープには、処理済みの問題の配点上位 \(K\) 個が保持されます。

処理済みの問題が \(K\) 問以下なら、すべてを保持します。それ以降は、新しい配点を追加したうえで最小値を削除するため、配点上位 \(K\) 個が残ります。

よって、ヒープの要素数が \(K\) のとき、sum は処理済みの問題から \(K\) 問を選んで得られる合計の最大値です。

初めて条件を満たした時点の難易度を \(b\) とすると、ヒープ内の \(K\) 問を選べば、難易度をすべて \(b\) 以下にしつつ合計を \(P\) 以上にできます。

一方、\(b\) より難易度が低い問題はすべて先に処理されています。それらだけで条件を満たせるなら、もっと前に判定が成功していたはずです。したがって、\(b\) より小さい値は答えにならず、\(b\) が最小値です。

最後まで成功しなければ、全問題の配点上位 \(K\) 問でも合計が不足するため、答えは \(-1\) です。

計算量

• 時間計算量: \(O(N\log N)\)
  • ソートに \(O(N\log N)\)、ヒープ操作全体に \(O(N\log(K+1))\) かかります。
• 空間計算量: \(O(N)\)
  • 問題の保存に \(O(N)\)、ヒープに \(O(K)\) 使用します。

実装のポイント

• 合計には long long を使います。
  配点の合計は最大 \(10^5\times10^9=10^{14}\) となり、32 ビット整数には収まりません。\(P\) も long long で受け取ります。

• C++ の priority_queue は、標準では最大ヒープです。
  最小値を取り出すため、次のように greater<int> を指定します。

  priority_queue<int, vector<int>, greater<int>> scores;
  

• 合計だけでなく、要素数が \(K\) であることも確認します。
  合計が \(P\) 以上でも、まだ \(K\) 問そろっていなければ条件を満たしません。

• 同じ難易度の問題をまとめて処理する必要はありません。
  同じ難易度の途中で条件を満たしても、その難易度を答えにできます。途中では満たさなくても、残りを追加しながら判定を続ければよいです。

• コードでは \((B_i,A_i)\) の順に保存しています。入力順は \(A_i,B_i\) なので、読み込み順に注意してください。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

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

    int N, K;
    long long P;
    cin >> N >> K >> P;

    vector<pair<int, int>> problems(N);
    for (auto& [b, a] : problems) {
        cin >> a >> b;
    }
    sort(problems.begin(), problems.end());

    priority_queue<int, vector<int>, greater<int>> scores;
    long long sum = 0;

    for (const auto& [b, a] : problems) {
        scores.push(a);
        sum += a;

        if (static_cast<int>(scores.size()) > K) {
            sum -= scores.top();
            scores.pop();
        }

        if (static_cast<int>(scores.size()) == K && sum >= P) {
            cout << b << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return 0;
}

---

この解説は gpt-6-astra-medium によって生成されました。