概要

\(N\) 個のお土産からちょうど \(K\) 個を捨てるとき、残りの満足度合計を最大にするには「満足度が低いものから \(K\) 個捨てる」のが最適です。

考察

持ち帰る個数は \(N-K\) 個で固定なので、合計満足度を最大化するには「捨てる満足度の合計」を最小化すればよい、と言い換えられます。

• もし満足度が高いお土産を捨ててしまうと、その分だけ合計が大きく減ります。
• 逆に、満足度が低いお土産を捨てれば、合計の減少を最小限にできます。

より形式的には、捨てる集合に「大きい値」と「小さい値」が混ざっているとき、大きい値を残して小さい値を捨てるように入れ替えると、持ち帰る合計は増える（または変わらない）ため、最終的に「捨てるのは小さいものから \(K\) 個」が最適になります。

素朴な方法がダメな理由

「どの \(K\) 個を捨てるか」を全探索すると、組合せは \(\binom{N}{K}\) 通りあり、\(N \le 2 \times 10^5\) では到底計算できません（TLE）。

具体例

例えば \(D = [6, 2, 9, 4]\)、\(K=2\) のとき： - 小さい方から \(2\) 個（\(2,4\)）を捨てる → 残りは \(6+9=15\) - もし \(6,2\) を捨てる → 残りは \(4+9=13\)（小さくなる）

よって「小さいものを捨てる」が正しい方針です。

アルゴリズム

1. 満足度配列 \(D\) を昇順にソートする。
2. 先頭から \(K\) 個が「捨てるお土産」（最小の \(K\) 個）になる。
3. 残り（添字 \(K\) 以降）の合計 \(\sum_{i=K}^{N-1} D_i\) を出力する。

これで「捨てる満足度の合計」が最小になり、結果として「持ち帰る満足度の合計」が最大になります。

計算量

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

実装のポイント

• \(N\) が大きいので、入力は sys.stdin.buffer.read() でまとめて読むと高速です。

• 満足度の合計は最大で \(10^9 \times 2\times 10^5 = 2\times 10^{14}\) 程度になり得ますが、Python の int は多倍長なのでそのまま sum して問題ありません。

• ソート後に sum(D[K:]) とすることで、捨てる \(K\) 個を除いた合計を簡潔に計算できます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    D = data[2:2+N]
    D.sort()
    print(sum(D[K:]))

if __name__ == "__main__":
    main()

---

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