概要

\(N\) 種類のお菓子の中から \(K\) 個を選び、それらの「満足度」（基本の美味しさ \(T_i\) + 好み補正値 \(C_i\)）の合計を最大化する問題です。

考察

この問題で最も重要なポイントは、各お菓子の評価値が \(T_i\) と \(C_i\) の和という単一の数値で決まるという点です。

高橋君は合計の満足度を最大化したいと考えています。あるお菓子 \(i\) を選んだときに得られる満足度は \(S_i = T_i + C_i\) と計算できます。 複数の項目からいくつかを選んでその合計を最大化する場合、「単体での値が大きいものから順番に選ぶ」という貪欲な戦略が最適となります。

例えば、以下のようなお菓子がある場合を考えます（\(K=2\)）： - お菓子1: \(T_1=10, C_1=5 \Rightarrow S_1=15\) - お菓子2: \(T_2=20, C_2=-10 \Rightarrow S_2=10\) - お菓子3: \(T_3=5, C_3=15 \Rightarrow S_3=20\)

この場合、満足度 \(S_i\) は順に \(15, 10, 20\) となります。合計を最大にするには、満足度が高い「お菓子3 (20)」と「お菓子1 (15)」の 2 つを選ぶのがベストです。

したがって、以下の手順で解くことができます： 1. すべてのお菓子について、満足度 \(S_i = T_i + C_i\) を計算する。 2. 計算した満足度を値の大きい順（降順）に並べ替える。 3. 上位 \(K\) 個の満足度を合計する。

アルゴリズム

1. 入力の受け取り: \(N, K\) および各お菓子の \(T_i, C_i\) を読み込みます。
2. 満足度の計算: 各 \(i\) について \(S_i = T_i + C_i\) を計算し、リストに格納します。
3. ソート: リストを降順（大きい順）にソートします。
4. 合計の算出: ソートされたリストの先頭から \(K\) 個の要素の和を求め、出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 満足度の計算に \(O(N)\)、ソートに \(O(N \log N)\)、上位 \(K\) 個の合計計算に \(O(K)\) かかります。全体ではソートの計算量が支配的になります。\(N = 2 \times 10^5\) であるため、この計算量で制限時間内に十分間に合います。
• 空間計算量: \(O(N)\)
  • \(N\) 個のお菓子の満足度を保持するためのリストが必要です。

実装のポイント

• 高速な入力: \(N\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() を使って一括で入力を読み込むと処理が高速になります。

• ソートの順序: sort(reverse=True) を指定することで、簡単に大きい順に並べ替えることができます。

• スライスと合計: sum(satisfactions[:K]) のようにスライスを用いることで、上位 \(K\) 個の合計を簡潔に記述できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白（スペースや改行）で分割してリストにします
    # 競技プログラミングにおいて、大量の入力を高速に処理する一般的な手法です
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します
    if not input_data:
        return
    
    # 文字列のリストを整数のリストに一括変換します
    # map関数をlistで包むことで、高速に変換処理が行われます
    data = list(map(int, input_data))
    
    # 1つ目の要素が種類数 N、2つ目の要素が選ぶ個数 K です
    N = data[0]
    K = data[1]
    
    # 各お菓子の満足度（T_i + C_i）を計算します
    # T_i と C_i のペアはインデックス2から始まります
    # i番目のお菓子の T_i は data[2 + 2*i]、C_i は data[3 + 2*i] に位置します
    satisfactions = [data[i] + data[i+1] for i in range(2, 2 * N + 2, 2)]
    
    # 満足度が高い順にお菓子を選ぶため、降順（大きい順）にソートします
    satisfactions.sort(reverse=True)
    
    # 上位 K 個の満足度の合計を計算して出力します
    # Pythonのスライス（[:K]）とsum関数を組み合わせることで効率的に合計を求められます
    print(sum(satisfactions[:K]))

if __name__ == '__main__':
    solve()

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