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

競技プログラミング 逐次更新記事

はじめに

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

言語は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;
}

進数変換

// 8進数の場合
string to_oct(int n){
  string s;
  while(n){
    s = to_string(n%8) + s;
    n /= 8;
  }
  return s;
}

円周率

double PI = acos(-1);

小数点の桁数指定

printf("%.10f\n", ans);

知っておくと良いこと

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

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

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

競プロの書籍

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド

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

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

世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法

世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

良問題集

おわりに

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

まとめページへのリンク

https://kuro-temko.hatenablog.com/entry/2020/06/12/184034kuro-temko.hatenablog.com

kuro-temko.hatenablog.com

kuro_temko

関連記事
コメントを書く