概要

整理後に残るのは、「自分より右側に、自分より高い積み木が存在しない」積み木だけです。

したがって、右から左へ見ていき、これまでに見た最大値以上の高さの積み木を数えれば答えになります。

考察

積み木が取り除かれる条件は、

右隣の積み木の高さが、自分より大きい

というものです。

つまり、ある積み木が取り除かれるためには、元々その積み木より右側にある積み木の中に、自分より高いものが必要です。

逆に言えば、自分より右側に自分より高い積み木が存在しないなら、その積み木は絶対に取り除かれません。
なぜなら、左側の積み木が右側の積み木を取り除くことはないからです。

一方で、自分より右側に自分より高い積み木が存在する場合、その積み木は最終的に取り除かれます。

例えば、次のような列を考えます。

4 2 4 3 5 5 1

右から見ていくと、

• 1 は右に何もないので残る
• 右から 2 番目の 5 は右側の最大値 1 以上なので残る
• その左の 5 も、右側に自分より大きい積み木はないので残る
• 3, 4, 2, 4 は右側に 5 があるので取り除かれる

最終的に残るのは、

5 5 1

です。

重要なのは、比較条件が「より大きい」であることです。
高さが等しい場合は取り除かれないため、右側の最大値と等しい積み木も残ります。

そのため、右から左に見ていき、

• 現在の高さが、これまで見た最大値以上なら残る
• 現在の高さが、これまで見た最大値未満なら取り除かれる

と判定できます。

素朴に列をシミュレーションして、積み木を削除していく方法では、途中の削除操作に時間がかかります。
特に Python のリストで中央の要素を削除すると \(O(N)\) かかるため、全体で \(O(N^2)\) になり、\(N \leq 10^6\) では間に合いません。

アルゴリズム

右から左へ積み木を見ていきます。

変数 mx を「これまで右側で見た高さの最大値」とします。

各積み木の高さを \(H_i\) とすると、

• \(H_i \geq mx\) の場合
  右側に \(H_i\) より高い積み木は存在しないので、この積み木は残ります。
  答えを \(1\) 増やし、mx を \(H_i\) に更新します。

• \(H_i < mx\) の場合
  右側に自分より高い積み木が存在するので、この積み木は取り除かれます。

これをすべての積み木について行えば、残る積み木の個数が求まります。

コードでは、入力全体を data として読み込んでいます。
data[0] は \(N\) なので、実際の高さは data[1] から data[N] に入っています。

mx = 0
ans = 0

for i in range(len(data) - 1, 0, -1):
    h = data[i]
    if h >= mx:
        ans += 1
        mx = h

高さはすべて \(1\) 以上なので、初期値 mx = 0 で問題ありません。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

入力をリストとして保持しているため、空間計算量は \(O(N)\) です。
追加で使う変数は mx と ans だけなので、入力を除けば \(O(1)\) です。

実装のポイント

判定は h > mx ではなく、h >= mx です。

高さが等しい積み木同士では取り除きが発生しないため、右側の最大値と等しい高さの積み木も残ります。

ソースコード

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
mx = 0
ans = 0

for i in range(len(data) - 1, 0, -1):
    h = data[i]
    if h >= mx:
        ans += 1
        mx = h

print(ans)

---

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