概要

各積み木が最終的に残るかどうかは、「その右側に自分より高い積み木が存在するか」だけで決まります。
右側に自分より高い積み木がなければ残り、あれば取り除かれます。

考察

整理の操作では、ある積み木が取り除かれるのは、

• その積み木の右隣にある積み木の方が高いとき

だけです。

つまり、積み木は必ず「右側にある自分より高い積み木」によって取り除かれます。
左側の積み木によって取り除かれることはありません。

ここで重要なのは、列の順番は変わらず、積み木が取り除かれて詰められるだけという点です。

残る積み木の条件

左から \(i\) 番目の積み木について考えます。

右側に自分より高い積み木がある場合

つまり、

\[ H_i < \max(H_{i+1}, H_{i+2}, \ldots, H_N) \]

である場合です。

このとき、右側にある最も高い積み木が、整理中に左へ進みながら、自分より低い積み木を取り除いていきます。
その結果、積み木 \(i\) も取り除かれます。

実は、このような積み木は最初のラウンドで取り除かれます。

右側に自分より高い積み木がない場合

つまり、

\[ H_i \geq \max(H_{i+1}, H_{i+2}, \ldots, H_N) \]

である場合です。

右側には自分より高い積み木が存在しないので、この積み木を取り除ける積み木はありません。
したがって、最後まで残ります。

特に、同じ高さの場合は「より大きい」ではないため取り除かれません。
そのため、条件は \(>\) ではなく \( \geq \) になります。

例

例えば、

\[ H = [5, 2, 4, 1, 3] \]

を考えます。

右から見ていくと、

• \(3\) は右側に何もないので残る
• \(1\) は右側に \(3\) があるので取り除かれる
• \(4\) は右側の最大値 \(3\) 以上なので残る
• \(2\) は右側に \(4\) があるので取り除かれる
• \(5\) は右側の最大値 \(4\) 以上なので残る

よって残る積み木は

\[ [5, 4, 3] \]

で、答えは \(3\) です。

素朴なシミュレーションが難しい理由

問題文通りに列から積み木を削除していくと、途中の削除が何度も発生します。

特に vector の途中要素を削除すると、そのたびに後ろの要素を詰める必要があり、\(O(N)\) かかります。
削除が最大で \(N\) 回起こるため、全体で \(O(N^2)\) になり得ます。

\(N \leq 10^6\) なので、これは間に合いません。

そこで、実際に削除をシミュレーションするのではなく、「最終的に残る条件」を利用します。

アルゴリズム

右から左へ走査しながら、これまで見た積み木の最大高さを管理します。

変数 mx を「現在見ている位置より右側にある積み木の最大高さ」とします。

右から順に見ていき、

• \(H_i \geq mx\) のとき
  右側に自分より高い積み木がないので、この積み木は残る
  答えを \(1\) 増やし、mx を更新する
• \(H_i < mx\) のとき
  右側に自分より高い積み木があるので、この積み木は取り除かれる

という処理をします。

疑似コードで書くと以下のようになります。

mx = -∞
ans = 0

for i = N-1 downto 0:
    if H[i] >= mx:
        ans += 1
        mx = H[i]

print(ans)

このようにして数えている積み木は、「右から見たときの最大値になっている積み木」です。
これは suffix maximum、つまり後ろから見た最大値です。

計算量

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

実装のポイント

• 高さ \(H_i\) は最大で \(10^9\) なので、int でも収まりますが、余裕を持って long long を使っています。

• 右側の最大値 mx の初期値は、どの高さよりも小さい値にします。

  • コードでは LLONG_MIN を使っています。

• 条件は H[i] >= mx です。

  • 同じ高さの積み木は取り除かれないため、> ではなく >= にする必要があります。

    ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];

    long long mx = LLONG_MIN;
    int ans = 0;

    for (int i = N - 1; i >= 0; i--) {
        if (H[i] >= mx) {
            ans++;
            mx = H[i];
        }
    }

    cout << ans << '\n';
    return 0;
}

---

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