概要

各観光地のお土産の満足度から中央値（評価値）を計算し、評価値が高い観光地を最大 \(K\) 箇所選んだときの、評価値の合計の最大値を求める問題です。

考察

この問題を解くためには、以下の2つのステップに分けて考えるのが分かりやすいです。

1. 各観光地の評価値を求める 問題文の通り、各観光地の評価値はお土産の満足度の中央値です。中央値を求めるには、満足度を昇順（小さい順）に並べ替え、真ん中の値を取得すればよいです。お土産の数 \(C_i\) は必ず奇数なので、プログラミングにおいて 0 から始まるインデックス（0-indexed）を用いる場合、中央値は C_i // 2 番目の要素になります。

2. 評価値の合計を最大化する 各観光地の評価値が求まったら、次はどの観光地を選ぶかを決めます。 評価値の合計を最大化するためには、以下の2点に注意する必要があります。 - 評価値が大きい観光地から優先して選ぶ - 評価値が負（または \(0\)）の観光地は選ばない

選べる観光地は「 \(0\) 箇所以上 \(K\) 箇所以下」です。もし評価値が負の観光地を選んでしまうと、合計値が減ってしまいます。そのため、評価値がプラスの観光地だけを対象にし、その中で値が大きいものから順に最大 \(K\) 箇所選ぶのが最適な戦略となります。

アルゴリズム

1. 各観光地 \(i\) について、お土産の満足度 \(V_{i,j}\) のリストを昇順にソートします。
2. ソートしたリストの C_i // 2 番目の要素を取得し、観光地 \(i\) の評価値とします。
3. すべての観光地の評価値を求めたら、それらを降順（大きい順）にソートします。
4. 降順にソートした評価値の先頭から最大 \(K\) 個を確認し、値が \(0\) より大きい（正の数である）場合のみ、答え（合計値）に加算していきます。
5. 最終的な合計値を出力します。

計算量

• 時間計算量: \(O(\sum (C_i \log C_i) + N \log N)\) 各観光地のお土産のソートに \(O(C_i \log C_i)\) かかり、観光地 \(N\) 箇所の評価値のソートに \(O(N \log N)\) かかります。制約（ \(N \leq 100\), \(C_i \leq 99\) ）が非常に小さいため、実行時間制限には余裕で間に合います。
• 空間計算量: \(O(N + \max(C_i))\) 各観光地の評価値を保持する配列に \(O(N)\) 、入力を受け取る際のお土産の満足度を保持する配列に最大で \(O(\max(C_i))\) のメモリを使用します。

実装のポイント

• 中央値のインデックス: Pythonなどの 0-indexed の言語では、要素数が奇数 C のとき、中央値のインデックスは C // 2（切り捨て除算）で簡単に取得できます。例えば C = 5 のとき、インデックスは 0, 1, 2, 3, 4 となり、中央値は 2 番目（ 5 // 2 ）になります。

• 正の値のみを加算する: 問題文に「 \(0\) 箇所以上」とあるため、評価値がすべて負の場合は \(0\) 箇所選ぶ（合計 \(0\) ）のが正解になります。ループの中で if evaluations[i] > 0: という条件分岐を入れることで、これを正しく処理できます。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    K = int(data[1])
    
    idx = 2
    evaluations = []
    for _ in range(N):
        C_i = int(data[idx])
        idx += 1
        V_i = [int(x) for x in data[idx : idx + C_i]]
        idx += C_i
        
        V_i.sort()
        median = V_i[C_i // 2]
        evaluations.append(median)
        
    evaluations.sort(reverse=True)
    
    ans = 0
    for i in range(min(K, N)):
        if evaluations[i] > 0:
            ans += evaluations[i]
            
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。