概要

積み木の列に対して「右にある積み木の方が高ければ左の積み木を取り除く」という操作を繰り返し、最終的に残る積み木の個数を求める問題です。これは 単調スタック（monotonic stack）を使うことで \(O(N)\) で解けます。

考察

操作の本質を理解する

1ラウンドの動作を追うと、カーソルは右端から左へ動き、「位置 \(k\) の積み木が位置 \(k-1\) より高いなら \(k-1\) を取り除く」を行います。取り除くと同じ積み木がさらに左隣と比較されるため、ある積み木は自分より低い積み木を左方向に食べ続け、自分以上の高さの積み木にぶつかると止まるという挙動になります。

ここから重要な観察が得られます：

積み木が取り除かれるのは、「自分より高い積み木が、途中の低い積み木をすべて食べながら右から到達したとき」だけである。

言い換えると、「ある積み木のすぐ右に、より高い積み木が来たら、その積み木は消える」ということです。

最終状態の性質

最終的に残る積み木を左から見ると、必ず高さが広義単調減少（右へ行くほど高くならない）になります。なぜなら、もし隣り合う残存積み木で右の方が高ければ、まだ左が取り除かれるはずで、整理が終了していないからです。

素朴なアプローチの問題点

問題文の手順どおりに、ラウンドを1つずつシミュレーションすると：

• 1ラウンドの走査に \(O(M)\)
• ラウンド数が最悪 \(O(N)\) 回

となり、全体で \(O(N^2)\)（最悪 \(10^{12}\) 回）となって TLE します。さらに、リストの途中から要素を削除して詰め直す操作自体も重いです。

アルゴリズム

「右から高い積み木が来ると、左の低い積み木が食べられる」という性質は、左から順に処理する単調スタックでそのままシミュレーションできます。

積み木を左から順に見て、次のように処理します：

1. 新しい積み木の高さ \(h\) を用意する。
2. スタックの一番上（すぐ左に残っている積み木）が \(h\) より低い 間、それをスタックから取り除く（\(h\) に食べられる）。
3. 取り除きが止まったら（スタックが空、または一番上が \(h\) 以上）、\(h\) をスタックに積む。

こうすると、スタックは常に「下から上へ高さが広義単調減少」に保たれ、これは最終状態の性質と一致します。各積み木について「自分より低い左隣を食べ、自分以上の高さで止まる」という挙動を左から順に再現しているため、ラウンドを繰り返した結果と同じ残存集合が得られます。

最後に残ったスタックの要素数が答えです。

具体例

高さ \([3, 1, 2]\) の場合：

• \(h=3\)：スタック空 → 積む。スタック [3]
• \(h=1\)：上は \(3\)（\(3 < 1\) ではない）→ 積む。スタック [3, 1]
• \(h=2\)：上は \(1\)（\(1 < 2\)）→ 取り除く。次の上は \(3\)（\(3 < 2\) ではない）→ 積む。スタック [3, 2]

残った個数は 2。実際にラウンドを回しても同じ結果になります。

計算量

• 時間計算量: \(O(N)\) — 各積み木はスタックに一度積まれ、一度だけ取り除かれるため、push/pop の合計回数は高々 \(2N\) 回。
• 空間計算量: \(O(N)\) — スタックのサイズ。

実装のポイント

• \(N \leq 10^6\) と大きいため、入力の読み込みは高速化が必須です。sys.stdin.buffer.read() で一括読み込みし、split() でまとめて分割します。

• Python では、ループ内で stack.append / stack.pop を毎回属性参照すると遅くなるため、ap = stack.append、pop = stack.pop のようにローカル変数へ束ねておくと高速化できます。

• 比較は「より低い」＝ stack[-1] < h の厳密な不等号で行います。等しい高さの積み木は取り除かれない（自分より高い場合のみ取り除く）ため、等号を含めないことが正解の条件です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    stack = []
    ap = stack.append
    pop = stack.pop
    for i in range(1, n + 1):
        h = int(data[i])
        while stack and stack[-1] < h:
            pop()
        ap(h)
    sys.stdout.write(str(len(stack)) + "\n")

main()

---

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