概要

複数の窓口があり、それぞれの窓口に処理できる申請の上限がある。申請が順番に届くので、希望する窓口に空きがあれば受付が成立する。最終的に何件の申請が受付されたかを求める。

考察

この問題では、申請が届いた順番に処理されていくため、先着順で窓口の処理枠が埋まっていくと考えることができます。つまり、ある申請が来たときに、希望する窓口にまだ処理可能件数が残っていれば受付され、そうでなければ拒否されます。

素朴な方法としては、毎回希望する窓口の残り処理可能件数を確認し、1つ減らすという処理を行うことが考えられます。これは1件あたり \(O(1)\) で処理できるので、全体でも十分高速です。

ただし、入出力の処理に注意が必要です。Python の input() を1行ごとに呼び出すと遅いため、すべての入力を一度に読み込む高速化が必要です。また、窓口の番号が 1-indexed であることに注意して、配列アクセスでは 0-indexed に変換する必要があります。

アルゴリズム

1. すべての入力を高速に読み込みます（sys.stdin.read を使用）。
2. 各窓口の処理可能件数をリスト counters として保持します（初期値は \(C_i\)）。
3. 申請を順番に処理します：
   • 希望する窓口の番号 \(T_j\) を取得します。
   • counters[T_j - 1] が 0 より大きければ、受付可能です：
     • counters[T_j - 1] を1減らします。
     • 受付件数を1増やします。
4. 最終的な受付件数を出力します。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• 入力の読み込みは sys.stdin.read を使い、高速化を図る。

• 窓口番号は1-indexedなので、リストアクセス時は T - 1 とする。

• counters は各窓口の残処理可能件数を管理するためのリスト。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    C = list(map(int, data[2:2+N]))
    
    # 各窓口の残り処理可能件数を管理
    counters = C[:]
    
    accepted = 0
    idx = 2 + N
    for _ in range(M):
        T = int(data[idx])
        idx += 1
        if counters[T - 1] > 0:
            counters[T - 1] -= 1
            accepted += 1
    print(accepted)

if __name__ == "__main__":
    main()

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