概要

\(N\) 個の岩を順番に破壊する問題です。各岩に対して「ハンマー（硬度を 1 減らす）」か「ダイナマイト（一撃で破壊する）」のいずれかを選択し、合計 \(K\) 回までのダイナマイトを効果的に使って、全岩を破壊する最小ターン数を求めます。

考察

まず、ダイナマイトを使わずにすべてハンマーで破壊する場合を考えます。このとき、岩 \(i\) を破壊するには \(H_i\) ターンかかるため、合計ターン数は \(\sum_{i=1}^{N} H_i\) となります。

次に、ダイナマイトを岩 \(i\) に使用した場合を考えます。

• ハンマーの場合: \(H_i\) ターンかかる
• ダイナマイトの場合: 1 ターンで済む

つまり、ダイナマイトを岩 \(i\) に使うことで、ターン数を \(H_i - 1\) だけ短縮できることになります。ただし、もともとの硬度が \(H_i = 1\) の岩にダイナマイトを使っても、ハンマーと同じ 1 ターンを消費するため、短縮できるターン数は \(0\) です。

最小ターン数を求めるためには、限られた \(K\) 回のダイナマイトを使って、「短縮できるターン数（\(H_i - 1\)）」を最大化すればよいことがわかります。

アルゴリズム

1. すべての岩をハンマーで叩いた場合の合計ターン数 total_hammer_turns を計算します。
2. 各岩について、ダイナマイトを使ったときに節約できるターン数 \(H_i - 1\) を計算し、リスト（savings）に格納します。
   • \(H_i = 1\) の場合は節約分が \(0\) なので、計算に含める必要はありません（含めても結果は変わりません）。
3. 節約できるターン数が多い順にリストをソート（降順ソート）します。
4. リストの先頭から最大 \(K\) 個分を取り出し、その合計を「最大削減量」とします。
5. total_hammer_turns - 最大削減量 が答えとなります。

計算量

• 時間計算量: \(O(N \log N)\)
  • 岩の硬度の合計計算に \(O(N)\)、節約できるターン数のソートに \(O(N \log N)\) かかります。\(N = 2 \times 10^5\) であるため、制限時間内に十分間に合います。
• 空間計算量: \(O(N)\)
  • 各岩の硬度や節約分を保持するためのリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 入力の高速化: \(N\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。
• スライスの活用: savings[:k] のようにスライスを用いることで、もし \(K\) が岩の個数より大きくてもエラーにならず、安全に「最大 \(K\) 個」の合計を計算できます。
• 大きな数値: 合計ターン数は非常に大きな数（最大 \(2 \times 10^{14}\) 程度）になることがありますが、Python は標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割します。
    # sys.stdin.read().split() は大量の入力を効率的に処理するのに適しています。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: 岩の個数, K: ダイナマイトの最大使用回数
    n = int(data[0])
    k = int(data[1])
    
    # h: 各岩の硬度のリスト
    # 入力の3番目の要素以降が各岩の硬度 H_i に対応します。
    h = list(map(int, data[2:]))
    
    # すべての岩をハンマーのみで破壊した場合の合計ターン数を計算します。
    # 各岩 i に対して H_i 回のハンマー叩きが必要です。
    total_hammer_turns = sum(h)
    
    # ダイナマイトを岩 i に使用した場合、その岩は1ターンで破壊されます。
    # つまり、ハンマーで破壊する場合に比べて (H_i - 1) ターンを節約できます。
    # ただし、H_i = 1 の場合はハンマーでもダイナマイトでも1ターンのため、節約分は 0 です。
    # 節約できるターン数が 0 より大きいもの（H_i > 1）をリストに抽出します。
    savings = []
    for val in h:
        if val > 1:
            savings.append(val - 1)
    
    # 節約できるターン数が多い順にソートします。
    # ダイナマイトの使用回数 K に制限があるため、節約効率が良い岩から優先的に使います。
    savings.sort(reverse=True)
    
    # 最大で K 個のダイナマイトを使用し、節約できるターンの合計（最大削減量）を求めます。
    # Pythonのスライス savings[:k] は、k がリストの長さを超えていても適切に処理されます。
    max_reduction = sum(savings[:k])
    
    # 最小ターン数 = (ハンマーのみの合計ターン数) - (ダイナマイトによる最大削減量)
    print(total_hammer_turns - max_reduction)

if __name__ == '__main__':
    solve()

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