概要

コンサートの座席エリアごとに定員とチケット価格が決まっており、ファンが順番に指定エリアのチケットを予約しようとする。定員を超えると予約できないとき、全ファンの予約後のチケット代金の合計を求めよ。

考察

この問題では、各座席エリアに対して「現在どれだけ座席が残っているか」を管理しながら、ファン一人ひとりの予約要求を順に処理していく必要があります。

重要な観察は以下の通りです：

• 各エリアの定員 \(K_i\) を超えてチケットを売れることはない。
• 予約できるかどうかは、その時点での「残り座席数」を見て判断すれば良い。
• ファンの予約要求は順番に処理されるため、前のファンの結果が次のファンに影響を与える。

素朴な方法として、「毎回すべての予約状況を確認する」ような実装をすると、非常に非効率になります（例えば2次元リストで管理など）。しかし、各エリアの残座席数だけを管理しておけば、1回の予約要求につき定数時間で処理できます。

したがって、各エリアの残り座席数を配列で持っておき、ファンごとにその値を減らしていくことで効率的に処理できます。

アルゴリズム

1. 座席エリア数 \(N\) とファン数 \(M\) を読み込む。
2. 各エリア \(i\) のチケット価格 \(C_i\) と定員 \(K_i\) を読み込み、定員情報をコピーした「残り座席数管理用配列 remaining」を作成する。
3. ファンの予約要求を順に読み込みながら以下を行う：
   • 指定されたエリア \(P_j\) の remaining[P_j] が 0 より大きければ、
     • remaining[P_j] を 1 減らす。
     • そのエリアのチケット価格 \(C_{P_j}\) を合計に加える。
4. 最終的なチケット代金の合計を出力する。

この方法により、各ファンの予約処理が定数時間で行えるため、全体で \(O(M)\) で処理可能です。

具体例

例えば入力が以下のとき：

2 4
100 2
200 1
1
2
1
1

• エリア1：価格100円、定員2
• エリア2：価格200円、定員1

ファンの予約順： 1. エリア1 → OK（残1）、合計 += 100 → 100 2. エリア2 → OK（残0）、合計 += 200 → 300 3. エリア1 → OK（残0）、合計 += 100 → 400 4. エリア1 → NG（残0）、無視

最終的な合計は 400。

計算量

• 時間計算量: \(O(N + M)\)
  （初期データ読み込みに \(O(N)\)、各ファンの処理に \(O(M)\)）
• 空間計算量: \(O(N)\)
  （C, K, remaining 配列に \(O(N)\) 使用）

実装のポイント

• 残り座席数を別配列で管理することで、高速に判定・更新できる。
• 1-indexedで扱うために、配列サイズは \(N+1\) にしておくと実装が楽。
• 入力を高速化するため、sys.stdin.read() を使用している。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    C = [0] * (N+1)
    K = [0] * (N+1)
    for i in range(1, N+1):
        C[i] = int(data[idx])
        idx += 1
        K[i] = int(data[idx])
        idx += 1
    
    # 各エリアの残り座席数を管理
    remaining = K[:]
    
    total_cost = 0
    for _ in range(M):
        P = int(data[idx])
        idx += 1
        if remaining[P] > 0:
            remaining[P] -= 1
            total_cost += C[P]
    
    print(total_cost)

if __name__ == "__main__":
    main()

---

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