概要

\(K\) 人を選んだときの戦闘力 \(S \times M\)（\(S\)=攻撃力合計、\(M\)=防御力の最小値）を最大化する。防御力の最小値を「候補として固定」して考え、攻撃力はその条件下で最大化する。

考察

戦闘力は \(S \times M\) です。ここで重要なのは \(M\) が選んだ \(K\) 人の中の最小防御力である点です。

• あるパーティの最小防御力が \(M\) だとすると、パーティの全員は 防御力が少なくとも \(M\) を満たします。
• つまり「最小防御力を \(M\) にする」＝「防御力 \(B \ge M\) の冒険者から \(K\) 人選ぶ」状況になります。
• このとき戦闘力を最大化するには、条件 \(B \ge M\) を満たす集合の中から 攻撃力 \(A\) の合計 \(S\) が最大になるように \(K\) 人を選べばよいです。

素朴に全組合せを試すと \(\binom{N}{K}\) 通りで不可能です。また、各 \(M\) ごとに「条件を満たす冒険者の中から攻撃力上位 \(K\) 人」を毎回ソートし直すと \(O(N^2 \log N)\) になり、\(N \le 2\times 10^5\) では間に合いません。

そこで、 - 防御力 \(B\) を大きい順に見ていけば、いま見ている防御力 \(b\) は「最小防御力の候補」になり得ます。 - その時点までに見た冒険者はすべて \(B \ge b\) を満たしているので、その中から攻撃力の合計が最大になる \(K\) 人を高速に管理できればよいです。

この「攻撃力上位 \(K\) 個の合計」を動的に管理するのに 最小ヒープが使えます。

アルゴリズム

1. 各冒険者を \((B_i, A_i)\) として保持し、防御力 \(B\) の降順にソートする。
2. 走査しながら、これまでに登場した冒険者（＝現在の \(b\) に対して \(B \ge b\) を満たす冒険者たち）の中から、
   • 攻撃力 \(A\) をヒープに追加
   • ヒープサイズが \(K\) を超えたら、最小の \(A\) を捨てる（＝攻撃力上位 \(K\) 個だけ残す）
   • ヒープ内の攻撃力合計 \(sum\_a\) も同時に更新しておく
3. ヒープサイズがちょうど \(K\) のとき、現在の防御力 \(b\) を最小防御力 \(M\) とみなした戦闘力は \(sum\_a \times b\)。 これを答えの最大値で更新する。

直感的なイメージ

防御力を高い方から「この値を最小にするなら、使える人はここまで」と候補を広げていき、そのたびに「使える人の中で攻撃力が強い \(K\) 人」を保つ、という流れです。

計算量

• 時間計算量: \(O(N \log N)\)（ソート \(O(N \log N)\) + 各要素のヒープ操作 \(O(\log K)\) を \(N\) 回）
• 空間計算量: \(O(N)\)（ソート用配列）＋ \(O(K)\)（ヒープ）

実装のポイント

• ヒープは 最小ヒープなので、「攻撃力上位 \(K\) 人」を維持するには、サイズが \(K\) を超えたら最小要素（弱い攻撃力）を捨てます。

• \(sum\_a \times b\) は最大で \(K \cdot 10^6 \cdot 10^6\) 程度になり得ますが、Python の int は多倍長なので安全です（他言語なら 64bit 整数を使用）。

• 入力が大きいので sys.stdin.buffer.readline を使うと安定します。

  ソースコード

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    adventurers = []
    for _ in range(N):
        A, B = map(int, input().split())
        adventurers.append((B, A))

    adventurers.sort(reverse=True)  # sort by B descending

    heap = []
    sum_a = 0
    ans = 0

    for b, a in adventurers:
        heapq.heappush(heap, a)
        sum_a += a
        if len(heap) > K:
            sum_a -= heapq.heappop(heap)
        if len(heap) == K:
            ans = max(ans, sum_a * b)

    print(ans)

if __name__ == "__main__":
    main()

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