概要

\(N\) 問の候補問題から \(K\) 問を選び、配点の合計を \(P\) 以上にしつつ、選んだ問題の難易度の最大値を最小化する問題です。難易度でソートしてから「配点上位 \(K\) 問の和」を優先度付きキュー（最小ヒープ）で管理することで解けます。

考察

気づき 1: 「最大値の最小化」は閾値を決めると簡単になる

「難易度の最大値が \(X\) 以下」という条件で \(K\) 問選ぶことを考えます。このとき使える問題は \(B_i \le X\) を満たすものだけです。その中から \(K\) 問選んで配点の合計を最大にしたいなら、配点 \(A_i\) が大きいものを上から \(K\) 個取るのが最適です（貪欲）。

つまり、

\(B_i \le X\) である問題の中で、\(A_i\) の上位 \(K\) 個の和が \(P\) 以上かどうか

を判定できれば、その \(X\) が答えの候補になるかが分かります。

気づき 2: 答えは必ずいずれかの \(B_i\) に一致する

最大値の最小値なので、答えは実際に選んだ問題のうち難易度が最大のもの、すなわち入力に現れる \(B_i\) のどれかです。よって、\(X\) として \(B_1, \dots, B_N\) だけを試せば十分です。

気づき 3: 単調性があるので二分探索も可能

\(X\) を大きくすると使える問題が増えるだけなので、「上位 \(K\) 個の和」は単調非減少です。よって答えに関して単調性があり、\(X\) について二分探索できます。ただし各判定でソートし直すと \(O(N \log^2 N)\) 程度になり、少し無駄です。

素朴なアプローチの問題点

• 全ての \(K\) 問の組み合わせを試す: \(\binom{N}{K}\) 通りで指数的、\(N \le 10^5\) では絶望的。
• 各 \(B_i\) を閾値として毎回ソート・上位 \(K\) 個を数え直す: 判定 1 回に \(O(N \log N)\) かかり、全体 \(O(N^2 \log N)\) で TLE。

解決策: 難易度昇順に見ていき、ヒープで上位 \(K\) 個を維持

問題を \(B\) の昇順に並べて 1 つずつ「使える集合」に追加していきます。閾値を \(B\) の小さい方から順に広げていくイメージです。このとき、

• 現在までに見た問題の中の \(A\) の上位 \(K\) 個の和 \(s\)

を、最小ヒープ（サイズ \(K\)、中身は選ばれている \(A\) の値）で \(O(\log K)\) ずつ更新できます。\(s \ge P\) になった瞬間の \(B\) が答えです（それ以降に \(B\) を大きくしても最大値は増えるだけなので、最初に条件を満たした時点が最小）。

アルゴリズム

1. \((B_i, A_i)\) のペアを作り、\(B\) の昇順にソートする。
2. 空の最小ヒープ heap と合計 \(s = 0\) を用意する。
3. ソート順に \((b, a)\) を見ていく:
   • ヒープのサイズが \(K\) 未満なら、\(a\) を push し \(s \mathrel{+}= a\)。
     • サイズが \(K\) になり、かつ \(s \ge P\) なら答えは \(b\) で終了。
   • サイズが \(K\) のとき、\(a\) がヒープの最小値 heap[0] より大きければ、最小値を捨てて \(a\) を入れる（heappushpop）。\(s\) をその差分だけ更新する。
     • \(s \ge P\) なら答えは \(b\) で終了。
   • \(a \le\) heap[0] のときは、\(a\) を入れると合計が減るだけなので何もしない（ただし、この問題を「使える」ようにしたこと自体は最大値に影響しないので無視して良い）。
4. 最後まで \(s \ge P\) にならなければ \(-1\) を出力。

具体例

\(N = 4, K = 2, P = 10\)、\((A, B) = (3, 1), (8, 5), (6, 3), (2, 2)\) とします。

\(B\) 昇順に並べると \((B, A) = (1, 3), (2, 2), (3, 6), (5, 8)\)。

処理	ヒープ（\(A\) の上位 2 個）	\(s\)	判定
\((1,3)\)	\(\{3\}\)	3	サイズ \(<K\)
\((2,2)\)	\(\{2,3\}\)	5	\(5 < 10\)
\((3,6)\)	\(\{3,6\}\)（2 を捨てる）	9	\(9 < 10\)
\((5,8)\)	\(\{6,8\}\)（3 を捨てる）	14	\(14 \ge 10\) → 答え \(5\)

答えは \(5\) です。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが \(O(N\log N)\)、ヒープ操作が全体で \(O(N \log K)\)）
• 空間計算量: \(O(N)\)（入力の保持。ヒープ自体は \(O(K)\)）

実装のポイント

• ソートキーの順序: タプルを \((B_i, A_i)\) の順で持つと、そのままソートするだけで \(B\) 昇順になります（コードでは items を (B, A) の順に作っています）。

• 答えを返すタイミング: サイズが \(K\) に達した後、\(s\) を更新するたびに \(s \ge P\) を判定します。「サイズ \(K\) 未満」の段階では \(K\) 問選べていないので判定してはいけません（コードでは len(heap) == k and s >= p としてサイズ到達時のみ判定）。

• 同じ \(B\) が複数ある場合: \(B\) 昇順に処理しているので、同じ \(B\) の問題群を途中まで入れた時点で条件を満たしても、答えはその \(B\) で正しく、問題ありません。

• 合計の更新は差分で: heappushpop で押し出された値 old を使い s += a - old とすると \(O(1)\) で合計を保てます。毎回ヒープ全体を足し直すと \(O(K)\) かかり TLE の恐れがあります。

• \(a \le\) heap[0] のスキップ: これを忘れて無条件に heappushpop すると合計が減ってしまい WA になります。

• オーバーフロー: \(P \le 10^{14}\)、\(A_i \le 10^9\) で合計は最大 \(10^{14}\) 程度。Python では多倍長整数なので問題ありませんが、C++ では long long を使う必要があります。

• 入力の高速化: \(N \le 10^5\) なので sys.stdin.buffer.read() でまとめて読むと安全です。

  ソースコード

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1]); p = int(data[2])
    items = [(int(data[3 + 2*i + 1]), int(data[3 + 2*i])) for i in range(n)]
    items.sort()
    heap = []
    push = heapq.heappush
    pushpop = heapq.heappushpop
    s = 0
    for i in range(n):
        b, a = items[i]
        if len(heap) < k:
            push(heap, a)
            s += a
            if len(heap) == k and s >= p:
                print(b)
                return
        else:
            if a > heap[0]:
                old = pushpop(heap, a)
                s += a - old
                if s >= p:
                    print(b)
                    return
    print(-1)

main()

---

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