概要

ハンマーだけで壊すと \(H_i\) ターンかかる各岩について、ダイナマイト（1ターンで破壊）をどの岩に使うと総ターン数が最小になるかを求める問題です。

考察

各岩を壊す方法は実質的に次の2通りです。

• ハンマーのみ：岩 \(i\) に \(H_i\) 回叩くので \(H_i\) ターン
• ダイナマイト使用：一撃で壊すので \(1\) ターン

したがって、岩 \(i\) にダイナマイトを使うと、ハンマーのみと比べて \( H_i - 1 \) ターン短縮できます（これが「得」）。

ここで重要なのは、岩は順番に処理する必要があるものの、どの岩にダイナマイトを使うかの選択は他の岩に影響しないという点です。
なぜなら、どの岩も「その岩を壊すのに必要なターン数」が独立に決まり、総ターン数は単純な合計になるからです。

よって最小化したい総ターン数は、

• まず全てハンマーで壊すと \(\sum H_i\) ターン
• そこから、ダイナマイトを使った岩については \(H_i\) を \(1\) に置き換える（＝ \(H_i-1\) だけ減る）

つまり、「短縮できるターン数 \(H_i-1\) が大きい岩ほど、ダイナマイトを使う価値が高い」です。
\(H_i-1\) の大小は \(H_i\) の大小と同じなので、硬度 \(H_i\) が大きい岩から順に最大 \(K\) 個選んでダイナマイトを使うのが最適です（貪欲法）。

素朴案がダメな理由

各ターンをシミュレーションすると、最大で \(\sum H_i\) 回の操作になり得ますが、\(H_i \le 10^9\) なので到底間に合いません。
この問題は「1ターンずつ減らす」必要はなく、各岩のコストが \(H_i\) か \(1\) かを選ぶだけに言い換えることで高速化できます。

具体例

例えば \(H=[5,2,4],\ K=1\) のとき：

• 全ハンマー：\(5+2+4=11\) ターン
• ダイナマイトをどれか1つに使う：
  • \(5\) に使うと \(11-(5-1)=7\)
  • \(4\) に使うと \(11-(4-1)=8\)
  • \(2\) に使うと \(11-(2-1)=10\)

最大の硬度 \(5\) に使うのが最適です。

アルゴリズム

1. \(total = \sum_{i=1}^{N} H_i\) を計算する（全てハンマーの場合のターン数）。
2. \(H\) を降順ソートする。
3. 上位 \(K\) 個の合計 \(sum\_k = \sum_{i=1}^{K} H_i\) を取る。
4. 上位 \(K\) 個は「\(H_i\) ターン」から「\(1\) ターン」になるので、総ターン数は \(total - sum\_k + K\) となる。
   • \(-sum\_k\)：本来かかる \(H_i\) を引く
   • \(+K\)：ダイナマイトは各1ターンなので足す

※ \(K=0\) のときはそのまま \(total\) を出力。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（配列保持）

実装のポイント

• 「得する量 \(H_i-1\) を最大化」≒「\(H_i\) の大きい順に選ぶ」なので、降順ソートして先頭 \(K\) 個を使うだけでよいです。
• \(H_i\) や \(\sum H_i\) は大きくなり得ますが、Python の int は任意精度なのでオーバーフローの心配はありません。

ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    total = sum(H)
    if K == 0:
        print(total)
        return
    H.sort(reverse=True)
    sum_k = sum(H[:K])
    ans = total - sum_k + K
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。