【C++】競技プログラミング用テンプレートとテクニック集

はじめに

競プロで使える実践的なC++テンプレートを網羅的に解説する。

「このテンプレにしてからAC率上がった」って人、意外と多いんじゃない？

基本設定

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

// 高速化
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // ...
}

型定義

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vpll = vector<pll>;

定数

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-9;

// 4方向・8方向
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};

マクロ

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple

便利関数

// 最小・最大更新
template<class T> bool chmin(T& a, const T& b) { 
    return b < a ? a = b, true : false; 
}
template<class T> bool chmax(T& a, const T& b) { 
    return a < b ? a = b, true : false; 
}

// 出力
template<class T> void print(const T& x) { cout << x << '\n'; }
template<class T> void print(const vector<T>& v) { 
    for (int i = 0; i < sz(v); i++) 
        cout << v[i] << " \n"[i == sz(v) - 1]; 
}

// Yes/No出力
void YN(bool b) { cout << (b ? "Yes" : "No") << '\n'; }

数学関数

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// 繰り返し二乗法
ll mod_pow(ll x, ll n, ll mod = MOD) {
    ll res = 1;
    x %= mod;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

// モジュラ逆元
ll mod_inv(ll a, ll mod = MOD) {
    return mod_pow(a, mod - 2, mod);
}

階乗と組み合わせ

vector<ll> fact, fact_inv;

void init_factorial(int n, ll mod = MOD) {
    fact.resize(n + 1);
    fact_inv.resize(n + 1);
    fact[0] = 1;
    rep(i, n) fact[i + 1] = fact[i] * (i + 1) % mod;
    fact_inv[n] = mod_inv(fact[n], mod);
    rrep(i, n) fact_inv[i] = fact_inv[i + 1] * (i + 1) % mod;
}

ll nCr(int n, int r, ll mod = MOD) {
    if (r < 0 || n < r) return 0;
    return fact[n] * fact_inv[r] % mod * fact_inv[n - r] % mod;
}

ll nPr(int n, int r, ll mod = MOD) {
    if (r < 0 || n < r) return 0;
    return fact[n] * fact_inv[n - r] % mod;
}

Union-Find

class UnionFind {
public:
    vector<int> par, rank_, siz;
    
    UnionFind(int n) : par(n), rank_(n, 0), siz(n, 1) {
        iota(all(par), 0);
    }
    
    int find(int x) {
        if (par[x] == x) return x;
        return par[x] = find(par[x]);  // 経路圧縮
    }
    
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (rank_[x] < rank_[y]) swap(x, y);
        par[y] = x;
        siz[x] += siz[y];
        if (rank_[x] == rank_[y]) rank_[x]++;
    }
    
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return siz[find(x)]; }
};

セグメント木

template<typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T identity;
    function<T(T, T)> op;
    
public:
    SegmentTree(int size, T id, function<T(T, T)> operation)
        : identity(id), op(operation) {
        n = 1;
        while (n < size) n *= 2;
        tree.assign(2 * n, identity);
    }
    
    void update(int i, T x) {
        i += n;
        tree[i] = x;
        while (i > 1) {
            i /= 2;
            tree[i] = op(tree[2 * i], tree[2 * i + 1]);
        }
    }
    
    T query(int l, int r) {  // [l, r)
        T res_l = identity, res_r = identity;
        l += n; r += n;
        while (l < r) {
            if (l & 1) res_l = op(res_l, tree[l++]);
            if (r & 1) res_r = op(tree[--r], res_r);
            l /= 2; r /= 2;
        }
        return op(res_l, res_r);
    }
};

// 使用例
SegmentTree<ll> seg(n, 0, [](ll a, ll b) { return a + b; });  // 区間和
SegmentTree<ll> seg(n, LINF, [](ll a, ll b) { return min(a, b); });  // 区間最小

グラフ

using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;  // 重み付き

// BFS
vi bfs(const Graph& g, int s) {
    vi dist(sz(g), -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : g[v]) {
            if (dist[u] < 0) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    return dist;
}

// ダイクストラ
vll dijkstra(const WGraph& g, int s) {
    vll dist(sz(g), LINF);
    priority_queue<pll, vpll, greater<pll>> pq;
    dist[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();
        if (d > dist[v]) continue;
        for (auto [u, w] : g[v]) {
            if (chmin(dist[u], dist[v] + w)) {
                pq.emplace(dist[u], u);
            }
        }
    }
    return dist;
}

実行結果

=== 型定義 ===
ll max: 1000000000000000000
pair: (1, 2)
vector: 1 2 3

=== マクロ ===
Original: 5 2 8 1 9
Sorted: 1 2 5 8 9
Reverse sorted: 9 8 5 2 1

=== chmin/chmax ===
x = 10
chmin(x, 5): x = 5
chmax(x, 15): x = 15

=== 数学関数 ===
gcd(24, 36) = 12
lcm(4, 6) = 12
2^10 mod 1e9+7 = 1024
10C3 = 120

=== Union-Find ===
same(0, 3): Yes
same(0, 4): No
size(0): 4

=== セグメント木 ===
sum[0, 5) = 15
sum[1, 4) = 9
After update(2, 10): sum[0, 5) = 22

=== BFS ===
Distance from 0: 0 1 2 3 4

=== ダイクストラ ===
Distance from 0: 0 1 3 4

完全テンプレート

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

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
template<class T> bool chmin(T& a, const T& b) { return b < a ? a = b, true : false; }
template<class T> bool chmax(T& a, const T& b) { return a < b ? a = b, true : false; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // ここに解答を書く
    
    return 0;
}

まとめ

このテンプレートで多くの競プロ問題に対応できます。必要に応じてカスタマイズしてください！