概要

\(N\) 個の窓口があり、それぞれに処理可能な最大件数が決まっています。届いた \(M\) 個の申請を順番に確認し、指定された窓口に空きがあるかどうかを判定して、最終的に受け付けられた合計件数を求めるシミュレーション問題です。

考察

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

1. 申請を順番に処理する: 申請は届いた順に処理されるため、入力を受け取った順にシミュレーションを行う必要があります。
2. 窓口の状態を管理する: 各窓口の残り処理可能件数を配列（リスト）で管理することで、特定の窓口に空きがあるかどうかを即座に判定できます。
3. 効率的な処理: 窓口の数 \(N\) と申請の数 \(M\) は最大で \(10^5\) です。各申請に対して「窓口の空きを確認して更新する」という操作を \(O(1)\) で行えば、全体で \(O(N + M)\) の計算量となり、制限時間内に十分に間に合います。

窓口の番号は \(1\) から \(N\) で与えられますが、プログラムの配列（リスト）は通常 \(0\) から始まるため、インデックスを \(T_j - 1\) として扱う点に注意が必要です。

アルゴリズム

以下の手順でプログラムを実装します。

1. 窓口の数 \(N\)、申請数 \(M\)、および各窓口の容量 \(C_1, \ldots, C_N\) を入力として受け取ります。
2. 各窓口の残り容量を管理する配列 C を用意します。
3. \(M\) 個の申請 \(T_j\) を順番に読み込み、以下の処理を行います。
   • 窓口 \(T_j\) （配列のインデックスでは \(T_j - 1\)）の残り容量が \(1\) 以上であるか確認します。
   • もし \(1\) 以上であれば、その窓口の容量を \(1\) 減らし、受付成立件数をカウントアップします。
   • 容量が \(0\) であれば、その申請は無視して次の申請へ進みます。
4. 最終的なカウントを出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)、申請の処理（ループ）に \(O(M)\) かかるため、全体として線形時間で処理可能です。
• 空間計算量: \(O(N)\)
  • 各窓口の容量を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonで \(10^5\) 規模の入力を扱う場合、input() を繰り返すよりも sys.stdin.read().split() などを使って一括で読み込む方が実行時間を短縮できます。

• インデックスの変換: 問題文の窓口番号（1-indexed）を配列の添字（0-indexed）に変換するために、常に -1 する操作を忘れないようにしましょう。

• 大きな数値の扱い: 各窓口の容量 \(C_i\) は最大 \(10^9\) と非常に大きいですが、Pythonの整数型は自動的に多倍長整数を扱うため、オーバーフローの心配はありません。

  ソースコード

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 をリストとして取得（0-indexedにするため、アクセス時は T_j - 1 とする）
    # C は input_data のインデックス 2 から 2 + N - 1 まで
    C = list(map(int, input_data[2:2+N]))
    
    # 受付が成立した総件数をカウントする変数
    accepted_count = 0
    
    # 各申請を順番に処理する
    # 申請 T_j は input_data のインデックス 2 + N から 2 + N + M - 1 まで
    for i in range(M):
        # 希望する窓口番号（1-indexed）を整数に変換
        t_j = int(input_data[2 + N + i])
        
        # 窓口のインデックスを 0-indexed に変換
        idx = t_j - 1
        
        # 希望する窓口に空きがあるか確認
        if C[idx] > 0:
            # 空きがあれば受付を成立させ、残り処理可能件数を1減らす
            C[idx] -= 1
            accepted_count += 1
            
    # 結果を出力
    print(accepted_count)

if __name__ == '__main__':
    solve()

---

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