Donutsプロコンチャレンジ2015 C問題 行列のできるドーナツ屋

これはできなかったのが悔やまれる…。
N人(身長がバラバラ)が並んでいて、i人目に関して、その人が前を見た時に見える人の数を出力する問題。

問題を簡単化する。
普通に考えるとi人目に関して、それより前のj人目を見て、そのiとjの間に二人より大きな人が存在しなければj人目は目視することができ、それの和を取ればいい。しかしこれで考えると、どう頑張ってもO(N^3)なので見方を変える。
i人目から順に見ていくことにすると、i-1番目は見える。i-2番目はi-1番目より大きければ見える。i-3番目はi-1, i-2番目より大きければ見える…というように、実はi-1番目から1番目まで順に見ていき、身長が単調増加になるように選んだ人間の数が答えになる。

こう考えれば一気に問題が簡単になり、i番目に関してi-1番目から1番目で単調増加になるような人の和をとればO(N^2)で計算できる。でもこれでもまだ足りない。そこでstackを用いる。1番目からN番目までの人を順番に見ていき、i番目の人の身長をpushしていく。もしstackのtopにあるのもがi番目の人の身長より低ければそれ以降の人からは見えないのでpopしていく。

stackを使った問題だったが、まず問題を簡単化するのができなかった。1から順に見たり、i番目から順に見たり、テーブルを用意したり、色んな考え方を柔軟に使っていかなければいけない。

    int N; cin >> N;
    int H[N];
    rep(i, N) cin >> H[i];
    stack<int> S;
    S.push(1000000000);
    for(int i=0; i<N; i++){
        cout << len(S)-1 << endl;
        while(S.top() < H[i]) S.pop();
        S.push(H[i]);
    }