概要

「どの食材を入れ替えるか」を直接考えるのではなく、入れ替えによって料理全体のおいしさがどれだけ増減するかに注目する問題です。
各食材について増減量 \(B_i - A_i\) を計算し、その値が大きいものからちょうど \(K\) 個選べばよいです。

考察

まず、どの食材も入れ替えないとしたときの料理全体のおいしさは

\[ A_1 + A_2 + \cdots + A_N \]

です。

ここで、\(i\) 番目の食材を入れ替えると、その食材のおいしさは \(A_i\) から \(B_i\) に変わります。
つまり、料理全体のおいしさは

\[ B_i - A_i \]

だけ変化します。

この値を「入れ替えによる増減量」と考えると、問題は次のように言い換えられます。

• 最初の合計値は \(\sum A_i\)
• そこに、選んだ \(K\) 個の食材について増減量 \(B_i - A_i\) を足す
• 合計が最大になるように選ぶ

したがって、増減量が大きい食材から \(K\) 個選ぶのが最適です。

具体例

例えば

• \(A = [5, 3, 8, 4]\)
• \(B = [6, 10, 2, 7]\)
• \(K = 2\)

とすると、最初の合計は

\[ 5 + 3 + 8 + 4 = 20 \]

各食材の増減量は

• \(6 - 5 = 1\)
• \(10 - 3 = 7\)
• \(2 - 8 = -6\)
• \(7 - 4 = 3\)

なので

\[ [1, 7, -6, 3] \]

です。
この中から大きい順に \(2\) 個選ぶと \(7, 3\) なので、最大値は

\[ 20 + 7 + 3 = 30 \]

となります。

素朴な方法がだめな理由

「\(N\) 個の中から \(K\) 個選ぶ」方法を全部試すと、組合せの数は

\[ \binom{N}{K} \]

通りあり、\(N \leq 3 \times 10^5\) では到底間に合いません。

そこで、各食材を独立に見て「その食材を入れ替える価値」を \(B_i - A_i\) で表し、
価値の高いものを上から \(K\) 個取るという形に変換することで、効率よく解けます。

また、増減量が負のものがあっても問題ありません。
なぜなら、この問題では ちょうど \(K\) 個 入れ替えなければならないため、たとえ損をする食材があっても、その中でできるだけ損が少ないものを選ぶ必要があるからです。
「大きい順に \(K\) 個選ぶ」はこの条件にも自然に対応しています。

アルゴリズム

1. 元の料理全体のおいしさ \(base = \sum A_i\) を計算する
2. 各食材について増減量 \(diff_i = B_i - A_i\) を計算する
3. \(diff\) を大きい順にソートする
4. 上から \(K\) 個の和を \(base\) に足す
5. その値を出力する

コードに対応すると、次の部分です。

• base = sum(A)
  元の合計値
• diff = [b - a for a, b in zip(A, B)]
  各食材の増減量
• diff.sort(reverse=True)
  大きい順に並べる
• base + sum(diff[:K])
  上位 \(K\) 個を足して答えを作る

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 「最初の合計 + 増減量の上位 \(K\) 個」という形に整理すると実装しやすいです。

• 増減量には負の値もありえますが、ちょうど \(K\) 個選ぶのでそのまま上位 \(K\) 個を使えばOKです。

• \(A_i, B_i\) は負の値を含み、合計も大きくなる可能性がありますが、Python の整数なら安全に扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    base = sum(A)
    diff = [b - a for a, b in zip(A, B)]
    diff.sort(reverse=True)
    
    print(base + sum(diff[:K]))

if __name__ == "__main__":
    main()

---

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