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

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

AtCoder ABC 152 C - Low Elements (300 点)

for 文って、本当に 1 回回すだけでいろんな処理ができる!!!

問題へのリンク

問題概要

 1, 2, \dots, N の順列  p_{1}, \dots, p_{N} が与えられる。

  •  p_{i} p_{1}, \dots, p_{i} の最小値となっている

という条件を満たす  p_{i} が何個あるかを数えよ。

制約

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

考えたこと

つまり「先頭から  i 個もってきたときに、 i 番目が最小値」となっているような  i が何通りあるかを数えればよい。これは、もし  O(N^{2}) の計算量をかけてよいならば、簡単にできる。

int res = 0;
for (int i = 0; i < N; ++i) {
  int mi = N;
  for (int j = 0; j <= i; ++j) mi = min(mi, p[j]);
  if (p[i] == mi) ++res;
}
cout << res << endl;

という感じ。しかし今回はこれを  O(N) で行わなければならない。二重の for 文を使ってる余裕はないのだ。でも実は、上の実装のうち mi の計算に無駄があることがわかる。つまり、たとえば

  • i = 4 のときに、p[0], p[1], p[2], p[3] の最小値を求めているのに
  • i = 5 のときに、もう一度 p[0], p[1], p[2], p[3] も全部見た上で、さらに p[4] の値も見比べて最小値を求めている

という感じになっている。これはこんな風に高速化できる

  • i - 1 (前回) の時点での最小値を mi に対して、
  • i (今回) の時点での最小値は、新たに p[i] と見比べて mi = min(mi, p[i]) と更新してあげる

という風にすれば OK。これは実は累積和的な考え方でもある。

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

int main() {
    int N;
    cin >> N;
    int mi = N+1, res = 0;
    for (int i = 0; i < N; ++i) {
        int p; cin >> p;
        mi = min(mi, p);
        if (mi== p) ++res;
    }
    cout << res << endl;
}