概要

\(N\) 個の商品のうち最大 \(K\) 個にクーポンを使ってセール価格で購入できるとき、購入金額の合計を最小化する問題です。割引額が大きい商品から優先的にクーポンを使う貪欲法で解けます。

考察

重要な気づき

まず、各商品についてクーポンを使うと「どれだけお得になるか」を考えます。

商品 \(i\) にクーポンを使うと： - 通常価格 \(A_i\) 円 → セール価格 \(B_i\) 円

つまり、割引額 = \(A_i - B_i\) 円お得になります。

問題の言い換え

全商品を通常価格で買うと、合計は \(\sum_{i=1}^{N} A_i\) 円です。

ここから、クーポンを使った商品について割引額だけ安くなります。

したがって、購入金額を最小化する = 割引額の合計を最大化する と言い換えられます。

貪欲法の正当性

割引額が大きい商品からクーポンを使えば、割引額の合計が最大になります。

具体例：\(N = 3\), \(K = 2\) の場合

商品	通常価格 \(A_i\)	セール価格 \(B_i\)	割引額 \(A_i - B_i\)
1	100	80	20
2	200	120	80
3	150	140	10

• 通常価格の合計：\(100 + 200 + 150 = 450\) 円
• 割引額が大きい順：商品2（80円）、商品1（20円）、商品3（10円）
• 上位 \(K=2\) 個の割引額合計：\(80 + 20 = 100\) 円
• 最小購入金額：\(450 - 100 = 350\) 円

アルゴリズム

1. 各商品の通常価格 \(A_i\) をすべて合計して total_normal を計算する
2. 各商品の割引額 \(A_i - B_i\) をリストに格納する
3. 割引額を大きい順（降順）にソートする
4. 上位 \(K\) 個の割引額を合計して total_discount を計算する
5. 答えは total_normal - total_discount

最小購入金額 = 全商品の通常価格合計 - 上位K個の割引額合計

計算量

• 時間計算量: \(O(N \log N)\)
  • 入力の読み込み：\(O(N)\)
  • ソート：\(O(N \log N)\)
  • 上位 \(K\) 個の合計：\(O(K) \leq O(N)\)
• 空間計算量: \(O(N)\)
  • 割引額を格納するリスト

実装のポイント

1. 割引額の計算：\(B_i \leq A_i\) という制約があるため、割引額 \(A_i - B_i\) は必ず \(0\) 以上になります。割引額が \(0\) の商品にクーポンを使っても損にはなりません。

2. 降順ソート：sort(reverse=True) で割引額が大きい順に並べ替えます。

3. スライスで上位K個を取得：discounts[:K] で先頭から \(K\) 個を取り出せます。\(K\) がリストの長さより大きくても、Pythonではエラーにならず正しく動作します。

4. オーバーフローに注意：\(A_i\) は最大 \(10^9\)、\(N\) は最大 \(2 \times 10^5\) なので、合計は最大 \(2 \times 10^{14}\) 程度になります。Pythonでは整数のオーバーフローを気にする必要はありませんが、他の言語では64ビット整数型を使う必要があります。

   ソースコード

def solve():
    N, K = map(int, input().split())
    
    # 各商品について、クーポンを使った場合の割引額を計算
    # 割引額 = A_i - B_i
    discounts = []
    total_normal = 0
    
    for _ in range(N):
        A, B = map(int, input().split())
        total_normal += A
        discounts.append(A - B)
    
    # 割引額が大きい順にソートして、上位K個を選ぶ
    discounts.sort(reverse=True)
    
    # 上位K個の割引額の合計を計算
    total_discount = sum(discounts[:K])
    
    # 最小購入金額 = 全商品の通常価格合計 - 選んだ商品の割引額合計
    print(total_normal - total_discount)

solve()

---

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