概要

問題を難易度の低い順に調べながら、それまでに見た問題のうち配点が大きい \(K\) 問を管理します。その配点の合計が初めて \(P\) 以上になったときの難易度が答えです。

考察

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

選ぶ問題の難易度をすべて \(x\) 以下に制限したとします。

このとき、難易度が \(x\) 以下の問題から配点が大きい順に \(K\) 問を選べば、配点の合計を最大にできます。したがって、条件を満たす選び方が存在するのは、次の両方を満たす場合です。

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

難易度の上限を大きくするほど選べる問題が増えるので、一度条件を満たせば、それ以降も条件を満たします。

そこで、問題を難易度の昇順に並べ、使える問題を \(1\) 問ずつ増やしていきます。

上位 \(K\) 個を効率よく管理する

すべての \(K\) 問の組合せを調べる方法は、組合せの数が膨大になるため間に合いません。また、問題を追加するたびに配点を並べ直しても、全体で \(O(N^2 \log N)\) 程度かかってしまいます。

必要なのは、これまでに見た問題の配点のうち、上位 \(K\) 個だけです。これらを最小ヒープで管理します。最小ヒープとは、格納した値の最小値をすぐに取得できるデータ構造です。

現在の上位 \(K\) 個の最小値を \(m\)、新しく見た問題の配点を \(a\) とすると、更新は次のようになります。

• \(a \leq m\) なら、上位 \(K\) 個は変更しない。
• \(a > m\) なら、\(m\) を取り除いて \(a\) を入れる。

配点の合計も保持すれば、置き換え時に \(a-m\) を加えるだけで更新できます。

例えば \(K=3\) で、保持している配点が \(4,7,10\) のとき、配点 \(8\) の問題が追加されたら \(4\) を \(8\) に置き換えます。合計は \(21\) から \(25\) になります。

アルゴリズム

1. 各問題を (難易度, 配点) の組として保存し、難易度の昇順にソートする。
2. 先頭の \(K\) 問の配点で最小ヒープを作り、その合計を total とする。
3. total が \(P\) 以上なら、先頭から \(K\) 番目の問題の難易度を出力して終了する。
4. 残りの問題を順に調べる。現在の問題の難易度を \(b\)、配点を \(a\) とする。
   • \(a\) がヒープの最小値以下なら、何もしない。
   • \(a\) がヒープの最小値より大きければ、最小値を \(a\) に置き換え、total を更新する。
   • 更新後の total が \(P\) 以上なら、\(b\) を出力して終了する。
5. 最後まで条件を満たさなければ、\(-1\) を出力する。

正しさの説明

最初は、見た問題がちょうど \(K\) 問なので、ヒープにはその中の配点上位 \(K\) 個が入っています。

新しい問題を追加したときも、その配点がヒープの最小値より大きい場合だけ置き換えることで、ヒープには常に、これまでに見た問題の配点上位 \(K\) 個が入るという性質が保たれます。よって、total はそれまでに見た問題から \(K\) 問を選ぶ場合の最大合計です。

初めて total が \(P\) 以上になったとき、現在の難易度を \(b\) とします。ここまでに見た問題の難易度はすべて \(b\) 以下なので、難易度の最大値を \(b\) 以下にして条件を満たせます。

一方、難易度が \(b\) 未満の問題はすでにすべて調べています。それらだけでは、問題数が足りないか、配点上位 \(K\) 個を選んでも合計が \(P\) 未満でした。したがって、\(b\) より小さい値を答えにすることはできず、\(b\) が最小です。

最後まで条件を満たさなければ、全問題の配点上位 \(K\) 個を選んでも合計が足りないため、答えは \(-1\) です。

計算量

• 時間計算量: \(O(N \log N)\)
  ソートに \(O(N \log N)\)、ヒープの更新全体に \(O(N \log K)\) かかります。
• 空間計算量: \(O(N)\)
  問題一覧に \(O(N)\)、ヒープに \(O(K)\) の領域を使います。

実装のポイント

• Python の heapq は最小ヒープを扱います。最小値は heap[0] で取得できます。

• heapq.heapreplace(heap, a) は、最小値を取り除いて \(a\) を挿入し、取り除いた値を返します。コードではこれを使って、合計を total += a - 取り除いた値 と更新しています。

• 置き換えが起きなければ合計は変わらないため、条件判定は初期化直後と置き換え直後だけで十分です。

• 同じ難易度の問題はまとめずに \(1\) 問ずつ処理して構いません。途中で条件を満たしても、出力する難易度は同じです。

• 配点の合計は最大 \(10^{14}\) になるため、固定長整数を使う言語では \(64\) ビット整数が必要です。Python の整数ではそのまま扱えます。

  ソースコード

import sys
import heapq


def main():
    input = sys.stdin.buffer.readline
    N, K, P = map(int, input().split())

    problems = []
    for _ in range(N):
        a, b = map(int, input().split())
        problems.append((b, a))
    problems.sort()

    heap = [problems[i][1] for i in range(K)]
    total = sum(heap)
    heapq.heapify(heap)

    if total >= P:
        print(problems[K - 1][0])
        return

    replace = heapq.heapreplace
    for i in range(K, N):
        b, a = problems[i]
        if a > heap[0]:
            total += a - replace(heap, a)
            if total >= P:
                print(b)
                return

    print(-1)


if __name__ == "__main__":
    main()

---

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