概要

\(N\) 個の食材からちょうど \(K\) 個を選んで代わりの食材に入れ替えるとき、食材のおいしさの総和を最大化する問題です。各食材について「入れ替えたときの利得」を計算し、利得が大きい順に \(K\) 個選ぶ貪欲法で解けます。

考察

問題の言い換え

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

ここで \(i\) 番目の食材を入れ替えると、おいしさの変化量（利得）は次のようになります：

\[d_i = B_i - A_i\]

• \(d_i > 0\) なら、入れ替えるとおいしさが増える
• \(d_i < 0\) なら、入れ替えるとおいしさが減る
• \(d_i = 0\) なら、変化なし

ちょうど \(K\) 個を入れ替えなければならないので、最終的なおいしさは次のように表せます：

\[\sum_{i=1}^{N} A_i + \sum_{i \in S} d_i\]

ここで \(S\) は入れ替える \(K\) 個の食材の集合です。

最大化の方針

\(\sum A_i\) は固定なので、\(\sum_{i \in S} d_i\)（選んだ \(K\) 個の利得の合計）を最大化すればよいです。

これは単純に \(d_i\) を降順ソートして、上位 \(K\) 個を選べば最大になります。

注意点

「ちょうど \(K\) 個」を入れ替えなければならないため、たとえ利得が負であっても \(K\) 個選ぶ必要があります。例えば \(N=3, K=2\) で \(d = [5, -1, -3]\) なら、\(d_1 = 5\) と \(d_2 = -1\) の2つを選び、合計利得は \(5 + (-1) = 4\) となります。

具体例

\(N=3, K=2, A=[10, 20, 30], B=[15, 5, 35]\) の場合：

• \(d = [15-10, \ 5-20, \ 35-30] = [5, -15, 5]\)
• 降順ソート: \([5, 5, -15]\)
• 上位 \(K=2\) 個の合計: \(5 + 5 = 10\)
• 答え: \((10+20+30) + 10 = 70\)

アルゴリズム

1. \(A\) の総和 \(\text{total} = \sum_{i=1}^{N} A_i\) を計算する。
2. 各 \(i\) について利得 \(d_i = B_i - A_i\) を計算する。
3. \(d_i\) を降順にソートする。
4. 上位 \(K\) 個の \(d_i\) を \(\text{total}\) に加算する。
5. 結果を出力する。

計算量

• 時間計算量: \(O(N \log N)\)（ソートがボトルネック）
• 空間計算量: \(O(N)\)（利得の配列を保持）

実装のポイント

• おいしさ \(A_i, B_i\) の値が \(-10^9\) から \(10^9\) まであり、\(N\) が最大 \(3 \times 10^5\) なので、総和は最大で約 \(3 \times 10^{14}\) 程度になります。Python は多倍長整数を扱えるためオーバーフローの心配はありませんが、C++ などでは long long を使う必要があります。

• 「ちょうど \(K\) 個入れ替えなければならない」という制約を見落とさないようにしましょう。利得が負でも選ばなければならない場合があります。

• sys.stdin.read() でまとめて入力を読み込むことで、Python でも高速に入力を処理できます。

  ソースコード

def main():
    import sys
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    # diff[i] = B[i] - A[i], the gain from swapping ingredient i
    # We want to choose exactly K ingredients to swap to maximize sum(A) + sum of K chosen diffs
    # To maximize, we sort diffs in descending order and pick the top K
    # But we MUST pick exactly K, so even if some diffs are negative, we must pick them
    
    total = sum(A)
    diffs = [B[i] - A[i] for i in range(N)]
    diffs.sort(reverse=True)
    total += sum(diffs[:K])
    print(total)

main()

---

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