【競プロ精進ログ】ABC152-C

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC152-C「Low Elements」です。

ポイント

問題文が若干ややこしいですが，答えるべき内容は非常に単純です。要するに，順列$P_1,\ldots,P_N$を左から見ていって，毎回最小値を更新しながら各要素がその更新された最小値以下であるかどうかを判断していけばOKです。最小値の初期値は$P_1$で設定して，条件を満たす$i$の個数は$P_1$を設定した分の$1$で設定しましょう。

今回の問題を愚直に実装しようとすると，全ての要素についてそれ以前の要素との大小比較を行う必要があり，$O(N^2)$の計算量がかかってしまいます。一方で，上で説明した手法は左から一回だけ見ていけば事足りますので，計算量は$O(N)$で抑えることができます。このように，左から見ていって極値を保管・更新していく方法は線形時間で動作する場合が多いので覚えておくと便利です。

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;

int main(){
  int N;
  cin >> N;
  int P[N];
  rep(i, N) cin >> P[i];

  // 最小値の初期化
  int min_p = P[0];
  // 回数の初期化
  int ans = 1;
  // 2番目の要素から最後まで見ていく
  rep(i, N-1){
    // もし最小値を更新すれば
    if (min_p >= P[i+1]){
      // 最小値変数の更新
      min_p = P[i+1];
      // 回数のインクリメント
      ans++;
    }
  }
  // 出力
  cout << ans << endl;
}