概要

ポイントが最も高い商品から \(K\) 個選んで合計すれば、獲得できるポイントの最大値を求めることができる。

考察

この問題では、高橋君が \(K\) 回の購入機会を使って、合計ポイントを最大化したいと考えています。
ただし、同じ商品は一度しか買えないという制約があります。

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

例えば、すべての商品の組み合わせの中から \(K\) 個を選ぶ組み合わせを全探索する方法が考えられますが、
これは \(_N C_K\) 通りあり、\(N\) が最大 \(2 \times 10^5\) なので、現実的ではありません（時間的に非常にかかる）。

解法の核心：貪欲法

実は、この問題は「貪欲法（greedy algorithm）」を用いることで効率的に解くことができます。
つまり、「毎回最もポイントの高い商品を選ぶ」という戦略が最適になります。
なぜなら、獲得できるポイントの合計を最大化するためには、できるだけ多くの高得点商品を選びたいからです。
また、同じ商品は買えないため、上位 \(K\) 個の商品を一つずつ選ぶのが最適です。

具体例

例えば、以下のような入力があったとします：

N = 5, K = 3
P = [10, 20, 5, 15, 25]

ポイントを降順に並べ替えると：

[25, 20, 15, 10, 5]

上位3つの合計は \(25 + 20 + 15 = 60\) となり、これが最大値です。

アルゴリズム

1. 商品のポイントリスト \(P\) を読み込む。
2. ポイントを降順にソートする。
3. ソートされたリストの先頭 \(K\) 個の要素を取り出し、その合計を求める。
4. 合計を出力する。

計算量

• 時間計算量: \(O(N \log N)\) （ソートに dominate）
• 空間計算量: \(O(N)\) （入力リストの保持）

実装のポイント

• sort(reverse=True) を使うことで簡単に降順ソートができる。
• sum(P[:K]) で先頭 \(K\) 個の和を高速に求められる。
• 入力の受け取り時に map(int, ...) を忘れずに。

## ソースコード

```python
# 入力受け取り
N, K = map(int, input().split())
P = list(map(int, input().split()))

# ポイントが高い順にソート
P.sort(reverse=True)

# 上位K個のポイントを合計
answer = sum(P[:K])

# 出力
print(answer)

---

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