概要

\(N\) 個の岩を破壊する最小ターン数を求める問題です。ダイナマイト（1ターンで破壊）を最大 \(K\) 個使え、それ以外はハンマーで硬度分のターンをかけて破壊します。

考察

重要な気づき

まず、各岩を破壊するのに必要なターン数を考えます。

• ダイナマイトを使う場合: 硬度に関係なく 1ターン
• ハンマーを使う場合: 硬度 \(H_i\) と同じ \(H_i\) ターン

岩は順番に処理する必要がありますが、どの岩にダイナマイトを使うかは自由に選べます。

最適な戦略

ダイナマイトを使うと、本来 \(H_i\) ターンかかる岩を 1ターンで破壊できます。つまり、\(H_i - 1\) ターン節約できます。

節約量を最大化するには、硬度が大きい岩にダイナマイトを使うべきです！

例えば、\(H = [3, 10, 2, 8]\) で \(K = 2\) の場合：

• 硬度の大きい順に並べると: \(10, 8, 3, 2\)
• ダイナマイトは硬度 \(10\) と \(8\) の岩に使う
• 必要ターン数 = \(2\)（ダイナマイト）\(+ 3 + 2\)（ハンマー）\(= 7\)

公式の導出

• ダイナマイトを \(K\) 個使う → \(K\) ターン
• 残り \(N - K\) 個の岩はハンマーで破壊 → 残りの硬度の合計ターン

\(\text{最小ターン数} = K + (\text{全硬度の合計} - \text{上位} K \text{個の硬度の合計})\)

アルゴリズム

硬度の大きい上位 \(K\) 個を効率的に求める方法を考えます。

方法1: ソート

全要素をソートして上位 \(K\) 個を取り出す。時間計算量 \(O(N \log N)\)。

方法2: ヒープ（本解法）

最小ヒープを使って、常にサイズ \(K\) の「今まで見た中で最大の \(K\) 個」を管理します。

1. ヒープのサイズが \(K\) 未満なら、要素を追加
2. サイズが \(K\) で、新しい要素がヒープの最小値より大きければ、最小値を取り除いて新しい要素を追加

この方法により、配列を1回走査するだけで上位 \(K\) 個が求まります。

コーナーケース

• \(K \geq N\) の場合: 全ての岩をダイナマイトで破壊 → 答えは \(N\)
• \(K = 0\) の場合: 全てハンマーで破壊 → 答えは \(\sum H_i\)

計算量

• 時間計算量: \(O(N \log K)\)
  • 各要素に対してヒープ操作（\(O(\log K)\)）を最大1回行う
• 空間計算量: \(O(K)\)
  • サイズ \(K\) のヒープを保持

実装のポイント

1. heapq.heapreplaceの活用: heappop してから heappush する代わりに、heapreplace を使うと効率的です（1回のヒープ操作で済む）。

2. コーナーケースの先処理: \(K \geq N\) や \(K = 0\) の場合を最初に処理しておくと、メインロジックがシンプルになります。

3. Pythonのheapqは最小ヒープ: 最大値を管理したい場合は符号を反転させる方法もありますが、本問題では「上位 \(K\) 個の最小値」を管理することで、最小ヒープをそのまま活用しています。

ソースコード

import heapq

def solve():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    if K >= N:
        # すべての岩をダイナマイトで破壊できる
        print(N)
        return
    
    if K == 0:
        # ダイナマイトが使えない場合、すべてハンマーで叩く
        print(sum(H))
        return
    
    # K個のダイナマイトを使う場合、硬度の大きい順にK個の岩にダイナマイトを使うのが最適
    # ダイナマイトを使う岩: 1ターン
    # ハンマーで壊す岩: H_i ターン
    
    # 硬度の大きいK個にダイナマイトを使い、残りはハンマーで壊す
    # 最小ターン = K + (全硬度の合計 - 上位K個の硬度の合計)
    
    # 上位K個の硬度を求める
    # ヒープを使って効率的に求める
    
    # 最小ヒープでK個の最大値を管理
    min_heap = []
    
    for h in H:
        if len(min_heap) < K:
            heapq.heappush(min_heap, h)
        elif h > min_heap[0]:
            heapq.heapreplace(min_heap, h)
    
    top_k_sum = sum(min_heap)
    total_sum = sum(H)
    
    # ダイナマイトを使う岩: K個 × 1ターン = Kターン
    # ハンマーで壊す岩: (N-K)個、合計硬度 = total_sum - top_k_sum ターン
    result = K + (total_sum - top_k_sum)
    print(result)

solve()

---

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