概要

各観光地のお土産の満足度の中央値（評価値）を求め、その中から高評価な観光地を最大 \(K\) 箇所選び、評価値の合計を最大化する問題。

考察

この問題では、各観光地の「評価値」を求める必要があります。評価値は、その観光地で売られているお土産の満足度の中央値であり、満足度のリストをソートしたときの \(\frac{C_i + 1}{2}\) 番目（0-indexedでは \(\frac{C_i - 1}{2}\) 番目）の値です。

たとえば、ある観光地のお土産の満足度が [3, -1, 2] だったとします。これをソートすると [-1, 2, 3] となり、中央値（評価値）は 2 です。

各観光地の評価値を全て求めた後、それらの中から「正の値を持つ上位 \(K\) 個」を選ぶのが最適です。なぜなら、負の評価値を選ぶメリットは無く、また0も選んでも合計に寄与しないため、正の評価値だけを選んで最大 \(K\) 個取るのが最善となります。

この素朴な方法で十分高速であり、特にTLEやWAの原因となるような罠もありません。ただ、入力を高速に読み込む工夫が必要です。

アルゴリズム

1. 各観光地について：
   • 満足度のリスト \(V\) を受け取り、ソートする。
   • 中央値を \((C_i - 1)/2\) 番目の要素として取得し、評価値とする。
2. 全観光地の評価値を集めて降順にソートする。
3. 上位 \(K\) 個の正の値を合計して答えとする（負になったらそこで打ち切り）。

計算量

• 時間計算量: \(O(N \cdot C_{\text{max}} \log C_{\text{max}} + N \log N)\)
  
  • 各観光地の中央値を求める処理が \(O(C_i \log C_i)\) で、それが \(N\) 回。
  • 評価値のソートが \(O(N \log N)\)。
• 空間計算量: \(O(C_{\text{max}} + N)\)
  
  • 各観光地の \(V\) の保持と、評価値リストの保存。

実装のポイント

• 標準入力を高速に読み込むために sys.stdin.read を使用。

• 中央値のインデックスは0-indexedで (C - 1) // 2。

• 評価値が負の場合は選ばないため、ソート後に上位から貪欲に正のものだけを選ぶ。

  ソースコード

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    evaluations = []
    
    for _ in range(N):
        C = int(data[idx])
        idx += 1
        V = []
        for _ in range(C):
            V.append(int(data[idx]))
            idx += 1
        V.sort()
        median = V[(C - 1) // 2]
        evaluations.append(median)
    
    # Sort evaluations in descending order to pick the top K positive ones
    evaluations.sort(reverse=True)
    
    max_sum = 0
    for i in range(min(K, len(evaluations))):
        if evaluations[i] > 0:
            max_sum += evaluations[i]
        else:
            break
    
    print(max_sum)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。