概要

駐車場に到着する車を順番に駐車させていくシミュレーションを行い、駐車できた車の台数を求めます。

考察

この問題は、車が到着する順番に従って、ルールに従い駐車場に配置していくシミュレーション問題です。

各車 \(i\) は希望の駐車スペース \(P_i\) があり、以下のように駐車します：

1. 希望のスペースが空いていればそこに駐車。
2. そうでない場合は、希望のスペースよりも番号の大きいスペースの中で、最も番号が小さい空きスペースに駐車。
3. それもなければ駐車できない。

この処理を愚直にシミュレーションすることで解けます。重要なのは、すでに駐車されているかどうかを効率よく管理することです。リストなどの配列を使って、各駐車スペースが埋まっているかどうかを管理すれば、各車に対して定数時間または線形時間で判定できます。

もし駐車場の状態を毎回全探索していたら、最悪の場合 \(O(NM)\) かかりますが、制約が \(N, M \leq 100\) なので十分間に合います。

アルゴリズム

以下のような手順でシミュレーションを行います：

1. 駐車場の状態を管理する配列 parking を用意します。parking[i] が True なら駐車スペース \(i\) は埋まっています。
2. 各車 \(i\) の希望駐車場 \(P_i\) について：
   • まず \(P_i\) が空いているか確認し、空いていればそこに駐車。
   • 空いていなければ、\(P_i+1\) から \(M\) まで見て、初めて空いているスペースに駐車。
   • どちらもできなければ駐車失敗。
3. 駐車できた台数をカウントして出力。

計算量

• 時間計算量: \(O(NM)\)
  各車に対して最大で \(M\) 個の駐車場を走査する可能性があるため。
• 空間計算量: \(O(M)\)
  駐車場の状態を管理する配列のサイズ。

実装のポイント

• 駐車場のインデックスは 1 から M までなので、parking 配列は長さ \(M+1\) で確保し、parking[1..M] を使用します。
• 各車の処理で、希望の場所が埋まっていた場合に、より大きな番号の駐車場を探すループを忘れずに break で終了させること。

## ソースコード

```python
N, M = map(int, input().split())
P = list(map(int, input().split()))

parking = [False] * (M + 1)  # parking[1..M] を使う
count = 0

for p in P:
    if not parking[p]:
        parking[p] = True
        count += 1
    else:
        for i in range(p + 1, M + 1):
            if not parking[i]:
                parking[i] = True
                count += 1
                break

print(count)

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