概要

各車は「希望位置 \(P_i\) 以上で空いている最小の駐車スペース」に停める（なければ帰る）ので、これを到着順にシミュレーションし、停められた台数を数えます。

考察

この問題の本質は、各車ごとに - 「\(P_i\) 以上で、まだ空いている中で最小の番号」 を高速に見つけて、そこを埋めることです。

素朴な方法

各車 \(i\) について、\(P_i, P_i+1, \dots, M\) を順に見て空きを探す方法が考えられます。
これは最悪で 1 台につき \(O(M)\) 探すことになり、全体で \(O(NM)\) です（この問題の制約だと間に合いますが、より大きい制約でも通る一般的な解法を考えます）。

重要な気づき

あるスペース \(s\) が埋まったら、次に「\(s\) から探し始めたい人」は必ず \(s+1\) 以降を見ればよく、\(s\) を見る必要は二度とありません。
つまり「この番号から探すなら次はどこを見るべきか」という“次の候補”を管理できれば高速化できます。

これを実現する典型手法が Union-Find（Disjoint Set Union, DSU）で“次の空き”を管理する方法です。

アルゴリズム

Union-Find を「次に探すべき空きスペース」を返すデータ構造として使います。

• find(x) を「\(x\) 以上で空いている最小の番号」を返す関数として扱う
• 初期状態では全て空きなので parent[i] = i
• あるスペース \(s\) に車を停めたら、そのスペースはもう使えないので
  「\(s\) の次の候補は \(s+1\)」として parent[s] = find(s+1) に更新する
  （これにより、次回以降 find(s) を呼ぶと \(s\) を飛ばして \(s+1\) 以降へ進む）

番兵（sentinel）の利用

\(M\) が埋まった後に find(M+1) を呼ぶ可能性があるので、配列を M+2 まで用意し、
M+1 を「空きが存在しない」ことを示す番兵にします。

流れ（シミュレーション）

各車の希望 \(p\) について 1. s = find(p) を計算（\(p\) 以上で空いている最小のスペース） 2. もし s <= M なら駐車成功
- ans += 1 - parent[s] = find(s+1) として \(s\) を使用済みにする 3. そうでなければ（s == M+1）駐車失敗で帰る

具体例

\(M=5\), 希望が \([3,3,4,3]\) のとき： - 1台目: find(3)=3 → 3に停める。以後 find(3) は 4 を返すようになる - 2台目: find(3)=4 → 4に停める。以後 find(4) は 5 - 3台目: find(4)=5 → 5に停める。以後 find(5) は 6(番兵) - 4台目: find(3)=6 → \(M\) を超えるので停められない

計算量

• 時間計算量: \(O\big((N+M)\alpha(M)\big)\) （\(\alpha\) は逆アッカーマン関数で、実用上ほぼ定数）
• 空間計算量: \(O(M)\)

実装のポイント

• parent を M+2 サイズで用意し、M+1 を番兵として使う（s+1 が M+1 になっても安全）

• find には 経路圧縮（コード中の parent[x] = parent[parent[x]] など）を入れて高速化する

• 駐車したら必ず parent[s] = find(s+1) と更新し、「次の空き」へつなぎ替えるのが肝心です

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    P = data[2:2+N]

    parent = list(range(M + 2))  # 1..M, sentinel M+1

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    ans = 0
    for p in P:
        s = find(p)
        if s <= M:
            ans += 1
            parent[s] = find(s + 1)

    print(ans)

if __name__ == "__main__":
    main()

---

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