概要

積み木の列に対して、右から左へ探索し、自分より右にある積み木の最大高さを記録していくことで、最終的に残る積み木の個数を求める問題です。

考察

問題文の手順通りにシミュレーションすると、各ラウンドで列を走査し、積み木を取り除く処理を行うことになります。しかし、\(N \leq 10^6\) と大きいため、最悪の場合 \(O(N^2)\) かかる可能性がありTLE（実行時間超過）となります。そこで、操作の本質を見抜く必要があります。

ラウンドの操作に注目すると、カーソルは右から左へ移動します。位置 \(k\) の積み木が位置 \(k-1\) の積み木より大きい場合、位置 \(k-1\) の積み木が取り除かれます。これは「右側にある高い積み木が、左側にある低い積み木を押しつぶしていく」という操作と捉えることができます。

ある積み木 \(A\) が最終的に残るためには、\(A\) より右側にある積み木の中で \(A\) よりも高いものが存在してはなりません。もし存在すれば、その高い積み木が右からやってきて \(A\) を押しつぶしてしまうからです。

逆に、\(A\) が右側にあるどの積み木よりも高ければ、\(A\) は誰にも押しつぶされずに残ります。さらに、\(A\) は自身より左にある積み木を押しつぶす可能性があります。

したがって、最終的に残る積み木は「右から左へ見ていったときに、それまでの最大高さを更新した（または並んだ）積み木」のみであることが分かります。

具体例として \(H = [3, 1, 4, 1, 5, 9, 2]\) で考えてみます。 右端（2）から左端（3）へ見ていきます。 - 2: 右側に何もないので残る。最大高さを 2 に更新。 - 9: 2 より大きいので残る。最大高さを 9 に更新。 - 5: 9 より小さいので、右から 9 がやってきて押しつぶされる。消える。 - 1: 9 より小さいので消える。 - 4: 9 より小さいので消える。 - 1: 9 より小さいので消える。 - 3: 9 より小さいので消える。

結果、残るのは 9 と 2 の2個です。

アルゴリズム

上記の考察に基づき、以下のアルゴリズムで答えを求めます。 1. それまでに見た積み木の最大高さを記録する変数 max_h を \(0\) で初期化する。答えのカウント ans も \(0\) で初期化する。 2. 配列 \(H\) を右端（インデックス \(N-1\)）から左端（インデックス \(0\)）に向かってループを回す。 3. 現在見ている積み木の高さ \(H[i]\) が max_h 以上であれば、この積み木は残るため ans を \(1\) 増やし、max_h を \(H[i]\) で更新する。 4. \(H[i]\) が max_h 未満であれば、この積み木は押しつぶされるため何もしない。 5. ループ終了後、ans を出力する。

計算量

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

実装のポイント

• \(N\) が \(10^6\) と非常に大きいため、C++では ios_base::sync_with_stdio(false); cin.tie(NULL); を記述し、入出力の高速化を行う必要があります。

• 積み木の高さは \(1\) 以上であることが制約で保証されているため、max_h の初期値を \(0\) に設定しても問題なく動作します。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    int max_h = 0;
    int ans = 0;
    for (int i = N - 1; i >= 0; --i) {
        if (H[i] >= max_h) {
            ans++;
            max_h = H[i];
        }
    }
    cout << ans << "\n";
    return 0;
}

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