概要

\(N\) 個の食材のうち、ちょうど \(K\) 個を代わりの食材に入れ替えて、おいしさの総和を最大化する問題です。入れ替えによる「おいしさの変化量」に着目することで、効率的に最適な組み合わせを見つけることができます。

考察

まず、入れ替えを行わない場合の料理全体のおいしさは \(\sum_{i=1}^{N} A_i\) です。

ある食材 \(i\) を入れ替えると、その食材のおいしさは \(A_i\) から \(B_i\) に変わります。このとき、料理全体のおいしさは次のように変化します。 - 変化量：\(D_i = B_i - A_i\) - 入れ替え後の総和：(元の総和) \(+ D_i\)

例えば、\(A_i = 10, B_i = 15\) なら変化量は \(+5\) です。逆に \(A_i = 10, B_i = 7\) なら変化量は \(-3\) となります。

本問題では「ちょうど \(K\) 個」を入れ替える必要があるため、料理全体のおいしさを最大化するには、変化量 \(D_i\) が大きいものから順に \(K\) 個選んで入れ替えるのが最善です。変化量が負（入れ替えるとおいしさが減る）であっても、ちょうど \(K\) 個選ぶというルールのために、上位 \(K\) 個に含まれるのであれば入れ替えなければなりません。

アルゴリズム

1. すべての食材 \(i = 1, \ldots, N\) について、入れ替えた際の変化量 \(D_i = B_i - A_i\) を計算します。
2. 計算した \(N\) 個の変化量を、値が大きい順（降順）にソートします。
3. 元のおいしさの総和 \(\sum A_i\) に、ソートした変化量のうち先頭 \(K\) 個の和を加算します。
   • 数式で表すと：最大値 \(= \sum_{i=1}^{N} A_i + (\text{上位 } K \text{ 個の } D_i \text{ の和})\)

計算量

\(N\) を食材の数とします。 - 時間計算量: \(O(N \log N)\) - 変化量の計算に \(O(N)\)、ソートに \(O(N \log N)\)、合計の計算に \(O(N)\) かかるため、全体の計算量はソートが支配的になります。 - \(N = 3 \times 10^5\) の場合、制限時間内に十分間に合います。 - 空間計算量: \(O(N)\) - 入力データ（\(A_i, B_i\)）と変化量（\(D_i\)）を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が最大 \(3 \times 10^5\) と比較的大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• ソートの順序: 変化量の大きいものから選びたいため、sort(reverse=True) を指定するか、昇順でソートした後に後ろから \(K\) 個取るようにします。

• ちょうど K 個: もし「最大 \(K\) 個」という条件であれば変化量が正のものだけを選べばよいですが、今回は「ちょうど \(K\) 個」なので、必ず \(K\) 個選ぶ処理にします。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 食材の数 N と入れ替える食材の数 K を取得
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 現在の食材のおいしさ A_i と入れ替え後の食材のおいしさ B_i を取得
    # input_data[2...n+1] が A_1...A_n
    # input_data[n+2...2n+1] が B_1...B_n
    a = list(map(int, input_data[2:n+2]))
    b = list(map(int, input_data[n+2:2*n+2]))
    
    # 各食材を入れ替えたときのおいしさの変化量 (B_i - A_i) を計算
    diffs = [b[i] - a[i] for i in range(n)]
    
    # 変化量を降順（大きい順）にソート
    # 料理全体のおいしさを最大化するためには、変化量が大きいものから K 個選んで入れ替える
    diffs.sort(reverse=True)
    
    # 元のおいしさの総和に、上位 K 個の変化量を加算することで最大のおいしさを求める
    # ちょうど K 個入れ替えるという条件があるため、上位 K 個をそのまま合計する
    ans = sum(a) + sum(diffs[:k])
    
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

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