概要

\(N\) 個の積み木に対してバブルソート風の除去操作を繰り返し、最終的に残る積み木の個数を求める問題です。結論から言うと、答えは「自分より右にあるすべての積み木以上の高さを持つ積み木」の個数となり、\(O(N)\) で求められます。

考察

操作の本質を見抜く

1ラウンドの操作は「位置 \(k\) の積み木が左隣（位置 \(k-1\)）より高いとき、左隣を取り除く」というものです。取り除きが起きると同じ積み木がさらに左隣と比較されるため、ある積み木は、自分より低い左側の積み木を次々に食べていくイメージになります。

まず、取り除かれる積み木の性質を観察します。

ある積み木が取り除かれるのは、必ず「その積み木の右側にあり、かつ高さが厳密に大きい積み木」によって食べられるときである。

したがって、次のことが言えます。

• 自分より右にあるすべての積み木以上の高さを持つ積み木（＝右向きの累積最大値）は、絶対に取り除かれない。 なぜなら、自分より高い積み木が右側に存在しないからです。

整理が終了する条件

ラウンドで1個も取り除かれないのは、どの位置 \(k\) でも「\(H_k > H_{k-1}\)」が成り立たないとき、つまり列が左から右へ非増加（広義単調減少）になっているときです。

つまり、最終的に残る列は必ず非増加列になります。

残る積み木の特定

• 残る列は非増加なので、残った積み木 \(i\) より右に、\(i\) より高い積み木は（残った中には）存在しません。
• 一方、もし積み木 \(i\) が「自分より右に厳密に高い積み木を持つ」のに残ったと仮定すると、その右側にある積み木の中で最も高いもの（これは右向き累積最大値なので必ず残る）は \(H_i\) より高く、\(i\) の右に残ってしまいます。これは残った列が非増加であることに矛盾します。

以上より、

残る積み木 ＝ 自分より右にあるすべての積み木の高さ以上である積み木（広義の右向き累積最大値）

と確定します。

素朴な方法の問題点

問題文の手順をそのまま実装すると、1ラウンドが \(O(M)\)、ラウンド数も最大で \(O(N)\) 回起こりうるため、最悪 \(O(N^2)\) となり、\(N \le 10^6\) では間に合いません。上記の考察により \(O(N)\) で答えが求まります。

アルゴリズム

配列を右から左へ走査し、これまで見た高さの最大値 maxRight を管理します。

• 現在の積み木 \(H_i\) が maxRight 以上なら、その積み木は残る（カウント \(+1\)）し、maxRight を \(H_i\) に更新する。
• そうでなければ、その積み木はいつか取り除かれるのでカウントしない。

最後まで走査したときのカウントが答えです。

具体例

\(H = [5, 3, 4, 1, 2]\) の場合、右から見ていくと：

\(i\)	\(H_i\)	maxRight（更新前）	残る？
5	2	0	○（→2）
4	1	2	×
3	4	2	○（→4）
2	3	4	×
1	5	4	○（→5）

残るのは高さ \(5, 4, 2\) の3個。実際に手順通りシミュレーションしても、最終的に列 \([5,4,2]\)（非増加）になり答えは \(3\) で一致します。

計算量

• 時間計算量: \(O(N)\)（配列を1回走査するだけ）
• 空間計算量: \(O(N)\)（高さを格納する配列）

実装のポイント

• \(N \le 10^6\) と入力が大きいため、高速な入力処理が重要です。コードでは fread で入力全体を一括読み込みし、自前の整数パーサで処理しています。標準の cin を使う場合も ios::sync_with_stdio(false) などの高速化を行うとよいでしょう。

• 判定は「\(H_i \ge\) maxRight」と等号を含める点に注意してください。問題の除去条件が「より大きい（厳密）」なので、高さが等しい積み木は取り除かれず、残る側に含まれます。

• maxRight の初期値は \(0\)（高さは常に \(1\) 以上なので、一番右の積み木は必ず残る）としておけば安全です。

  ソースコード

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

int main(){
    int N;
    // fast input
    static char buf[1 << 25];
    int len = fread(buf, 1, sizeof(buf), stdin);
    int pos = 0;
    auto readInt = [&]() -> long long {
        while(pos < len && (buf[pos] < '0' || buf[pos] > '9') && buf[pos] != '-') pos++;
        bool neg = false;
        if(pos < len && buf[pos]=='-'){ neg = true; pos++; }
        long long x = 0;
        while(pos < len && buf[pos] >= '0' && buf[pos] <= '9'){
            x = x*10 + (buf[pos]-'0');
            pos++;
        }
        return neg ? -x : x;
    };

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

    long long maxRight = 0;
    long long count = 0;
    for(int i=N-1;i>=0;i--){
        if(H[i] >= maxRight){
            count++;
            maxRight = H[i];
        }
    }

    printf("%lld\n", count);
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。