概要

\(N + M\) 個のフルーツをすべてまとめて、甘さが大きい順に上位 \(K\) 個を選び、その甘さの合計を求める問題です。

考察

• 店にあるフルーツ（\(N\) 個）と新しく届いたフルーツ（\(M\) 個）は出所が異なりますが、選び方に制限はありません。つまり、すべてのフルーツを区別なく一つの集合として扱ってよいという点が重要な気づきです。
• 「甘さの大きい順に \(K\) 個選ぶ」とは、全フルーツを甘さで降順にソートして、先頭から \(K\) 個取ればよいということです。
• 素朴に全フルーツをソートするアプローチで十分高速です。\(N + M \leq 150000\) なので、ソートの計算量 \(O((N+M) \log(N+M))\) は余裕で間に合います。

具体例で確認してみましょう。

例えば \(N = 3, M = 2, K = 3\) で、店のフルーツの甘さが \([5, 1, 3]\)、新しいフルーツの甘さが \([4, 2]\) の場合：

1. すべてまとめると \([5, 1, 3, 4, 2]\)
2. 降順にソートすると \([5, 4, 3, 2, 1]\)
3. 上位 \(K = 3\) 個は \([5, 4, 3]\)
4. 合計は \(5 + 4 + 3 = 12\)

アルゴリズム

1. \(N\) 個のフルーツの甘さと \(M\) 個のフルーツの甘さを、一つのリストにまとめる。
2. そのリストを甘さの降順（大きい順）にソートする。
3. 先頭から \(K\) 個の要素を取り出し、その合計を出力する。

全フルーツ = A の要素 + B の要素
全フルーツを降順にソート
答え = 全フルーツの先頭 K 個の合計

計算量

• 時間計算量: \(O((N+M) \log(N+M))\)
  • ソートが支配的です。\(N + M \leq 150000\) なので十分高速です。
• 空間計算量: \(O(N+M)\)
  • 全フルーツを格納するリストの分です。

実装のポイント

• 入力の高速化: sys.stdin.read() で入力を一括読み込みし、split() で分割しています。\(N + M\) が大きい場合、1行ずつ input() で読むより高速です。

• 降順ソート: fruits.sort(reverse=True) で降順にソートし、fruits[:K] でスライスすることで上位 \(K\) 個を簡潔に取り出せます。

• 甘さの合計のオーバーフロー: 各フルーツの甘さは最大 \(10^9\)、\(K\) は最大 \(150000\) なので、合計は最大 \(1.5 \times 10^{14}\) 程度になります。Python は整数のオーバーフローがないため心配不要ですが、C++ 等で解く場合は long long を使う必要があります。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    fruits = []
    for i in range(N + M):
        fruits.append(int(input_data[idx])); idx += 1
    
    fruits.sort(reverse=True)
    print(sum(fruits[:K]))

main()

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