概要

\(N\) 台の車を、それぞれの希望する駐車スペース \(P_i\) に基づいて順番に案内し、最終的に何台の車が駐車できたかをシミュレーションする問題です。

考察

この問題で重要なのは、車が到着するたびに「どのスペースに停められるか」をルールの通りに判定することです。

ルールを整理すると以下のようになります： 1. まず、希望の場所 \(P_i\) を確認する。 2. \(P_i\) が埋まっていれば、\(P_i + 1\)、その次は \(P_i + 2 \dots\) と、番号が大きい方へ順に空きを探す。 3. \(M\) 番目まで確認しても空きがなければ、その車は諦めて帰る。

制約を見ると、車の台数 \(N\) も駐車スペースの数 \(M\) も最大で 100 と非常に小さいです。そのため、各車が到着するたびに駐車スペースを端から順番にチェックする「素朴なシミュレーション」を行っても、計算回数は最大で \(N \times M = 10,000\) 回程度にしかなりません。これは一般的なプログラミング言語で 1 秒間に処理できる回数（約 \(10^8\) 回）に比べて十分に小さいため、単純なループで解くことができます。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 準備: 駐車スペースの状態を管理する配列 occupied を用意します。初期状態はすべて「空き」にします。
2. シミュレーション: \(N\) 台の車について、到着順に以下の処理を行います。
   • その車の希望 \(P_i\) から \(M\) 番目までのスペースを順番に調べる。
   • もし空いているスペース \(j\) が見つかったら：
     • occupied[j] を「駐車済み」に更新する。
     • 駐車成功台数を \(1\) 増やす。
     • 次の車の処理へ移る（その車のための探索を終了する）。
   • 最後まで空きが見つからなければ、その車は無視して次の車の処理へ移る。
3. 出力: 最終的な駐車成功台数を出力します。

計算量

• 時間計算量: \(O(NM)\)
  • \(N\) 台の車それぞれに対して、最大で \(M\) 個のスペースを走査するためです。
• 空間計算量: \(O(M)\)
  • 駐車スペースの状態（空きか否か）を保持するための配列のサイズです。

実装のポイント

• 1-indexed への対応: 問題文では駐車スペースが \(1\) から \(M\) 番までとなっています。プログラムの配列（リスト）は通常 \(0\) から始まるため、サイズを \(M+1\) で確保して \(1\) 番から \(M\) 番までをそのまま使うようにすると、混乱が少なく実装できます。

• フラグ管理: 各車について「駐車できたかどうか」を判定するために、内側のループで break を使用したり、見つかったかどうかを記録する変数（found など）を用意したりするとスムーズです。

  ソースコード

import sys

def main():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    p = list(map(int, input_data[2:]))
    
    # 駐車スペースの状態を管理するリスト（1番からM番まで）
    # False: 空き、True: 駐車済み
    occupied = [False] * (m + 1)
    
    parked_count = 0
    
    # 到着順に車を案内する
    for desired_space in p:
        # 希望のスペースから順に、空いている最も番号が小さいスペースを探す
        found = False
        for j in range(desired_space, m + 1):
            if not occupied[j]:
                occupied[j] = True
                parked_count += 1
                found = True
                break
        
        # 条件を満たすスペースがない場合は何もしない（帰ってしまう）
        if not found:
            continue
            
    # 駐車できた台数を出力
    print(parked_count)

if __name__ == '__main__':
    main()

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