概要

\(N\) 人の冒険者から \(K\) 人を選ぶとき、選んだメンバーの攻撃力の合計 \(S\) と防御力の最小値 \(M\) を使って \(S \times M\) を最大化する問題。

考察

この問題のポイントは、「戦闘力 = 攻撃力の合計 × 防御力の最小値」であることです。つまり、防御力の低いメンバーを入れてしまうと、たとえ攻撃力が高くても戦闘力が低くなってしまいます。

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

単純には、すべての \(K\) 人の組み合わせを試す方法がありますが、これは \({}_N C_K\) 通りあり、\(N\) が最大 \(2 \times 10^5\) なので現実的ではありません（時間計算量が爆発する）。

解決策

「防御力の最小値 \(M\)」に注目して、すべての冒険者を防御力が高い順に並べて考えます。この順番で先頭から \(K\) 人選ぶことを考えると、\(K\) 番目に選んだ冒険者の防御力がそのグループの最小値になります。

したがって、防御力が高い順に並べた上で、先頭から \(i\) 番目の冒険者を「最小防御力を持つメンバー」と仮定し、それ以前（つまり防御力がより高い or 同じ）の冒険者の中から攻撃力が最も高い上位 \(K\) 人を選ぶのが最適です。

このようにすることで、防御力を固定して攻撃力を最大化するという戦略が有効になります。

なぜこれでうまくいくのか？

防御力が高い順にソートしておくことで、ある冒険者を最小防御力の候補としたときに、それより防御力が高い候補の中から攻撃力を最大にするような組み合わせを高速に求めることができるのです。

アルゴリズム

1. 冒険者リストを防御力 \(B_i\) の降順にソートする。
2. ソート後のリストを前から見ていき、今見ている冒険者の防御力 \(b\) を「最小防御力」と仮定する。
3. その時点で見た冒険者のうち、攻撃力が大きい上位 \(K\) 人の合計を管理するために、最小ヒープを使用する：
   • 新しい冒険者の攻撃力をヒープに追加し、合計も更新。
   • ヒープのサイズが \(K\) を超えたら、最小の攻撃力を削除。
4. ヒープのサイズがちょうど \(K\) になったら、その時点での攻撃力の合計 \(S\) と現在の防御力 \(b\) を使って戦闘力 \(S \times b\) を計算し、最大値を更新する。
5. 最終的な最大値を出力。

例

例えば、以下のような入力があったとします：

4 2
3 5
2 4
4 3
1 2

冒険者は次のように整理できます： - (攻撃力, 防御力): (3,5), (2,4), (4,3), (1,2)

これを防御力で降順ソートすると： - (3,5), (2,4), (4,3), (1,2)

1つずつ見て行きながら、攻撃力の上位2人を選びます。

• 最初: (3,5) → ヒープ: [3], 合計=3, 人数=1 → 不十分
• 次: (2,4) → ヒープ: [2,3], 合計=5, 人数=2 → 戦闘力 = 5×4 = 20
• 次: (4,3) → ヒープ: [3,4]（最小の2を捨てる）→ 合計=7 → 戦闘力 = 7×3 = 21
• 最後: (1,2) → ヒープ: [4,3]（最小の1を捨てる）→ 合計=7 → 戦闘力 = 7×2 = 14

最大値は 21。

計算量

• 時間計算量: \(O(N \log N)\)

  • ソートに \(O(N \log N)\)
  • 各要素に対してヒープ操作（push/pop）が \(O(\log K)\) で行われるため、全体で \(O(N \log K)\)
  • よって総合で \(O(N \log N)\)

• 空間計算量: \(O(K)\)

  • 最小ヒープのサイズは最大 \(K\)

実装のポイント

• 冒険者を防御力で降順ソートするのが重要。

• 攻撃力の上位 \(K\) 個を効率よく管理するために最小ヒープを使う。

• ヒープのサイズが \(K\) を超えたら、最小の要素を削除する。

• 最後に最大値を更新するタイミングは、ヒープのサイズがちょうど \(K\) のときだけ。

  ソースコード

import sys
import heapq

input = sys.stdin.read
data = input().split()

N = int(data[0])
K = int(data[1])

adventurers = []
index = 2
for i in range(N):
    a = int(data[index])
    b = int(data[index+1])
    adventurers.append((a, b))
    index += 2

# 防御力で降順ソート
adventurers.sort(key=lambda x: -x[1])

max_power = 0
min_heap = []  # 攻撃力の最小ヒープ
attack_sum = 0

for i in range(N):
    a, b = adventurers[i]
    heapq.heappush(min_heap, a)
    attack_sum += a

    if len(min_heap) > K:
        removed = heapq.heappop(min_heap)
        attack_sum -= removed

    if len(min_heap) == K:
        power = attack_sum * b
        if power > max_power:
            max_power = power

print(max_power)

---

この解説は qwen3-coder-480b によって生成されました。