概要

\(N\) 個の問題から \(K\) 問を選び、配点の合計を \(P\) 以上にしつつ、難易度の最大値を最小化する問題です。「難易度でソートして、先頭から順に候補を増やしながら配点上位 \(K\) 個の和を管理する」ことで解けます。

考察

気づき1：答えを固定して考える

「難易度の最大値の最小値」を求める問題は、答えを \(X\) に固定して判定問題に変換するのが定石です。

「難易度の最大値が \(X\) 以下になるように \(K\) 問選んで、配点合計 \(P\) 以上にできるか？」

この判定は簡単です。使える問題は \(B_i \le X\) を満たすものだけなので、その中から配点 \(A_i\) が大きい順に \(K\) 個取ればよく、その合計が \(P\) 以上かどうかを見れば十分です（合計を最大化したいので貪欲に大きい方から取るのが最適）。もちろん、\(B_i \le X\) を満たす問題が \(K\) 個未満なら不可能です。

気づき2：単調性がある

\(X\) を大きくすると使える問題は増えるだけなので、「\(X\) で達成可能」なら「\(X' > X\) でも達成可能」です。つまり判定結果は \(X\) に関して単調で、二分探索が使えます。

ただし、\(X\) の候補は実質 \(B_i\) の値のみなので、\(B\) でソートしてから「先頭 \(i\) 個までを使える」という形で \(i\) を動かすと考えれば、二分探索を書かずに一度の走査で済みます。こちらの方が実装が楽です。

素朴な方法の問題点

各 \(i\) について「先頭 \(i\) 個の中の \(A\) の上位 \(K\) 個の和」を毎回ソートして求めると、\(O(N K \log N)\) や \(O(N^2 \log N)\) になって \(N = 10^5\) では間に合いません。

そこで、\(i\) を \(1\) ずつ増やすとき、上位 \(K\) 個の集合はほとんど変化しないことを使います。新しい要素 \(A_i\) が入るかどうかは「今持っている \(K\) 個の中の最小値」と比べればわかります。これは 最小値を取り出せる優先度付きキュー（min-heap） でちょうど管理できます。

アルゴリズム

1. 各問題を \((B_i, A_i)\) のペアにして、\(B\) の昇順にソートする。
2. min-heap pq（現在選んでいる \(A\) たち）と、その総和 sum を用意する。
3. \(i = 0, 1, \dots, N-1\) の順に見て、
   • pq のサイズが \(K\) 未満なら、\(A_i\) を追加して sum += A_i。
   • サイズが \(K\) でかつ \(A_i > \) pq の最小値なら、最小値を取り除いて \(A_i\) を入れる（sum も更新）。これで「先頭 \(i+1\) 個の中の \(A\) の上位 \(K\) 個」が常に保たれる。
   • その後、pq のサイズが \(K\) でかつ sum \(\ge P\) なら、答えは \(B_i\)（ソート後の \(i\) 番目の \(B\)）なので出力して終了。
4. 最後まで達成できなければ \(-1\) を出力。

なぜ最初に条件を満たした時点の \(B_i\) が答えになるのか？ \(i-1\) 番目までで達成できなかったということは、先頭 \(i\) 個（\(0\) ～ \(i-1\)）からどう \(K\) 問選んでも \(P\) 未満ということです（上位 \(K\) 個の和が最大値なので）。よって最適解は必ず \(i\) 番目の問題を含み、選ばれた問題の難易度の最大値は \(B_i\) になります。\(B\) が同じ値の問題が複数あっても、出力される値は同じなので問題ありません。

具体例

\(N=4, K=2, P=10\)、\((A,B) = (3,5), (8,2), (4,9), (6,3)\) の場合。

\(B\) 昇順に並べると \((8,2), (6,3), (3,5), (4,9)\)。

• \(i=0\): pq \(=\{8\}\), sum \(=8\)（サイズ \(1 < K\)）
• \(i=1\): pq \(=\{8,6\}\), sum \(=14 \ge 10\) かつサイズ \(=2=K\) → 答え \(B=3\)

実際に配点 \(8\) と \(6\) の問題を選ぶと合計 \(14 \ge 10\) で、難易度の最大値は \(3\) です。

計算量

• 時間計算量: \(O(N \log N)\)（ソートとヒープ操作がそれぞれ \(O(N\log N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• オーバーフロー：\(P \le 10^{14}\)、配点の合計は最大 \(10^5 \times 10^9 = 10^{14}\) なので、int では溢れます。合計や \(P\) は 64bit 整数（long long）で扱いましょう。

• ペアのソート：pair<long long,long long> に \((B, A)\) の順で入れておけば、sort で \(B\) 昇順に並びます（\(A\) を第一要素にしない点に注意）。

• min-heap の書き方：C++ の priority_queue はデフォルトが最大値取り出しなので、priority_queue<long long, vector<long long>, greater<long long>> と書いて最小値取り出しにします。

• \(K\) 個未満の状態での判定禁止：ちょうど \(K\) 問選ぶ必要があるので、pq.size() == K の条件を必ず入れます。

• 二分探索で書く場合は、判定の中で「\(B_i \le X\) の問題の \(A\) を降順ソートして先頭 \(K\) 個の和」を求めればよく、\(O(N \log^2 N)\) 程度で通ります。ただし上記の走査の方がシンプルです。

  ソースコード

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

int main(){
    int N; long long K, P;
    scanf("%d %lld %lld", &N, &K, &P);
    vector<pair<long long,long long>> v(N); // (B, A)
    for(int i=0;i<N;i++){
        long long a,b;
        scanf("%lld %lld",&a,&b);
        v[i] = {b,a};
    }
    sort(v.begin(), v.end());
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long sum = 0;
    for(int i=0;i<N;i++){
        long long a = v[i].second;
        if((long long)pq.size() < K){
            pq.push(a);
            sum += a;
        } else if(!pq.empty() && a > pq.top()){
            sum -= pq.top();
            pq.pop();
            pq.push(a);
            sum += a;
        }
        if((long long)pq.size() == K && sum >= P){
            printf("%lld\n", v[i].first);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

---

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