概要

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

考察

この問題を解くためのポイントは以下の2点です。

1. どの商品が「選抜候補」になるかを素早く判定する 各商品が保管されているエリア \(C_i\) が、立ち入り可能なエリアのリスト \(\{S_1, S_2, \ldots, S_Q\}\) に含まれているかを確認する必要があります。 商品の数 \(N\) と立ち入り可能エリアの数 \(Q\) は最大で \(10^5\) 規模であるため、各商品ごとにリスト \(S\) を最初から最後まで探すと、最悪の場合 \(O(N \times Q)\) の時間がかかり、制限時間に間に合いません。 そこで、バケット（真偽値の配列）やセット（集合型）を用いることで、特定のエリアが立ち入り可能かどうかを \(O(1)\) で判定できるようにします。

2. 合計値を最大化する選び方（貪欲法） 選べる商品の数には「最大 \(K\) 個」という制限があります。合計金額を最大化するためには、選べる商品の中から販売価格が高いものから順に選んでいくのが最適です。これは「貪欲法」と呼ばれる基本的な考え方です。

アルゴリズム

以下の手順で解を求めます。

1. 立ち入り可能エリアの記録: 長さ \(M+1\) の真偽値配列 is_accessible を用意し、与えられた \(S_1, \ldots, S_Q\) 番目の要素を True にします。
2. 商品のフィルタリング: すべての商品 \((V_i, C_i)\) を確認し、is_accessible[C_i] が True である商品の価格 \(V_i\) だけをリスト valid_prices に追加します。
3. ソート: リスト valid_prices を降順（大きい順）に並べ替えます。
4. 合計の計算: 並べ替えたリストの先頭から最大 \(K\) 個を取り出し、その合計を出力します。もし候補の商品が \(K\) 個より少ない場合は、ある分だけすべて足します。

計算量

• 時間計算量: \(O(N \log N + M)\)
  • 立ち入り可能エリアの記録に \(O(Q + M)\)
  • 商品のフィルタリングに \(O(N)\)
  • 商品のソートに \(O(N \log N)\) かかります。
  • 全体として \(N, M\) の制約（約 \(10^5\)）に対して十分に高速です。
• 空間計算量: \(O(N + M)\)
  • 商品価格のリストやエリア情報の配列を保持するために必要です。

実装のポイント

• 高速な入出力: Pythonでは input() を繰り返すと時間がかかることがあるため、sys.stdin.read().split() を使って一括で入力を取得し、処理を高速化しています。

• スライスの活用: Pythonのリストのスライス valid_prices[:K] は、リストの要素数が \(K\) 個より少ない場合でもエラーにならず、存在する分だけを取得してくれるため、個数の判定処理を簡潔に書くことができます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割します。
    # 大量の入力を高速に処理するために sys.stdin.read().split() を使用します。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 読み込んだ文字列のリストを整数のリストに変換します。
    nums = list(map(int, input_data))
    
    # 基本情報の取得
    # N: 商品の数, M: エリアの数, K: 最大選抜数, Q: 立ち入り可能エリア数
    N = nums[0]
    M = nums[1]
    K = nums[2]
    Q = nums[3]
    
    # 立ち入り可能なエリアを高速に判定するために、真偽値の配列を作成します。
    # エリア番号は1からMまでなので、サイズをM+1にします。
    is_accessible = [False] * (M + 1)
    
    # 立ち入り可能なエリア番号(S_j)は、N個の商品情報(V_i, C_i)の後に続いています。
    # 商品情報の開始インデックスは4、各商品は2つの数値(V, C)を持つため、
    # S_jの開始インデックスは 4 + 2 * N となります。
    s_start = 4 + 2 * N
    for i in range(s_start, s_start + Q):
        area_id = nums[i]
        is_accessible[area_id] = True
        
    # 立ち入り可能なエリアに保管されている商品の販売価格を抽出します。
    # 商品iの販売価格 V_i は nums[4 + 2*i]、エリア番号 C_i は nums[4 + 2*i + 1] です。
    valid_prices = []
    for i in range(N):
        v_idx = 4 + 2 * i
        c_idx = 4 + 2 * i + 1
        if is_accessible[nums[c_idx]]:
            valid_prices.append(nums[v_idx])
    
    # 販売価格の合計を最大化するため、抽出した価格を降順（大きい順）にソートします。
    valid_prices.sort(reverse=True)
    
    # 上位 K 個（商品が K 個未満の場合はすべて）の販売価格の合計を計算して出力します。
    # Pythonのスライス valid_prices[:K] はリストの要素数が K 未満でもエラーになりません。
    print(sum(valid_prices[:K]))

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-preview によって生成されました。