はじめに

　ここでは競技プログラミングでよく使うものや知っておくと便利なものについてまとめる。絶対に正しいとは言えない（保険）。コード集というよりも、勉強になるウェブサイトのリンク集になりそう。

　言語はC++。

はじめに
探索
グラフ
データ構造
算数・数学
小技コード集
知っておくと良いこと
勉強・参考になるウェブサイト
競プロの書籍
おわりに
まとめページへのリンク

探索

二分探索

けんちょんさんのコードを拝借
二分探索アルゴリズムを一般化〜めぐる式二分探索法のススメ〜 - Qiita

// ソート済みの配列
vector<int> s;

int binary_search(int key) {
    int ng = -1;
    int ok = (int)s.size();
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (s[mid] >= key) ok = mid;
        else ng = mid;
    }
    return ok;
}

グラフ

グラフ作成

グラフの持ち方には隣接リストと隣接行列があるらしい

// グラフ用の二次元配列
vector<vector<int>> g;

int main() {

    // 頂点の個数nの分だけ配列の長さを確保
    g.resize(n);

    // 辺（頂点u→頂点v）を受け取ってグラフを作る
    for(int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

}

データ構造

stack

LIFO（last in, first out）
参考：stack - cpprefjp C++日本語リファレンス

stack<int> st;

st.push(3); // 追加
st.push(5);

st.size(); // 要素数取得 → 2

int a = st.top(); // 末尾参照 → 5
st.pop(); // 末尾削除

queue

FIFO（first in, first out）
参考：queue - cpprefjp C++日本語リファレンス

queue<int> que;

que.push(3); // 追加
que.push(5);

cout << que.size(); // 要素数取得 → 2

int a = que.front(); // 先頭参照 → 3
que.pop(); // 先頭削除

算数・数学

最大公約数（gcd）

いわゆるユークリッドの互除法（名前がカッコいい）
けんちょんさんのコードを拝借
AtCoder 版！マスター・オブ・整数 (最大公約数編) - Qiita

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

二項係数（nCk）

けんちょんさんの記事を参考
よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
コードは、けんちょんさんの記事から拝借する

modの話

「1000000007で割った余りを出力せよ」と言われたときの話
参考1：1000000007で割ったあまりを求める問題勉強メモ - Qiita
参考2：数学的な性質 Wiki - yukicoder

long long mod = 1000000007;

int main() {

    long long ans = 0;
    
    // 足すたびにmodをとる
    for(int i = 0; i < n; ++i) {
        cin >> t;
        ans += (t % mod);
        ans %= mod;
    }

    // 掛けるたびにmodをとる
    for(int i = 0; i < n; ++i) {
        cin >> t;
        ans *= (t % mod);
        ans %= mod;
    }

}

繰り返し二乗法

累乗の計算を高速に
modも取りながら計算
参考：【競プロ】繰り返し二乗法と再帰関数 | なかけんの数学ノート

素数判定・テーブル作成

素数関連はコピペさせてもらうと早い
素数判定：素数判定(Is-Prime) | Luzhiled’s memo
テーブル作成：素数テーブル(Prime-Table) | Luzhiled’s memo

フェルマーの小定理

中国剰余定理

小技コード集

10進数の各桁の和

// 10進数の非負整数を渡すと、各桁の和が返ってくる
int digits_sum(int x) {
    int sum = 0;
    while(x > 0) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}