概要

各窓口ごとに「残り受付可能件数」を管理し、申請が来るたびに空きがあれば1件受理して減らす、というシミュレーション問題です。

考察

重要なのは「申請は順番に処理され、希望窓口以外には回せない」点です。つまり、申請 \(j\) が窓口 \(T_j\) に来たときにやることは、

• その窓口の残り枠が \(> 0\) なら受理（残り枠を1減らす）
• そうでなければ不受理

の判定だけで十分です。

ここで、例えば「各申請ごとにその窓口が過去に何回出たかを毎回数え直す」などをすると、最悪で \(O(M^2)\) になり \(10^5\) では間に合いません（TLEの原因）。
本問題では窓口ごとの残り枠を配列で持ち、申請ごとに \(O(1)\) で更新すればよい、という気づきがポイントです。

（具体例）
\(C=[2,1]\)（窓口1は2件、窓口2は1件）で、申請が \([1,2,1,2]\) の順に来るとすると：

• 1番窓口：残り2→1（受理）
• 2番窓口：残り1→0（受理）
• 1番窓口：残り1→0（受理）
• 2番窓口：残り0なので不受理

合計3件が受理されます。

アルゴリズム

1. 配列 \(C\) を「各窓口の残り受付可能件数」として保持する。
2. 申請 \(T_j\) を先頭から順に読む。
3. 窓口 \(t=T_j-1\)（0-indexに変換）の \(C[t]\) を確認し、
   • \(C[t] > 0\) なら \(C[t]\) を1減らし、答えを1増やす
   • それ以外は何もしない
4. 最後に答えを出力する。

計算量

• 時間計算量: \(O(N+M)\)（初期化 \(N\)、申請処理 \(M\)）
• 空間計算量: \(O(N)\)（窓口ごとの残り枠配列）

実装のポイント

• 入力が最大 \(10^5\) 行規模なので、Pythonでは sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 窓口番号 \(T_j\) は \(1\) 始まりなので、配列アクセスのために \(t = T_j - 1\) に変換します。

• \(C_i\) は最大 \(10^9\) ですが、減算するだけなので通常の整数で問題ありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    C = [next(it) for _ in range(N)]
    ans = 0
    for _ in range(M):
        t = next(it) - 1
        if C[t] > 0:
            C[t] -= 1
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。