概要

\(N\) 個のお土産から \(K\) 個を諦めて残りを持ち帰るとき、持ち帰るお土産の満足度の合計を最大化する問題です。これは「満足度が高い方から \(N-K\) 個を選ぶ」という貪欲法で解けます。

考察

問題の言い換え

「\(K\) 個を諦める」ということは、「\(N-K\) 個を持ち帰る」ということです。

持ち帰るお土産の満足度の合計を最大化したいので、問題は次のように言い換えられます：

\(N\) 個のお土産から \(N-K\) 個を選んで、満足度の合計を最大化せよ

重要な気づき

合計を最大化するには、満足度が大きいものから順に選ぶのが最善です。

例えば、\(N = 5\), \(K = 2\) で満足度が \([3, 1, 4, 1, 5]\) の場合を考えます。 - 持ち帰れるのは \(N - K = 3\) 個 - 満足度を大きい順に並べると \([5, 4, 3, 1, 1]\) - 上位 \(3\) 個を選ぶと \(5 + 4 + 3 = 12\)

これが最大値になります。逆に言えば、諦めるのは満足度が小さい方から \(K\) 個（この例では \(1, 1\)）を選ぶのが最善です。

なぜ貪欲法で正しいか

満足度はすべて正の値（\(D_i \geq 1\)）なので、選べるなら満足度が高いものを選んだ方が必ず得です。選ぶ個数が固定（\(N-K\) 個）なので、単純に上位を選ぶだけで最適解が得られます。

アルゴリズム

1. 入力を受け取る（\(N\), \(K\), 満足度の配列 \(D\)）
2. 配列 \(D\) を満足度の降順（大きい順）にソートする
3. ソート後の配列の先頭から \(N-K\) 個の要素の合計を求める
4. その合計を出力する

具体例での動作

入力: \(N = 4\), \(K = 1\), \(D = [10, 30, 20, 40]\)

1. 降順ソート: \(D = [40, 30, 20, 10]\)
2. 上位 \(N-K = 3\) 個を選ぶ: \(40, 30, 20\)
3. 合計: \(40 + 30 + 20 = 90\)

出力: 90

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 合計の計算に \(O(N-K) \subseteq O(N)\)
• 空間計算量: \(O(N)\)
  • 満足度を格納する配列のサイズ

実装のポイント

• Pythonでは sort(reverse=True) で降順ソートができます

• スライス D[:N-K] で先頭から \(N-K\) 個の要素を取得できます

• sum() 関数でリストの合計を簡単に計算できます

• \(K\) 個を「諦める」という問題文に惑わされず、「\(N-K\) 個を選ぶ」と読み替えることが大切です

  ソースコード

def solve():
    N, K = map(int, input().split())
    D = list(map(int, input().split()))
    
    # K個を諦めるので、N-K個を持ち帰る
    # 満足度の合計を最大化するには、満足度が高い順にN-K個選べばよい
    
    D.sort(reverse=True)
    
    # 上位N-K個の合計を求める
    result = sum(D[:N-K])
    
    print(result)

solve()

---

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