概要

各食材を入れ替えるかどうかは独立に考えられ、入れ替えによる「増減量」\(B_i - A_i\) が大きいものからちょうど \(K\) 個選べば、全体のおいしさを最大化できます。

考察

最終的なおいしさの合計を式で書くと、次のように分解できます。

• まず全食材を入れ替えないときの合計：\(\sum A_i\)
• 食材 \(i\) を入れ替えたときの変化量：\(B_i - A_i\)

したがって、入れ替える集合を \(S\)（\(|S|=K\)）とすると、

[ \text{総おいしさ} = \sum Ai + \sum{i \in S}(B_i - A_i) ]

ここで \(\sum A_i\) はどの選び方でも一定なので、最大化すべきは
[ \sum_{i \in S}(B_i - A_i) ] です。
つまり「差分 \(d_i = B_i - A_i\) が大きいものを \(K\) 個選ぶ」問題になります。

素朴な方法がだめな理由

「\(N\) 個から \(K\) 個選ぶ」組合せを全探索すると、場合の数は \(\binom{N}{K}\) で非常に大きく、\(N \le 3 \times 10^5\) では到底間に合いません。

どう解決するか

差分配列 \(d_i\) を作って降順にソートし、上位 \(K\) 個を足せばよいです。
負の差分しかなくても「ちょうど \(K\) 個」選ぶ必要があるため、その場合は（損をしつつも）上位 \(K\) 個を選ぶのが最善です。

例えば
\(A=[5,1,4],\ B=[6,-2,10],\ K=2\) のとき
差分は \([1,-3,6]\)。降順で \([6,1,-3]\) なので上位2つは \(6,1\)。
基準合計 \(\sum A_i=10\) だから答えは \(10+6+1=17\)。

アルゴリズム

1. \(A\) の総和 base = sum(A) を求める。
2. 各 \(i\) について差分 diffs[i] = B_i - A_i を作る。
3. diffs を降順ソートする。
4. base + sum(diffs[:K]) を出力する。

計算量

• 時間計算量: \(O(N \log N)\)（差分のソート）
• 空間計算量: \(O(N)\)（差分配列）

実装のポイント

• 制約的に合計値は大きくなる可能性がありますが、Python の int ならオーバーフローを気にせず扱えます。

• 入力が大きいので sys.stdin.readline を使うと高速です。

• zip(A, B) を使うと B_i - A_i を簡潔に書けます。

  ソースコード

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)
    diffs = [b - a for a, b in zip(A, B)]
    diffs.sort(reverse=True)

    ans = base + sum(diffs[:K])
    print(ans)

if __name__ == "__main__":
    main()

---

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