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

はじめに

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

言語はC++。

よく使うコード集

基本

#include <bits/stdc++.h>
using namespace std;
 
int main() {

}

探索

二分探索

// ソート済みの配列
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(); // 先頭削除

算数・数学

素数判定

bool isprime(int n) {
    if(n < 2) return false;
    for(int i = 2; i*i <= n; ++i) {
        if(n % i == 0) return false;
    }
    return true;
}

最大公約数（gcd）

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

二項係数（nCk）

順列

  • 次の順列を求める
string s = "abc";
next_permutation(s.begin(),s.end());
cout << s << endl; // "acb"

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

図形の回転

char s0[n][n];
char s1[n][n];

// s0を90度回転
for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      s1[i][j] = s0[j][n-1-i];

三項演算子

bool flag = true;
cout << (flag? "Yes" : "No") << endl;

座標圧縮

配列の重複削除

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

文字列からn文字抜き取り

  • i番目からn文字を抜き取る
s.substr(i, n)

知っておくと良いこと

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

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

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

競プロの書籍

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

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

Amazon

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

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

Amazon

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

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

Amazon

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

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

Amazon

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

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

Amazon

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

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

Amazon

また解きたい問題集

おわりに

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