概要

一列に並んだ積み木に対し、右隣の高さが左隣より大きい場合に左隣を取り除く操作を、取り除けなくなるまで繰り返します。最終的に残る積み木の個数を求める問題です。

考察

問題文のシミュレーションをそのまま実装すると、1ラウンドあたり \(O(N)\)、ラウンド数も最悪 \(O(N)\) かかるため \(O(N^2)\) の計算量となり、\(N \leq 10^6\) の制約ではTLE（時間切れ）になります。そこで、最終的にどの積み木が残るかの法則を見つけます。

ある積み木 \(A\) が取り除かれるのは、右隣に \(A\) より背の高い積み木 \(B\) が来たときです。右隣の積み木が何度か入れ替わっても、最終的に \(A\) の右隣に「\(A\) より右にある積み木の中で最も高い積み木」がやってきて \(A\) を消し去ります。

つまり、積み木 \(A\) が最後まで残るためには、「自分より右にある積み木の高さの最大値」以上の高さを持つ必要があります。 逆に言えば、右から順番に見ていき、「これまで見てきた積み木の高さの最大値」を更新する積み木（＝右から見て単調非減少な積み木）だけが最終的に残るということです。

例えば、高さが [2, 5, 3, 1, 4] の場合、右から見ると 4, 1, 3, 5, 2 となります。 - 最初の 4 は基準となるので残ります（最大値: 4）。 - 1 は最大値 4 未満なので消えます。 - 3 も最大値 4 未満なので消えます。 - 5 は最大値 4 以上なので残ります（最大値: 5）。 - 2 は最大値 5 未満なので消えます。 残るのは 4 と 5 の2つだけで、これが実際のシミュレーション結果と一致します。

アルゴリズム

1. 右端（\(N\) 番目）から左端（1番目）へ向かって積み木を順に調べます。
2. これまで見てきた積み木の高さの最大値 max_h を記録します（初期値は積み木の高さより小さい値、例えば -1 とします）。
3. 現在見ている積み木の高さ \(h\) が max_h 以上であれば、この積み木は最後まで残るため、カウントを \(1\) 増やし、max_h を \(h\) で更新します。
4. 左端まで調べ終わったら、カウントした値が答えとなります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （入力を一括で読み込むため。1つずつ読み込めば \(O(1)\) にも可能です）

実装のポイント

• \(N \leq 10^6\) と大きいため、Pythonの標準入力 input() を使うとTLEになる可能性があります。代わりに sys.stdin.buffer.read().split() を使用して入力を一括で高速に読み込むことで実行時間を短縮できます。

• 右から左へ走査するため、配列のインデックスを \(N\) から \(1\) に向かって減らすようにループを回します。

  ソースコード

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    N = int(data[0])
    count = 0
    max_h = -1
    for i in range(N, 0, -1):
        h = int(data[i])
        if h >= max_h:
            count += 1
            max_h = h
    print(count)

if __name__ == '__main__':
    solve()

この解説は or-glm5.2-high によって生成されました。