【競プロ精進日記】c++習得編＜２１＞

本記事は管理人が競技プログラミングを始めたため，その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。まずはc++を習得するところから始めます。その他の記事は以下をご覧ください。

【競プロ精進日記】目次まとめ ABC Atcoder Beginner Contestの過去問を解いています。最低限のコメントと一言が添えられています。 ...

計算量

C++入門 AtCoder Programming Guide for beginners (APG4b)を1からさらっていく内容です。

#include <bits/stdc++.h>
using namespace std;

int f0(int N) {
  return 1;
}

int f1(int N, int M) {
  int s = 0;
  for (int i = 0; i < N; i++) {
    s++;
  }
  for (int i = 0; i < M; i++) {
    s++;
  }
  return s;
}

int f2(int N) {
  int s = 0;
  for (int i = 0; i < N; i++) {
      int t = N;
      int cnt = 0;
      while (t > 0) {
        cnt++;
        t /= 2;
      }
      s += cnt;
  }
  return s;
}


int f3(int N) {
  int s = 0;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      s++;
    }
  }
  return s;
}

int f4(int N) {
  int s = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      s += i + j;
    }
  }
  return s;
}

int f5(int N, int M) {
  int s = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      s += i + j;
    }
  }
  return s;
}

int main() {
  int N, M;
  cin >> N >> M;

  int a0 = -1, a1 = -1, a2 = -1, a3 = -1, a4 = -1, a5 = -1;

  // 計算量が最も大きいもの1つだけコメントアウトする
  a0 = f0(N);
  a1 = f1(N, M);
  a2 = f2(N);
  a3 = f3(N);
//  a4 = f4(N);
  a5 = f5(N, M);

  cout << "f0: " << a0 << endl;
  cout << "f1: " << a1 << endl;
  cout << "f2: " << a2 << endl;
  cout << "f3: " << a3 << endl;
  cout << "f4: " << a4 << endl;
  cout << "f5: " << a5 << endl;
}

計算量を見積もる問題でした。これは，簡単にはfor文の長さに着目すればOKです。今回の場合は，f4のみ長さNのfor文が二重になっていたため計算量は$\mathcal{O}(N^2)$になり，$N\leq10^6$では間に合いません。

f0：$\mathcal{O}(1)$
f1：$\mathcal{O}(N+M)$
f2：$\mathcal{O}(N \log N)$
f3：$\mathcal{O}(1)$
f4：$\mathcal{O}(N^2)$
f5：$\mathcal{O}(NM)$

また，以下の表は競技プログラミングに挑戦する上では頭に入れておく必要があると感じました。基本的には$2^N$のオーダーにならないように気をつける必要があり，$N^2$も$N\leq 10^6$では使えないことに驚きました。なんと$N\leq 10^8$のときは$N\log N$のオーダーでも2秒以内に収まらないのですね。ビックリです。