概要

\(N\) 問の候補問題から配点の合計が \(P\) 点以上となるように \(K\) 問を選ぶとき、選ばれた問題の難易度の最大値を最小化する問題です。

考察

素朴なアプローチとその課題

すべての組み合わせ（\(_N\mathrm{C}_K\) 通り）を試す全探索は、\(N \le 10^5\) という制約下では天文学的な計算量となり間に合いません。

重要な気づき

「難易度の最大値をできるだけ小さくしたい」という目的に注目します。 もし「選ぶ問題の難易度の上限を \(X\) に制限する」とした場合、難易度が \(X\) 以下の問題の中から配点 \(A_i\) が大きい上位 \(K\) 問を選んだときに、配点の合計が最大になります。この合計が \(P\) 以上になれば、難易度の最大値を \(X\) 以下にできることになります。

この判定問題に対して二分探索を行うアプローチ（答えで二分探索）も考えられますが、難易度 \(B_i\) の昇順にソートして走査することで、さらに効率的かつシンプルに解くことができます。

難易度が低い順に問題を 1 つずつ見ていき、「これまでに出現した問題の中で、配点 \(A_i\) が大きい上位 \(K\) 個」を常に管理します。 難易度の昇順に見ているため、配点上位 \(K\) 個の合計が初めて \(P\) 以上になった瞬間の難易度 \(B_i\) が、求めるべき「難易度の最大値の最小値」となります。

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

配点の上位 \(K\) 個を管理するには、サイズが \(K\) の最小ヒープ（優先度付きキュー）を利用します。 - ヒープ内の要素数が \(K\) 未満のときは、無条件で配点 \(A_i\) をヒープに追加します。 - すでに \(K\) 個あるときは、ヒープの先頭（現在の上位 \(K\) 個の中で最小の配点）と現在の配点 \(A_i\) を比較します。\(A_i\) の方が大きければ、最小値を取り出して \(A_i\) を追加します。

この操作により、常に「これまで見た中で最大の配点を持つ \(K\) 個」を高速に維持できます。

アルゴリズム

1. 各問題を \((\text{難易度 } B_i, \text{配点 } A_i)\) のペアとして保持し、難易度 \(B_i\) の昇順にソートします。
2. 最小ヒープ h と、ヒープ内の配点の合計値を保持する変数 current_sum を用意します。
3. ソートした問題を先頭から順に走査します：
   • len(h) < K の場合：\(A_i\) を h に追加し、current_sum に加算します。
   • len(h) == K かつ \(A_i > \text{hの最小値}\) の場合：h の最小値を \(A_i\) で置き換え、差分を current_sum に反映します。
   • len(h) == K かつ current_sum >= P を満たしたら、その時点の \(B_i\) を出力して終了します。
4. 全ての問題を見終えても条件を満たさなかった場合は、配点の合計を \(P\) 以上にすることが不可能であるため -1 を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 問題のソートに \(O(N \log N)\) かかります。
  • 各問題についてヒープの操作（挿入または置換）を行うため、走査部分は \(O(N \log K)\) です。
  • 全体として \(O(N \log N + N \log K) = O(N \log N)\) となり、制約 \(N \le 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 入力された問題リストの保持に \(O(N)\)、ヒープのサイズは最大で \(K\) のため \(O(K)\) となり、全体で \(O(N)\) です。

実装のポイント

• heapq.heapreplace の活用: すでにヒープのサイズが \(K\) のとき、最小値のポップと新しい値のプッシュを heapq.heapreplace(h, a) で同時に行うことで、処理を効率化しています。

• オーバーフローの考慮: 配点の合計 \(P\) や合計値 current_sum は最大で \(10^{14}\) 程度に達します。Python では自動的に多倍長整数として扱われますが、C++ 等の静的型付け言語で実装する場合は 64-bit 整数型（long long）を使用する必要があります。

  ソースコード

import sys
import heapq

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    K = int(input_data[1])
    P = int(input_data[2])

    problems = []
    idx = 3
    for _ in range(N):
        a = int(input_data[idx])
        b = int(input_data[idx + 1])
        problems.append((b, a))
        idx += 2

    problems.sort(key=lambda x: x[0])

    h = []
    current_sum = 0

    for b, a in problems:
        if len(h) < K:
            heapq.heappush(h, a)
            current_sum += a
        elif h[0] < a:
            current_sum += a - h[0]
            heapq.heapreplace(h, a)

        if len(h) == K and current_sum >= P:
            print(b)
            return

    print(-1)

if __name__ == '__main__':
    main()

---

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