概要

\(N\) 個のお土産から \(K\) 個を諦めて残りを持ち帰るとき、持ち帰るお土産の満足度の合計を最大化する問題。

考察

この問題の目的は、持ち帰るお土産の満足度の合計を最大化することです。言い換えれば、諦めるお土産の満足度の合計を最小化すればよいということになります。

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

例えば、すべての組み合わせの中から \(K\) 個を選ぶ方法を全探索すると、組み合わせの数は \({}_N C_K\) となり、非常に大きな計算量になってしまいます。特に \(N\) が最大で \(2 \times 10^5\) あるため、現実的ではありません。

解決策

実は、満足度の高いお土産は持ち帰りたいので、満足度が低い \(K\) 個をお土産を諦めるのが最適です。

したがって、以下のような手順で解くことができます： 1. すべてのお土産を満足度の高い順に並べる（降順ソート）。 2. 上位 \((N - K)\) 個の満足度の合計を取れば、それが持ち帰るお土産の最大満足度の合計となる。

例

例えば、次のような入力があるとします：

N = 5, K = 2
D = [3, 1, 4, 1, 5]

これを降順にソートすると：

[5, 4, 3, 1, 1]

上位 \(N - K = 3\) 個の合計は \(5 + 4 + 3 = 12\) であり、これが答えになります。

アルゴリズム

1. お土産の満足度リスト \(D\) を降順にソートする。
2. 先頭から \((N - K)\) 個の要素の和を計算する。
3. その和を出力する。

計算量

• 時間計算量: \(O(N \log N)\) （ソートに支配される）
• 空間計算量: \(O(N)\) （入力配列の記憶領域）

実装のポイント

• Pythonでは sort(reverse=True) を使うことで簡単に降順ソートができる。

• スライス D[:N - K] を使って上位 \((N - K)\) 個を取り出すことができる。

• 合計値は sum() 関数で求められる。

  ソースコード

# 入力の受け取り
N, K = map(int, input().split())
D = list(map(int, input().split()))

# 満足度を降順にソート
D.sort(reverse=True)

# 上位(N - K)個の合計が答え
answer = sum(D[:N - K])

# 出力
print(answer)

---

この解説は qwen3-coder-480b によって生成されました。