for 文って、本当に 1 回回すだけでいろんな処理ができる!!!
問題概要
の順列 が与えられる。
- が の最小値となっている
という条件を満たす が何個あるかを数えよ。
制約
考えたこと
つまり「先頭から 個もってきたときに、 番目が最小値」となっているような が何通りあるかを数えればよい。これは、もし の計算量をかけてよいならば、簡単にできる。
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;
という感じ。しかし今回はこれを で行わなければならない。二重の 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; }