概要

店にあるフルーツ \(N\) 個と新しく届いたフルーツ \(M\) 個をまとめて考え、甘さが大きい順に \(K\) 個選んだときの合計を求める問題です。

つまり、\(N+M\) 個の数の中から「大きいもの上位 \(K\) 個の和」を求めればよいです。

考察

この問題で大事なのは、元々店にあったフルーツか、新しく届いたフルーツかは関係ないということです。
最終的に必要なのは、全部合わせた \(N+M\) 個の中で甘さが大きい順に \(K\) 個を選ぶことだけです。

たとえば、

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

なら、全部まとめると

\([5, 1, 8, 4, 10]\)

これを大きい順に並べると

\([10, 8, 5, 4, 1]\)

なので、上位 \(3\) 個の合計は

\(10 + 8 + 5 = 23\)

です。

素朴な方法

「どの \(K\) 個を選ぶか」を全探索すると、組み合わせの数は非常に多くなり現実的ではありません。
また、毎回最大値を探すことを \(K\) 回繰り返す方法も、実装はできますがもっと簡単な方法があります。

どう解決するか

全てのフルーツの甘さを 1 つの配列に入れて、降順ソートします。
すると、先頭から \(K\) 個がそのまま「甘さの大きい順に選ばれる \(K\) 個」になります。

制約は \(N+M \leq 150000\) なので、ソートの \(O((N+M)\log(N+M))\) で十分間に合います。

アルゴリズム

1. \(N, M, K\) を読み込む
2. 続く \(N+M\) 個の甘さをすべて 1 つの配列 vals に読み込む
3. vals を降順にソートする
4. 先頭 \(K\) 個の合計を出力する

コードでは、\(A_i\) と \(B_j\) を区別せずにそのまま N+M 個まとめて読み込んでいます。
この問題では最終的に全部まとめて比較するだけなので、それで十分です。

計算量

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

実装のポイント

• \(A_i\) と \(B_j\) は最終的に同じように扱うので、別々の配列に分ける必要はありません。

• Python では vals.sort(reverse=True) で簡単に降順ソートできます。

• 合計値は大きくなる可能性がありますが、Python の整数型ならそのまま扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    vals = [int(input()) for _ in range(N + M)]
    vals.sort(reverse=True)
    print(sum(vals[:K]))

if __name__ == "__main__":
    main()

---

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