概要

\(N\) 種類の座席エリア（価格 \(C_i\), 定員 \(K_i\)）に対して、\(M\) 人のファンが順番に希望するエリア \(P_j\) の予約を試みます。各エリアの定員を管理しながら、予約に成功したチケットの合計金額を求めるシミュレーション問題です。

考察

この問題で重要なのは、「各エリアにあと何席残っているか」をリアルタイムで管理することです。

ファンは一人ずつ順番に予約を行うため、前の人の予約結果が後ろの人の予約可否に影響を与えます。したがって、入力されたファンの順番通りに以下の処理を行う必要があります。

1. ファンが希望するエリア \(P_j\) の残りの座席数（定員）を確認する。
2. 座席が \(1\) つ以上残っていれば：
   • 予約成功として、そのエリアの価格 \(C_{P_j}\) を合計金額に加算する。
   • そのエリアの残りの座席数を \(1\) つ減らす。
3. 座席が残っていなければ：
   • 予約失敗として、何もしない。

制約を確認すると、エリア数 \(N\) とファンの数 \(M\) はともに最大 \(10^5\) です。各ファンの処理を定数時間 \(O(1)\) で行えば、全体で \(O(N + M)\) となり、実行時間制限内に十分に間に合います。

アルゴリズム

1. データの格納: 各エリアの価格 \(C\) と定員 \(K\) を配列（リスト）に格納します。
   • エリア番号は \(1\) から \(N\) で与えられるため、プログラム上のインデックス（\(0\) から \(N-1\)）とずれないよう注意します。
2. シミュレーション: \(M\) 人のファンについてループを回します。
   • 現在のファンの希望エリア \(P_j\) を取得します。
   • K[P_j] が \(0\) より大きいか判定します。
   • 条件を満たすなら、合計金額変数 total_price に C[P_j] を足し、K[P_j] を \(1\) 減らします。
3. 出力: 最終的な total_price を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • エリア情報の読み込みに \(O(N)\)、ファンの予約処理（ループ）に \(O(M)\) かかります。各予約処理は定数時間で終わるため、全体で線形時間となります。
• 空間計算量: \(O(N)\)
  • 各エリアの価格と定員を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonの場合、データ量が多い（\(10^5\) 行程度）と input() 関数では時間がかかることがあります。sys.stdin.read().split() を使って一括で読み込むことで、実行時間を短縮できます。

• インデックスの調整: 問題文のエリア番号 \(1 \dots N\) を、配列のインデックス \(0 \dots N-1\) に変換して扱う必要があります（入力された \(P_j\) から \(1\) を引くなど）。

  ソースコード

import sys

def solve():
    # 入力データをすべて読み込み、スペースや改行で分割してリストに格納します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 座席エリアの数, M: ファンの数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各エリアの価格 C と定員 K を格納するリスト
    # 0インデックスで管理するため、エリア i はインデックス i-1 に対応させます
    C = [0] * N
    K = [0] * N
    
    # エリア情報の読み込み
    idx = 2
    for i in range(N):
        C[i] = int(input_data[idx])
        K[i] = int(input_data[idx + 1])
        idx += 2
        
    total_price = 0
    # 各ファンの予約処理を順番に行います
    for _ in range(M):
        # 予約しようとするエリア番号 P (1-indexed)
        p = int(input_data[idx])
        idx += 1
        
        # 0-indexed に変換
        area_idx = p - 1
        
        # 定員に達していなければ予約可能
        if K[area_idx] > 0:
            total_price += C[area_idx]
            K[area_idx] -= 1
            
    # 合計金額を出力
    print(total_price)

if __name__ == '__main__':
    solve()

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