概要

各観光地の「評価値（お土産の満足度の中央値）」を求め、その中から正の評価値を持つ観光地を最大 \(K\) 箇所まで選んで合計を最大化する問題です。

考察

重要な気づき①：評価値は中央値

各観光地 \(i\) の評価値は、\(C_i\) 個のお土産の満足度を昇順に並べたときの \(\frac{C_i+1}{2}\) 番目の値、つまり中央値です。\(C_i\) は必ず奇数なので、中央値は一意に決まります。

具体例: お土産の満足度が \([3, -1, 5]\) の場合、昇順に並べると \([-1, 3, 5]\) となり、中央値（2番目の値）は \(3\) です。

重要な気づき②：貪欲に正の評価値を選べばよい

• 0箇所以上 \(K\) 箇所以下を選べるので、訪れない選択肢もあります。
• 評価値が負の観光地を訪れると合計が減ってしまうため、評価値が正の観光地だけを選ぶべきです。
• 評価値が0の観光地は選んでも合計に影響しないため、選んでも選ばなくてもよいです（選ばなくてよい）。
• 正の評価値を持つ観光地が \(K\) 箇所以上あれば、大きい方から \(K\) 箇所選びます。\(K\) 箇所未満であれば、正の評価値を持つ観光地をすべて選びます。

素朴なアプローチとの比較

\(N\) 箇所から \(0\) 〜 \(K\) 箇所選ぶ全組合せを試すと最悪 \(2^N\) 通りで、\(N=100\) では到底間に合いません。しかし、上記の貪欲法により、ソートして上位を取るだけで最適解が得られます。

アルゴリズム

1. 各観光地 \(i\) について、\(C_i\) 個の満足度を昇順ソートし、中央値（インデックス \(C_i // 2\) の要素）を求める。
2. 全観光地の中央値のうち、正のもの（\(> 0\)）だけを集める。
3. 集めた正の中央値を降順にソートし、先頭から最大 \(K\) 個の合計を求める。
4. その合計が答え（正の中央値がなければ \(0\)）。

具体例: \(N=3, K=2\) で、各観光地の評価値が \([5, -3, 2]\) の場合、正の評価値は \([5, 2]\)。\(K=2\) 箇所まで選べるので、両方選んで合計 \(7\) が答えです。

計算量

• 時間計算量: \(O\!\left(\sum_{i=1}^{N} C_i \log C_i + N \log N\right)\)
  • 各観光地のお土産をソートするコスト \(O(C_i \log C_i)\) と、中央値をソートするコスト \(O(N \log N)\) の合計です。
• 空間計算量: \(O\!\left(\max_i C_i + N\right)\)
  • 各観光地のお土産リストと、中央値リストの格納に必要です。

実装のポイント

• 中央値のインデックス: \(C_i\) 個の要素を0-indexedで昇順ソートしたとき、中央値は V[C_i // 2] です。例えば \(C_i = 5\) なら V[2]（3番目の要素）。

• 0箇所選ぶ場合を忘れない: 全ての評価値が負の場合、1箇所も訪れず合計 \(0\) が最大です。正の評価値だけを集めることで、この場合は自然に合計が \(0\) になります。

• 評価値が0の観光地: 選んでも合計は変わらないため、実装では m > 0 のフィルタで除外しても問題ありません。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    medians = []
    for i in range(N):
        C = int(input_data[idx]); idx += 1
        V = []
        for j in range(C):
            V.append(int(input_data[idx])); idx += 1
        V.sort()
        median = V[C // 2]
        medians.append(median)
    
    # Select up to K spots with positive medians to maximize sum
    positive_medians = sorted([m for m in medians if m > 0], reverse=True)
    result = sum(positive_medians[:K])
    print(result)

main()

---

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