atcoder よく使う関数, アルゴリズムのまとめ (c++)

C++でよく使う関数の覚書です.
それ、このライブラリで簡単に計算できるよみたいなのあれば教えて頂きたいです.

最初に貼るといいやつ

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

stdの関数

next_permutation

順列の全探索で使える.

int main(){
  cin >> R;
  int r[R];
  rep(i, R)cin >> r[i];
  do{
    //処理
  }while(next_permutation(r , r+R));//数列の順列全探索を実行する. 
  cout << ans << endl;
}

アルゴリズム

整数編

GCD

ユークリッドの互除法で最大公約数を求める関数.

ll gcd(ll a, ll b){
  if (a%b == 0){return b;}
  else{return(gcd(b, a%b));}
}

エラトステネスの篩

$N$ 以下の素数を求める. $O(N \log \log N)$
参考文献 蟻ホン

int N = 100010;
int prime[100010];//i番目の素数
bool is_prime[100011]; //is_prime[i] がTrueならiは素数

int sieve(int n){
  int p = 0;
  for (int i = 0; i <= n; i++) is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; i++){
    if (is_prime[i]){
      prime[p++] = i;
      for (int j = 2*i; j <=n; j+=i) is_prime[j] = false;
    }
  }
  return p;//pは素数の数
}

素因数分解

$O(\sqrt{N})$で素因数分解する. 何度も素因数分解する場合はエラトステネスの篩で素数を列挙してからの方が速そう.
(main関数は自分がよくmapの出力方法を忘れるので消さずに残しました. )

int N;
map<int, int> prime;//[素数の値, 指数]の形で値を保持するmap
ll MOD = 1000000007;
void factorization(int n){
  int i = 2;
  int temp = n;
  if (temp % i == 0){
    if (prime.find(i) == prime.end()){
      prime[i] = 0;
    }
  }
  while (i*i <= n){
    while (temp % i == 0){
      prime[i]++;
      temp /= i;
    }
    i++;
  }
  if (temp != 1){
    prime[temp]++;
  }
}
int main(){
  cin >> N;
  factorization(N);
  for (auto itr = prime.begin(); itr != prime.end(); itr++){
    cout << itr->first << " "<< itr->second << endl;
  }
}

グラフ理論編

重みがある場合のグラフ入力の受け取り

struct edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    edge(int t, int w) : to(t), weight(w) { }
};
using gragh = vector<vector<edge>>;

int main(){
  int n, m; cin >> n >> m;
  gragh g(n);
  rep(i, m){
    int l, r, d; cin >> l >> r >> d;
    l--;
    r--;
    g[l].push_back(edge(r, d));
  }
}

ワーシャルフロイド法

グラフの任意の2頂点間の最短距離を求める.
ここで配列d[i][j] は頂点iからjへの最短距離を格納する配列である. iからjに向かう辺があるならi-jのコストをcとしてd[i][j] = cと初期化し, それ以外をinfで初期化する.
また対角線上のd[i][i]については0で初期化する.

int inf = 1000000000;
int d[200][200];

void warshall_floyd(){
  rep(k, N)rep(i, N)rep(j, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

データ構造

UnionFind

https://qiita.com/DaikiSuyama/items/444e409423bd1b4b83d7
さんのコードです。引用するだけにしようと思ったのですがマクロなどが異なってエラーになってしまったので少し個人用に改修させて頂きました。

class UnionFind{
public:
    vector<ll> parent; //parent[i]はiの親
    vector<ll> siz; //素集合のサイズを表す配列(1で初期化)
    map<ll,vector<ll>> group; //集合ごとに管理する(key:集合の代表元、value:集合の要素の配列)
    ll n; //要素数

    //コンストラクタ
    UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){ 
        //全ての要素の根が自身であるとして初期化
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //データxの属する木の根を取得(経路圧縮も行う)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//代入式の値は代入した変数の値なので、経路圧縮できる
    }

    //xとyの木を併合
    void unite(ll x,ll y){
        ll rx=root(x);//xの根
        ll ry=root(y);//yの根
        if(rx==ry) return;//同じ木にある時
        //小さい集合を大きい集合へと併合(ry→rxへ併合)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;//xとyが同じ木にない時はyの根ryをxの根rxにつける
    }

    //xとyが属する木が同じかを判定
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    //xの素集合のサイズを取得
    ll size(ll x){
        return siz[root(x)];
    }

    //素集合をそれぞれグループ化
    void grouping(){
        //経路圧縮を先に行う
        rep(i,n)root(i);
        //mapで管理する(デフォルト構築を利用)
        rep(i,n)group[parent[i]].push_back(i);
    }

    //素集合系を削除して初期化
    void clear(){
        rep(i,n){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};

BIT

atcoder の公式(?)ライブラリから引用。
アルゴリズムの詳細は蟻本のp.159-161を参照してください。
ここでは何ができるのかに絞ってまとめる。

考える対象は数列$a_1, a_2 , \cdots, a_n$であり始めは全ての$a_i$が0であるとする。

BIT主な動作として
1. iが与えられたとき$a_1 + a_2 + \cdots + a_i$を計算する(sum)
2. iとxが与えられたとき　$a_i += x$と更新する。(add)
が$O(\log N)$でできるデータ構造である。

注意すべき点として下のコードのsum(int l, int r)は区間$[l, r)$の和を求める形になってるため$[l, r]$の和を求める場合はsum(l, r+1)とする必要があることがあげられる。

template<typename T>
struct BIT{
  int n;
  vector <T> d;
  BIT(int n = 0):n(n), d(n+1){}
  void add(int i, T x = 1){
    for (i++; i <= n; i += i&-i){
      d[i] += x;
    }
  }
  T sum(int i){
    T x = 0;
    for (i++; i;i -= i&-i){
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r){
    return sum(r-1)-sum(l-1);
  }
};