概要

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

考察

1. 愚直なシミュレーションの問題点

問題文に書かれている通りのラウンドごとのシミュレーションを愚直に行うとどうなるでしょうか。 積み木の個数 \(N\) は最大で \(10^6\) です。1ラウンドで取り除かれる積み木が少なく、何回もラウンドを繰り返す必要がある場合、シミュレーションの計算量は最悪で \(O(N^2)\) になり、実行時間制限（TLE）になってしまいます。 そのため、シミュレーションを実際に行うことなく、最終的な状態を高速に判定する法則を見つける必要があります。

2. 操作の性質を考える（重要な気づき）

操作のルールをよく観察してみましょう。 カーソル \(k\) は右端から左へと動いていきます。 もし \(H_k > H_{k-1}\)（右隣の方が高い）であれば、左隣の \(H_{k-1}\) が取り除かれます。 取り除かれた後、もともと位置 \(k\) にあった積み木は位置 \(k-1\) に移動し、次はさらにその左隣の \(H_{k-2}\) と比較されます。

これはつまり、「ある高い積み木が、その左側にある自分より低い積み木を次々と『食べて』消し去っていく」という動きをしています。

具体例として、積み木の高さが左から [3, 1, 4] だったとします。 1. 右端の 4 とその左の 1 を比較します。 4 > 1 なので、 1 が消えて [3, 4] になります。 2. 次に、左にずれた 4 とその左の 3 を比較します。 4 > 3 なので、 3 が消えて [4] になります。

このように、右側にある大きな要素は、左側にある自身より小さい要素をすべて消し去るまで左へと進み続けます。この「捕食」プロセスは、自分以上の高さの積み木に出会うまで止まりません。

3. どの積み木が生き残るか？

この性質から、ある積み木 \(H_i\) が生き残るための条件を考えることができます。

• もし、 \(H_i\) より右側に \(H_i\) 以上の高さを持つ積み木が存在する場合：
  • その右側にある高い積み木が左へと進んできて、最終的に \(H_i\) は消されてしまいます。
• 一方、 \(H_i\) より右側にあるすべての積み木が \(H_i\) 未満である場合：
  • 右側からどんなに積み木が消しながら進んできても、 \(H_i\) より高いものは存在しないため、 \(H_i\) を消すことはできません。よって、 \(H_i\) は必ず生き残ります。

したがって、「右から左に見ていったときに、それまでに現れた最大値以上の高さを持つ積み木」だけが最終的に生き残ることになります。

アルゴリズム

この規則性を利用すると、配列を右から左へ1回走査するだけで答えを求めることができます。

1. 生き残る積み木の個数を表す変数 ans = 0、これまでに現れた積み木の最大高さを表す変数 max_val = 0 を用意します。
2. 積み木の列を右端（\(i = N-1\)）から左端（\(i = 0\)）に向かって順番に見ていきます。
3. 現在見ている積み木の高さ \(H_i\) が、これまでの最大値 max_val 以上である場合：
   • この積み木は生き残るため、 ans を 1 増やします。
   • 最大値を更新するため、 max_val = H_i とします。
4. すべての積み木を見終えたときの ans の値を出力します。

計算量

• 時間計算量: \(O(N)\) 配列を右から左へ1回走査するだけなので、積み木の数 \(N\) に対する線形時間 \(O(N)\) で解くことができます。 \(N = 10^6\) でも実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\) 入力を保存するための配列（std::vector）のメモリ空間として \(O(N)\) を使用します。

実装のポイント

• 高速な入出力: C++では \(N = 10^6\) と入力が非常に大きいため、 std::cin の速度がボトルネックになることがあります。 ios_base::sync_with_stdio(false); cin.tie(NULL); を記述することで、入出力を高速化しています。

• 右からの走査: ループのインデックスを i = n - 1 から i >= 0 までデクリメント（--i）しながら回すことで、右から左への走査をシンプルに実現しています。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (cin >> n) {
        vector<int> h(n);
        for (int i = 0; i < n; ++i) {
            cin >> h[i];
        }

        int ans = 0;
        int max_val = 0;
        // 右から左に走査し、これまでの最大値以上の要素のみが残る
        for (int i = n - 1; i >= 0; --i) {
            if (h[i] >= max_val) {
                ans++;
                max_val = h[i];
            }
        }

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

---

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