けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 372 D - Buildings (1Q, 緑色, 400 点)

建物の高さに関する問題 AtCoder AtCoder400点 ABC-D 緑色diff NoviSteps1Q stack 操作をstackを用いて高速化する シミュレーション:stackの活用 データ構造 非自明な線形時間 数列 後ろから解く 各kに対して

この手のスタックの問題はもうすっかり常識と化した！

問題概要

ビル 1, 2, \dots, N がこの順に並んでいる。ビル i の高さは H_{i} である。

各 i = 1, 2, \dots, N に対して、ビル i, j の間にビル H_{j} より高いものがないような j ( \gt i) の個数を求めよ。

制約

  • 1 \le N \le 2 \times 10^{5}

考えたこと

いかにもスタックを使いそうな匂いがする問題だ。

たとえば H = (3, 1, 4, 1, 5, 9, 2, 6) について、後ろから考えてみよう。次のようになる。

i H_{i} 自分より後ろにある、条件を満たす j についての H_{j} のリスト 備考
7 6 {} そもそも後ろのビルがない
6 2 {6}
5 9 {2, 6}
4 5 {9} 高さ 9 のビルが、高さ 2, 6 のビルよりも高いので、高さ 2, 6 のビルは見えなくなる
3 1 {5, 9}
2 4 {1, 5, 9}
1 1 { 4, 5, 9 } 高さ 4 より低い高さ 1 のビルは見えなくなるが、高さ 5, 9 のビルは依然として見える
0 3 {1, 4, 5, 9}

このように実験してみると、毎回次の処理をしていけばよいことがわかる。

ビル H_{i} を追加するとき、前回求めた建物リストについて、 H_{i} よりも低い建物を削除していき、新たにビル H_{i} を挿入する

この挙動はスタックとなっている。ただし、通常スタックは末尾に挿入して末尾から pop する。それに対して今回は、先頭に挿入して先頭から pop するような感じになっている。しかしながら、建物リスト全体を reverse すれば、末尾に挿入して末尾から pop するような通常のスタックになる。

スタックを用いて実装すれば全体の計算量は O(N) となる。

コード

ここでは vector<int> 型を用いてスタックを実現した。

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

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

    vector<int> st, res;
    for (int i = N-1; i >= 0; i--) {
        res.push_back(st.size());
        while (!st.empty() && st.back() < H[i]) st.pop_back();
        st.push_back(H[i]);
    }
    reverse(res.begin(), res.end());
    for (int i = 0; i < N; i++) cout << res[i] << " ";
    cout << endl;
}