概要

\(N\) 人の冒険者から \(K\) 人を選び、「攻撃力の合計 \(\times\) 防御力の最小値」を最大化する問題です。 防御力の最小値を固定して考えることで、効率的に最適な組み合わせを見つけることができます。

考察

この問題の難しさは、攻撃力の合計 \(S\) を大きくしようとすると防御力の最小値 \(M\) が小さくなりやすく、逆に \(M\) を大きくしようとすると選べる人数が限られて \(S\) が小さくなりやすいという、2つの変数のバランスにあります。

1. 防御力を固定して考える

もし、「パーティの防御力の最小値 \(M\) を、冒険者 \(i\) の防御力 \(B_i\) 以上にする」と決めた場合、どのような選び方が最善でしょうか？ この場合、防御力が \(B_i\) 以上である冒険者たちの中から、攻撃力 \(A\) が大きい順に \(K\) 人選ぶのが明らかに最適です。

2. 全ての冒険者を「最小値の候補」として試す

全ての冒険者について、「この人の防御力をパーティの最小値（\(M\)）とする」という状況を順に試していきます。 効率的に計算するために、まず全冒険者を防御力 \(B\) の降順（大きい順）にソートします。

ソートされた順に冒険者を見ていくと、\(i\) 番目の冒険者を処理しているとき、それまでに登場した冒険者（\(1\) 〜 \(i\) 番目）は全員、現在の冒険者の防御力 \(B_i\) 以上の防御力を持っています。 したがって、この \(i\) 人の中から攻撃力 \(A\) が大きい \(K\) 人を選べば、その時点での「攻撃力の合計 \(\times B_i\)」の最大値が計算できます。

3. 効率的な管理（優先度付きキュー）

冒険者を一人ずつ追加しながら「攻撃力が高い上位 \(K\) 人」を維持するには、最小ヒープ（優先度付きキュー）を使うのが効率的です。

• 新しい冒険者の攻撃力 \(A_i\) をヒープに追加する。
• ヒープのサイズが \(K\) を超えたら、最も攻撃力が低い（ヒープの先頭）冒険者を削除する。
• これにより、常に「これまでに現れた中で攻撃力が高い \(K\) 人」の合計を維持できます。

アルゴリズム

1. 冒険者を防御力 \(B_i\) の降順にソートする。
2. 空の最小ヒープと、現在の攻撃力の合計 current_attack_sum（初期値 0）を用意する。
3. ソートされた冒険者を一人ずつ取り出し、以下の処理を行う：
   • 現在の冒険者の攻撃力 \(A_i\) を current_attack_sum に加え、ヒープに追加する。
   • ヒープのサイズが \(K\) を超えたら、最小値（一番小さい攻撃力）を取り出して current_attack_sum から引く。
   • ヒープのサイズがちょうど \(K\) になったとき、current_attack_sum * B_i を計算し、これまでの最大値と比較して更新する。
4. 最終的な最大値を出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  • 冒険者のソートに \(O(N \log N)\) かかります。
  • \(N\) 人の冒険者を順に処理し、各ステップでヒープの挿入・削除を行うのに \(O(N \log K)\) かかります。
  • 全体として \(O(N \log N)\) となり、制約の \(N = 2 \times 10^5\) でも十分に高速です。
• 空間計算量: \(O(N)\)
  • 冒険者のデータを保持するリストと、最大 \(K\) 個の要素を持つヒープを使用します。

実装のポイント

• ソートの順序: 防御力の高い順に処理することで、「現在の \(B_i\) が、選ばれた \(K\) 人の中での最小値である」という状態を自然に作り出せます。

• 高速な入出力: Pythonの場合、データ量が多い（\(N=2 \times 10^5\)）ため、sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

  ソースコード

import sys
import heapq

def solve():
    # 入力の高速化
    input = sys.stdin.read().split()
    if not input:
        return
    
    N = int(input[0])
    K = int(input[1])
    
    adventurers = []
    idx = 2
    for _ in range(N):
        a = int(input[idx])
        b = int(input[idx+1])
        adventurers.append((a, b))
        idx += 2
    
    # 防御力 B の降順にソートする
    # これにより、ある冒険者を「パーティ内で最小の防御力」としたとき、
    # それまでに見た（防御力がそれ以上の）冒険者の中から攻撃力の高い K 人を選べばよくなる
    adventurers.sort(key=lambda x: x[1], reverse=True)
    
    max_power = 0
    current_attack_sum = 0
    # 攻撃力 A を管理するための最小ヒープ
    # パーティの候補となる K 人の攻撃力を保持する
    min_heap = []
    
    for a, b in adventurers:
        heapq.heappush(min_heap, a)
        current_attack_sum += a
        
        # パーティの人数が K 人を超えたら、攻撃力が最小の冒険者を除外する
        if len(min_heap) > K:
            removed_a = heapq.heappop(min_heap)
            current_attack_sum -= removed_a
        
        # パーティの人数がちょうど K 人になったら戦闘力を計算
        if len(min_heap) == K:
            # 現在の b は、ヒープに入っている K 人の中で最小の防御力であることが保証されている
            power = current_attack_sum * b
            if power > max_power:
                max_power = power
                
    print(max_power)

if __name__ == "__main__":
    solve()

---

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