概要

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

考察

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

\(N\) 人から \(K\) 人を選ぶ組み合わせは \({}_N C_K\) 通りあります。\(N = 2 \times 10^5\) のとき、これは天文学的な数になり、全探索は到底間に合いません。

重要な気づき

戦闘力は \(S \times M\)（攻撃力合計 × 防御力最小値）で計算されます。ここで、防御力の最小値 \(M\) を固定して考えると問題がシンプルになります。

防御力の最小値が \(M\) であるとき： - 選ぶ \(K\) 人全員の防御力が \(M\) 以上でなければならない - その中で攻撃力の合計 \(S\) を最大化したい

つまり、「防御力が \(M\) 以上の冒険者の中から、攻撃力が大きい上位 \(K\) 人を選ぶ」のが最適です。

解決のアイデア

冒険者を防御力の降順にソートします。すると、\(i\) 番目の冒険者まで見たとき、それらの冒険者は全員、\(i\) 番目の冒険者の防御力以上を持っています。

つまり、\(i\) 番目の冒険者の防御力を \(M\) として固定したとき、候補となる冒険者は「\(1\) 番目から \(i\) 番目まで」の \(i\) 人です。この中から攻撃力上位 \(K\) 人を効率的に選べれば、各 \(M\) に対する最大戦闘力が求まります。

アルゴリズム

1. ソート: 全冒険者を防御力 \(B\) の降順にソートする

2. ヒープで攻撃力上位 \(K\) 人を管理:

   • 最小ヒープ（min-heap）を使い、現在選んでいる \(K\) 人の攻撃力を管理
   • 攻撃力の合計 current_sum も同時に管理

3. 順番に冒険者を追加:

   • \(i\) 番目の冒険者を追加（ヒープに push し、合計に加算）
   • \(K\) 人を超えたら、攻撃力が最小の冒険者をヒープから除外（pop して合計から減算）
   • ちょうど \(K\) 人のとき、戦闘力 = current_sum × \(B_i\) を計算し、最大値を更新

具体例

\(N=4, K=2\) で、冒険者が \((A, B) = (5, 3), (4, 7), (3, 5), (6, 2)\) の場合：

防御力降順にソート: \((4, 7), (3, 5), (5, 3), (6, 2)\)

ステップ	追加	ヒープ内の攻撃力	合計	防御力最小	戦闘力
1	(4,7)	[4]	4	-	-
2	(3,5)	[3,4]	7	5	\(7 \times 5 = 35\)
3	(5,3)	[4,5]（3を除外）	9	3	\(9 \times 3 = 27\)
4	(6,2)	[5,6]（4を除外）	11	2	\(11 \times 2 = 22\)

最大値は \(35\)。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 各冒険者に対するヒープ操作が \(O(\log K)\)、全体で \(O(N \log K)\)
• 空間計算量: \(O(N)\)
  • 冒険者リストとヒープの保持に必要

実装のポイント

• Pythonの heapq は最小ヒープなので、攻撃力が最も小さいものが先頭に来る。これは「攻撃力が小さい冒険者を除外したい」という要件に合致

• 防御力の降順でソートしているため、\(i\) 番目の冒険者を追加した時点で、ヒープ内の全員が \(B_i\) 以上の防御力を持つことが保証される

• 戦闘力の計算結果は最大 \(10^6 \times K \times 10^6\) 程度になりうるが、Pythonは多倍長整数を扱えるのでオーバーフローの心配は不要

  ソースコード

import heapq

def solve():
    N, K = map(int, input().split())
    adventurers = []
    for _ in range(N):
        a, b = map(int, input().split())
        adventurers.append((a, b))
    
    # 防御力Bの降順でソート
    adventurers.sort(key=lambda x: -x[1])
    
    # 攻撃力の最小ヒープ（現在選んでいるK人の攻撃力を管理）
    min_heap = []
    current_sum = 0
    max_combat = 0
    
    for i in range(N):
        a, b = adventurers[i]
        
        # 現在の冒険者を追加
        heapq.heappush(min_heap, a)
        current_sum += a
        
        # K人を超えたら、攻撃力が最小の冒険者を除外
        if len(min_heap) > K:
            removed = heapq.heappop(min_heap)
            current_sum -= removed
        
        # ちょうどK人選んでいる場合、戦闘力を計算
        if len(min_heap) == K:
            # 現在の冒険者iが最後に追加されたので、防御力の最小値はb
            combat = current_sum * b
            max_combat = max(max_combat, combat)
    
    print(max_combat)

solve()

---

この解説は claude4.5opus によって生成されました。