概要

各窓口の処理可能件数の上限を管理しながら、申請を順番に処理し、受付が成立した件数を数える問題です。

考察

問題の本質

この問題は、各窓口ごとに「残り何件処理できるか」を管理すればよいシンプルなシミュレーション問題です。

重要な気づき

1. 申請は順番に処理される: 先に来た申請が優先されます
2. 窓口ごとに独立: 窓口 \(i\) の残り件数は、他の窓口に影響しません
3. 残り件数の管理: 各窓口について、最大処理件数 \(C_i\) から受け付けた件数を引いた値を追跡すれば十分です

なぜシンプルな方法で解けるか

各申請について行う処理は以下の2つだけです： - 希望窓口の残り件数を確認する（\(O(1)\)） - 残り件数があれば、1減らして受付成立（\(O(1)\)）

\(M\) 件の申請すべてに対してこの処理を行っても、全体で \(O(M)\) の計算量で済みます。

アルゴリズム

1. 初期化: 各窓口 \(i\) の残り処理可能件数を \(C_i\) で初期化した配列 remaining を用意する

2. 申請の処理: \(M\) 件の申請を順番に処理する

   • 申請 \(j\) で希望された窓口番号 \(T_j\) を読み取る
   • 窓口 \(T_j\) の残り件数が \(1\) 以上なら：
     • 残り件数を \(1\) 減らす
     • 受付成立件数を \(1\) 増やす
   • 残り件数が \(0\) なら、何もしない（受理されない）

3. 結果出力: 受付が成立した総件数を出力する

具体例

\(N = 2\)、\(M = 4\)、\(C = [2, 1]\)、申請が窓口 \(1, 1, 2, 1\) の順に来た場合：

申請	希望窓口	窓口1の残り	窓口2の残り	結果
初期	-	2	1	-
1	1	2→1	1	成立
2	1	1→0	1	成立
3	2	0	1→0	成立
4	1	0	0	不成立

結果：受付成立は 3件

計算量

• 時間計算量: \(O(N + M)\)
  • 初期化に \(O(N)\)
  • 各申請の処理に \(O(1)\) × \(M\) 件 = \(O(M)\)
• 空間計算量: \(O(N)\)
  • 残り件数を管理する配列 remaining に \(O(N)\)

実装のポイント

1. インデックスの変換: 問題文では窓口番号が \(1\) から始まる（1-indexed）ですが、Pythonの配列は \(0\) から始まる（0-indexed）ため、idx = T - 1 として変換が必要です

2. 配列のコピー: remaining = C[:] でリストをコピーしています。remaining = C とすると参照渡しになり、元の \(C\) も変更されてしまうので注意が必要です

3. 大きな \(C_i\) への対応: \(C_i\) は最大 \(10^9\) まであり得ますが、単純に残り件数として保持するだけなので、特別な処理は不要です

   ソースコード

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

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。