概要

各観光地の評価値（お土産の満足度の中央値）が与えられ、最大K個の観光地を選んで評価値の合計を最大化する問題です。

考察

重要な観察点は以下の通りです： 1. 各観光地の評価値は、その観光地のお土産の満足度をソートした中央値として計算できます 2. 評価値が正の観光地だけを選ぶのが最適です（負の値を足すと合計が減少するため） 3. 評価値が大きい観光地から順に選ぶことで、合計を最大化できます

素朴なアプローチとして全ての組み合わせを試す方法がありますが、Nが最大100、Kが最大100なので、組み合わせの数が膨大になり現実的ではありません。代わりに、貪欲法を用いることで効率的に解くことができます。

アルゴリズム

1. 各観光地について、お土産の満足度をソートし、中央値を計算する
2. 得られた評価値を降順（大きい順）にソートする
3. 上位K個の評価値のうち、正の値のみを合計する
4. 途中で負の値が出たら、それ以降は合計しない（負の値を足すと合計が減少するため）

計算量

• 時間計算量: \(O(N \cdot C_i \log C_i)\)
  • 各観光地でソートする処理が支配的（\(C_i \leq 99\)）
• 空間計算量: \(O(N)\)
  • 評価値を格納するための配列のみを使用

実装のポイント

• 中央値の計算では、\((C_i + 1)/2\) 番目の値を取得する（インデックスは0始まりなので-1する）

• 評価値が正のものだけを選ぶことで最適解が得られる

• 空入力の場合（観光地が0個）への対応を忘れない

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    if not data:
        print(0)
        return
        
    first_line = data[0].split()
    N = int(first_line[0])
    K = int(first_line[1])
    
    attractions = []
    index = 1
    for i in range(N):
        C = int(data[index]); index += 1
        values = list(map(int, data[index].split())); index += 1
        values.sort()
        median_index = (C + 1) // 2 - 1
        median = values[median_index]
        attractions.append(median)
    
    attractions.sort(reverse=True)
    total = 0
    for i in range(min(K, len(attractions))):
        if attractions[i] > 0:
            total += attractions[i]
        else:
            break
            
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。