競技プログラミングでよく使うコード集


はじめに

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

 言語はC++。



探索

二分探索

// ソート済みの配列
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

stack<int> st;

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

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

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

queue

queue<int> que;

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

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

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

算数・数学

最大公約数(gcd)

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

二項係数(nCk)

modの話

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;
    }

}

繰り返し二乗法

素数判定・テーブル作成

フェルマーの小定理

中国剰余定理


小技コード集

10進数の各桁の和

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

知っておくと良いこと

  • cin, cout よりも scanf, printf を使ったほうがおそらく速い
  • 普段からlong longを使っておけば忘れずに済む
  • #include <bits/stdc++.h>は便利
  • using namespace std;は便利

勉強・参考になるウェブサイト

競プロにはそこまで関係ないけど


競プロの書籍

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)


おわりに

 やる気が続く限り、このページを更新していきたい。


まとめページへのリンク

kuro-temko.hatenablog.com

kuro-temko.hatenablog.com