概要

立ち入り可能なエリアにある商品の中から、販売価格が高い順に最大 \(K\) 個選んで、その合計を最大化する問題です。

考察

重要な気づき

この問題で最大化したいのは「選んだ商品の販売価格の合計」です。売り場に並べられる商品数に上限 \(K\) があるので、価格が高い商品から優先的に選ぶのが最適です。

素朴なアプローチの検討

1. まず、立ち入り可能なエリアにある商品だけをフィルタリングする
2. その商品を価格順にソートして上位 \(K\) 個を選ぶ

この方法で正しい答えが得られます。

効率化のポイント

• 立ち入り可能なエリアの判定には、集合（set） を使うと \(O(1)\) で判定できます
• 全体をソートすると \(O(N \log N)\) かかりますが、上位 \(K\) 個だけが必要なので heapq.nlargest を使うと \(O(N \log K)\) で済みます（\(K\) が小さい場合に有利）

具体例で確認

例えば、以下のような入力を考えます： - 商品: (価格=100, エリア=1), (価格=200, エリア=2), (価格=150, エリア=1), (価格=300, エリア=3) - 立ち入り可能エリア: {1, 3} - \(K = 2\)

立ち入り可能なエリアの商品は：価格100（エリア1）、価格150（エリア1）、価格300（エリア3） 上位2個を選ぶと：300 + 150 = 450 が答えになります。

アルゴリズム

1. 入力の読み込み: 商品情報と立ち入り可能エリアを読み込む
2. 立ち入り可能エリアを集合に格納: 高速な判定のため set を使用
3. フィルタリング: 各商品について、そのエリアが立ち入り可能かチェックし、可能なら価格をリストに追加
4. 上位 \(K\) 個の選択:
   • 商品数が \(K\) 以下なら全部選ぶ
   • そうでなければ nlargest(K, リスト) で上位 \(K\) 個を取得
5. 合計を出力: 選んだ商品の価格の合計を出力

計算量

• 時間計算量: \(O(N + Q + N \log K)\)

  • \(O(N)\): 商品のフィルタリング（各商品について集合の判定は \(O(1)\)）
  • \(O(Q)\): 立ち入り可能エリアの集合構築
  • \(O(N \log K)\): nlargest による上位 \(K\) 個の取得

• 空間計算量: \(O(N + Q)\)

  • \(O(N)\): 商品情報と利用可能な商品の価格リスト
  • \(O(Q)\): 立ち入り可能エリアの集合

実装のポイント

1. 集合（set）の活用: 立ち入り可能エリアの判定を \(O(1)\) で行うため、リストではなく set を使用します

2. heapq.nlargest の利用: 全体をソートするより効率的に上位 \(K\) 個を取得できます。内部的にはヒープを使って実装されています

3. 商品数が \(K\) 以下の場合の処理: 選べる商品が \(K\) 個に満たない場合は、全商品を選ぶだけで良いので、単純に sum を取ります

4. 大量入力への対応: sys.stdin.read() を使って一括で読み込むことで、入力処理を高速化しています

   ソースコード

import sys
from heapq import nlargest

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
    Q = int(input_data[idx]); idx += 1
    
    products = []
    for i in range(N):
        V = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        products.append((V, C))
    
    accessible = set()
    for j in range(Q):
        S = int(input_data[idx]); idx += 1
        accessible.add(S)
    
    # 立ち入り可能なエリアにある商品の価格を集める
    available_values = []
    for V, C in products:
        if C in accessible:
            available_values.append(V)
    
    # 上位K個の合計を求める
    if len(available_values) <= K:
        print(sum(available_values))
    else:
        # nlargestを使って上位K個を効率的に取得
        top_k = nlargest(K, available_values)
        print(sum(top_k))

if __name__ == "__main__":
    main()

---

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