概要

各商品の獲得ポイント \(P_i\) が与えられたとき、同じ商品は1回まで・購入回数は最大 \(K\) 回という条件で、合計ポイントを最大化します。

考察

• 1回の購入で得られるポイントは商品ごとに固定で、購入同士の相互作用（割引や倍率など）はありません。
• さらに「同じ商品は最大1回」という制約があるので、結局 高得点の商品から順に最大 \(K\) 個まで選ぶ のが最適です。

具体例： - \(P = [10, 3, 8, 5]\), \(K = 2\) のとき
高い順に並べると \([10, 8, 5, 3]\) なので、上位2つの \(10 + 8 = 18\) が最大です。
これ以外（例: \(10 + 5 = 15\)）は必ず小さくなります。

素朴に「どの商品を買うか」を全探索すると、組合せは \(\binom{N}{K}\) 通りにもなり、\(N \le 2 \times 10^5\) では現実的ではありません（TLE）。
この問題は選択に迷う必要がなく、「上位を取る」だけで決まるのが重要な観察です。

また、\(K\) が \(N\) より大きい場合でも、買える商品は最大 \(N\) 個なので、実際に選べる個数は \(k = \min(N, K)\) 個です。

アルゴリズム

1. 配列 \(P\) を降順（大きい順）にソートする。
2. \(k = \min(N, K)\) とする。
3. ソート後の先頭 \(k\) 個の合計 \(\sum_{i=1}^{k} P_i\) を出力する。

降順に並べたとき、先頭から \(k\) 個は「取りうる \(k\) 個の集合の中で合計が最大」になるため、これが最適解です。

計算量

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

実装のポイント

• \(K > N\) のケースに注意し、\(k=\min(N,K)\) として先頭 \(k\) 個を足します。

• \(P_i\) は最大 \(10^9\)、\(N\) も大きいので合計は大きくなりますが、Python の int は任意精度なのでオーバーフローの心配はありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    P.sort(reverse=True)
    k = min(N, K)
    print(sum(P[:k]))

if __name__ == "__main__":
    main()

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