概要

\(N\) 種類の商品の中から、最大 \(K\) 回の購入機会を利用して獲得できるポイントの合計を最大化する問題です。各商品は一度しか購入できないという制約の下で、効率よくポイントを集める必要があります。

考察

この問題を解くための鍵は、「どの商品から優先的に購入すべきか」を考えることです。

合計ポイントを最大化するためには、単純にポイントが高い商品から順番に選んでいくのが最善です。このような、その場その場で最も得な選択を繰り返す手法を「貪欲法」と呼びます。

ただし、以下の2つの制約に注意する必要があります： 1. 購入回数の制限: 最大 \(K\) 回までしか購入できません。 2. 商品の種類の制限: 商品は \(N\) 種類しかありません。同じ商品は1回しか買えないため、たとえ \(K\) が \(N\) より大きくても、最大で \(N\) 個までしか購入できません。

したがって、実際に購入する個数は 「\(N\) と \(K\) の小さい方の値」 となります。

アルゴリズム

以下の手順で解を求めます。

1. データの読み込み: 商品数 \(N\)、購入機会 \(K\)、および各商品のポイント \(P_i\) を取得します。
2. ソート（並び替え）: 各商品のポイント \(P_i\) を、値が大きい順（降順）に並び替えます。
3. 個数の決定: 購入する商品の個数 num_to_buy を \(\min(N, K)\) として計算します。
4. 合計の算出: 並び替えたリストの先頭から num_to_buy 個分の要素を足し合わせます。

計算量

• 時間計算量: \(O(N \log N)\)
  • ポイントのリストをソートする工程がボトルネックとなります。\(N=2 \times 10^5\) の場合、\(O(N \log N)\) は十分に実行時間制限内に収まります。
• 空間計算量: \(O(N)\)
  • \(N\) 個の商品のポイントをリストに格納するために必要なメモリ量です。

実装のポイント

• ソートの順序: Pythonの sort() メソッドや sorted() 関数はデフォルトで昇順（小さい順）になるため、reverse=True を指定して降順にするか、ソート後にスライスを使って後ろから取得する必要があります。

• \(K > N\) のケース: 問題文の制約で \(K\) が \(N\) を超える可能性があるため、単純に \(K\) 個選ぼうとするとリストの範囲外を参照してしまう恐れがあります。min(n, k) を使う、あるいはスライスの特性（p[:k] は \(k\) が要素数を超えていてもエラーにならない）を利用することで安全に実装できます。

  ソースコード

import sys

def solve():
    # 標準入力からNとKを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    
    # ポイントのリストを読み込む
    p = list(map(int, input_data[2:]))
    
    # ポイントを降順（大きい順）にソートする
    p.sort(reverse=True)
    
    # 購入できる最大数は商品の種類数Nと購入機会Kの小さい方
    num_to_buy = min(n, k)
    
    # 上位 num_to_buy 個の合計を計算して出力する
    print(sum(p[:num_to_buy]))

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。