AtCoder Beginner Contest メモ

はじめに

AtCoderのABCで問題に詰まったときに参考にする知識をまとめます。

全探索

• 深さ優先探索(dfs)
• 幅優先探索(bfs)
  • 地図で良く用いる
• bit全探索
  • 選択する/しないを0,1で表す
• 順列
  • next_permutation

グラフ

• パスグラフの特徴
  • 次数が2以下
  • サイクルがない(木)
• サイクルの判定
  • UnionFindで辺を追加する。ただし、追加する前にその頂点が同じグラフになるかで判定する

角度

• ベクトルの外積を求めることで、2つのベクトルが時計回りなのか反時計回りなのかを判定できる
  • A × B = Ax By - Ay Bx
• 直角であるということ
  • 内積が0
• 並行であること
  • 外積が0

素数

• エラトステネスの篩(ふるい)
  • N 以下の素数を全て求めるためのアルゴリズム

vector<bool> Eratosthenes(int N){

  vector<bool> isPrime(N+1, true);
  isPrime[0] = isPrime[1] = false;

  for(int p=2;p<=N;p++){
    if(!isPrime[p]) continue;

    for(int q = p*2;q<=N;q+=p){
      isPrime[q] = false;
    }
  }

  return isPrime;
}

その他

• 繰り返し二乗法

  • a^2m = (a^m)^2
  • a^(2m+1) = (a^m)^2 * a

• 括弧列

  • 開括弧:+1,閉じ括弧:−1 として 間が 0 以上で最後が 0 だと括弧列となる
  • Stackで処理する