概要

\(N\) 個の商品すべてを購入する際に、最大 \(K\) 個の商品を無料にできるクーポンを使って、支払う合計金額を最小化する問題です。

考察

重要な気づき

クーポンを使うと商品を \(0\) 円にできるので、高い商品にクーポンを使うほどお得です。

例えば、商品の価格が \([100, 300, 200, 500]\) で \(K = 2\) の場合を考えましょう： - 価格の高い順に並べると：\(500, 300, 200, 100\) - クーポンを使うべき商品：\(500\) 円と \(300\) 円の商品（上位2つ） - 支払う金額：\(200 + 100 = 300\) 円

もし安い商品（\(100\) 円と \(200\) 円）にクーポンを使ってしまうと、支払いは \(500 + 300 = 800\) 円になり、損をします。

なぜ貪欲法で良いのか

この問題では「\(K\) 個以下の商品を無料にできる」という単純な制約しかありません。商品間に依存関係がないため、単純に価格が高い順に \(K\) 個選んでクーポンを適用するという貪欲法が最適解を与えます。

素朴なアプローチとの比較

すべての商品の組み合わせを試すと、\(N\) 個から \(K\) 個を選ぶ組み合わせ \(\binom{N}{K}\) 通りを調べる必要があり、\(N\) や \(K\) が大きいと計算量が爆発してTLE（時間超過）になります。

貪欲法を使えば、ソートするだけで最適解が求まります。

アルゴリズム

1. 商品の価格リスト \(D\) を降順（高い順）にソートする
2. ソート後、先頭から \(K\) 個の商品にクーポンを適用する（これらは \(0\) 円になる）
3. 残りの商品（インデックス \(K\) 以降）の価格の合計を計算して出力する

ソート後: D[0], D[1], ..., D[K-1], D[K], D[K+1], ..., D[N-1]
          ~~~~~~~~~~~~~~~~~~~~    ~~~~~~~~~~~~~~~~~~~~~~~~~~~
          クーポン適用（0円）       支払う商品（合計を求める）

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 合計の計算に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 価格リストの保持に \(O(N)\)

実装のポイント

1. 降順ソート: D.sort(reverse=True) で価格を高い順に並べる

2. スライスで合計計算: D[K:] は「インデックス \(K\) 以降の要素すべて」を表すPythonのスライス記法。これで「クーポンを使わない商品」を簡潔に取得できる

3. \(K = N\) の場合: すべての商品にクーポンを適用できるので、D[N:] は空リストとなり、sum([]) は \(0\) を返す。特別な場合分けは不要

4. オーバーフローに注意: \(D_i\) は最大 \(10^9\)、\(N\) は最大 \(2 \times 10^5\) なので、合計は最大 \(2 \times 10^{14}\) 程度。Pythonでは整数のオーバーフローがないため問題ないが、他の言語では64ビット整数型を使う必要がある

   ソースコード

N, K = map(int, input().split())
D = list(map(int, input().split()))

D.sort(reverse=True)
print(sum(D[K:]))

---

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