こういうのが素早くストレスなく書けるようになるといい感じな気がする

問題概要

海から順番に建物 $1, 2, ..., N$ があって、それぞれの高さは $H_1, H_2, \dots, H_N$ である。

海が見える建物が何個あるかを求めよ。なお、 $i$ 番目の建物から海が見えるとは $i$ より前の $1, 2, \dots, i-1$ 番目の建物よりも自分の建物が低くない状態を指す。

制約

$1 \le N \le 100$

考えたこと

$N \le 100$ なので editorial のような $O(N^{2})$ 解法が間に合う。

ここではよりオーソドックスそうな $O(N)$ 解法でやってみる。 $i$ 番目の建物から海が見える条件は

$H_{i} \ge {\rm max}(H_{1}, H_{2}, \dots, H_{i-1})$

と表すことができる。つまり $H_i$ が $i$ 番目の建物の手前の建物の最大値以上であることが条件となる。

これは以下の実装のように、

current_max という変数にそれまでの高さの最大値を格納する
H[i] と current_max との比較が終わったら、H[i] という値を加味して current_max を再び更新する

という風にしてできる。ちなみにこれは累積和ならぬ累積 max と呼ばれるものを用いている。200 点で要求される知識ではないけど、累積 max を使えば、 $O(N)$ で解くことができて、 $N \le 10^{5}$ とかでも通せるし、実装もむしろシンプルになる。

コード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; ++i) cin >> H[i];
    
    int res = 0;
    int current_max = 0;
    for (int i = 0; i < N; ++i) {
        // i 番目が、i-1 番目以前の最大値以上だったらカウント
        if (H[i] >= current_max) ++res;

        // これまでの最大値を新たに更新する
        if (current_max < H[i]) current_max = H[i];
    }
    cout << res << endl;
}

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

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

AtCoder ABC 124 B - Great Ocean View (灰色, 200 点)

問題概要

制約

考えたこと

コード