概要

各お菓子の満足度（基本の美味しさ + 好み補正値）を計算し、上位 \(K\) 個の満足度の合計を求める問題です。

考察

重要な気づき

この問題のポイントは非常にシンプルです：

1. 各お菓子の満足度は独立に計算できる: お菓子 \(i\) の満足度は \(T_i + C_i\) で、他のお菓子の選択に影響されません
2. 貪欲法が最適: 満足度の合計を最大化するには、単純に満足度が高いものから順に \(K\) 個選べばよい

具体例で考える

例えば、\(N = 4\)、\(K = 2\) で以下のお菓子があるとします：

お菓子	\(T_i\)	\(C_i\)	満足度 \(T_i + C_i\)
1	10	5	15
2	8	-3	5
3	20	-5	15
4	3	10	13

満足度を降順に並べると：15, 15, 13, 5

上位 \(K = 2\) 個を選ぶと、満足度 15 と 15 のお菓子を選び、合計は \(15 + 15 = 30\) となります。

素朴なアプローチについて

この問題では、素朴な「全ての \(K\) 個の組み合わせを試す」アプローチは不要です。 - 組み合わせを全列挙すると \(O(\binom{N}{K})\) となり、\(N\) が大きいと TLE になります - しかし、ソートして上位 \(K\) 個を選ぶだけで最適解が得られるため、その必要はありません

アルゴリズム

1. 満足度の計算: 各お菓子 \(i\) について、満足度 \(T_i + C_i\) を計算してリストに格納する
2. ソート: 満足度のリストを降順（大きい順）にソートする
3. 上位K個の合計: ソート後のリストの先頭から \(K\) 個の要素を取り出し、その合計を計算する

入力: N=4, K=2, お菓子の情報
↓
満足度リスト: [15, 5, 15, 13]
↓ ソート（降順）
[15, 15, 13, 5]
↓ 上位K個を選択
[15, 15]
↓ 合計
出力: 30

計算量

• 時間計算量: \(O(N \log N)\)

  • 満足度の計算: \(O(N)\)
  • ソート: \(O(N \log N)\)
  • 上位 \(K\) 個の合計: \(O(K)\)（\(K \leq N\) なので \(O(N)\)）
  • 全体として \(O(N \log N)\) が支配的

• 空間計算量: \(O(N)\)

  • 満足度を格納するリストに \(N\) 個の要素を保持

実装のポイント

1. オーバーフローに注意: \(T_i\) と \(C_i\) の範囲から、満足度は最大で約 \(2 \times 10^9\) になります。\(K\) 個の合計は最大で約 \(4 \times 10^{14}\) となりますが、Python では整数のオーバーフローを気にする必要はありません（C++ などでは long long を使う必要があります）

2. 降順ソート: sort(reverse=True) を使うことで、大きい順にソートできます

3. スライスの活用: Python では satisfactions[:K] で先頭 \(K\) 個を簡単に取り出せます

   ソースコード

def main():
    N, K = map(int, input().split())
    satisfactions = []
    for _ in range(N):
        T, C = map(int, input().split())
        satisfactions.append(T + C)
    
    # 満足度を降順にソートして上位K個の合計を求める
    satisfactions.sort(reverse=True)
    print(sum(satisfactions[:K]))

if __name__ == "__main__":
    main()

---

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