概要

この問題は、一列に並んだ積み木に対して「右隣の積み木が自分より高い場合に、左隣の積み木を取り除く」という操作を繰り返したとき、最終的に残る積み木の個数を求める問題です。

一見複雑なシミュレーションが必要に見えますが、「右から左へ」 順に考えていくことで、非常にシンプルな規則（スタックを用いた一方向の走査）で解くことができます。

考察

なぜ素朴なシミュレーションではダメなのか？

問題文の指示通りに、毎ラウンド配列を走査して要素を削除するシミュレーションを行うと、最悪の場合で \(O(N^2)\) の時間がかかってしまいます。 本問題では \(N \le 10^6\) と非常に大きいため、愚直なシミュレーションでは実行時間制限（TLE）になってしまいます。そのため、より効率的な法則を見つける必要があります。

重要な観察：右から左への「ドミノ倒し」

この問題の操作は、「右側にある高い積み木が、その左側にある自分より低い積み木を次々と消し去っていく」 という挙動をしています。

具体例として、積み木の高さが \(H = [3, 2, 4, 1]\) の場合を考えます。

1. 一番右の \(1\)： 右隣に積み木がないため、誰からも消されることはなく、必ず生き残ります。
2. 右から2番目の \(4\)： 右隣の \(1\) より大きいため、消されずに生き残ります。さらに、この \(4\) は左側にある自分より低い積み木（\(2\) や \(3\)）を次々と消し去る力を持っています。
3. 右から3番目の \(2\)： 右側にある \(4\) よりも低いため、いずれ \(4\) に押し流されて（消されて）しまいます。
4. 一番左の \(3\)： これも右側にある \(4\) より低いため、同様に消されてしまいます。

このように、右から左へと見ていったとき、「それまでに生き残ることが確定した積み木（の高さの基準）」以上の高さを持つ積み木だけが生き残ることができます。

生き残る条件の整理

右から左へ順に見ていきます。 - 現在の積み木の高さを \(x\) とします。 - これまでに生き残ることが確定した、最も左にある積み木の高さを \(S\) とします。 - \(x \ge S\) であれば、右側のどの積み木も \(x\) を消すことはできません。したがって、 \(x\) は生き残ります。このとき、新たな基準は \(x\) に更新されます（\(S \leftarrow x\)）。 - \(x < S\) であれば、 \(x\) は右側にある \(S\) にいずれ消されてしまうため、生き残りません。

この規則を適用すると、右から左へ1回走査するだけで、最終的に生き残る積み木をすべて特定できます。

---

具体例でのシミュレーション

\(H = [3, 2, 4, 1]\) を右から（逆順に）見ていきます。

• \(1\) を見る: スタックは空なので、生き残り確定。スタックに追加。
  • スタック: [1]
• \(4\) を見る: スタックの末尾（\(1\)）以上なので、生き残り確定。スタックに追加。
  • スタック: [1, 4]
• \(2\) を見る: スタックの末尾（\(4\)）未満なので、消滅。スタックには追加しない。
  • スタック: [1, 4]
• \(3\) を見る: スタックの末尾（\(4\)）未満なので、消滅。スタックには追加しない。
  • スタック: [1, 4]

最終的にスタックに残ったのは [1, 4] の \(2\) 個となり、これが答えです。

アルゴリズム

スタック（Pythonではリスト）を用いて、以下の手順で解くことができます。

1. 空のスタック stack を用意する。
2. 入力配列 \(H\) を末尾（右端）から先頭（左端）に向かって逆順に走査する。
3. 各要素 \(x\) について：
   • stack が空、または stack の末尾の要素が \(x\) 以下である場合：
     • \(x\) を stack に追加する。
   • そうでない場合（\(x\) が stack の末尾の要素より小さい場合）：
     • 何もしない（無視する）。
4. 最終的な stack の要素数（長さ）を出力する。

計算量

• 時間計算量: \(O(N)\) 配列を逆順に1回だけ走査するため、要素数 \(N\) に対して線形時間で処理が終了します。\(N = 10^6\) でも 0.1 秒未満で高速に動作します。
• 空間計算量: \(O(N)\) 入力データの保持および、最悪の場合（すべての積み木が生き残る場合など）にスタックに最大 \(N\) 個の要素を格納するためです。

実装のポイント

• 高速な入出力: Pythonで \(N = 10^6\) の入力を処理する場合、input() を繰り返すと入出力がボトルネックになり TLE になる可能性があります。sys.stdin.read().split() を使用して、すべての入力を一括で取得することで高速化しています。

• 逆順の走査: reversed(H) を使用することで、元の配列を書き換えることなく、効率的に後ろから要素を取り出すことができます。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    H = [int(x) for x in input_data[1:]]

    stack = []
    for x in reversed(H):
        if not stack or stack[-1] <= x:
            stack.append(x)

    print(len(stack))


if __name__ == "__main__":
    solve()

---

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