HikariMusic

HikariMusic

有為の奥山今日越えない

Algorithm

Published:

Templates of Algorithm

General / 一般

Brute-Force / 全探索

Bit Exhaustive Search / ビット全探索

ll arr[N];

void search(ll n) {
    for (ll s=0; s<(1LL<<n); ++s) {
        for (ll i=0; i<n; ++i) {
            if (s&(1LL<<i))
                "arr[i]...";
        }
    }
}

Permutation Exhaustive Search / 順列全探索

ll arr[N];

void search(ll n) {
    sort(arr, arr + n);
    do {
        for (ll i=0; i<n; ++i)
            "arr[i]...";
    } while (next_permutation(arr, arr+n));
}

DFS Exhaustive Search / DFS全探索

ll arr[N];

void search(ll p, ll n) {
    if (p==n) {
        for (ll i=0; i<n; ++i)
            "arr[i]...";
        return;
    }
    for ("next value i") {
        if ("pruning")
            continue;
        arr[p] = i;
        search(p+1, n);
        arr[p] = 0;
    }
}

ll arr[N];

bool search(ll p, ll n) {
    if (p==n) {
        if ("satisfied")
            return true;
        return false;
    }
    for ("next value i") {
        if ("pruning")
            continue;
        arr[p] = i;
        if (search(p+1, n))
            return true;
        arr[p] = 0;
    }
    return false;
}

Greedy Algorithm / 貪欲法

Greedy Algorithm / 貪欲法

vector<ll> V;

void solve(ll n) {
    sort(V.begin(), V.end(), [](ll a, ll b) {
        return "condition of a precede b";
    });
    for (ll i=0; i<n; ++i) {
        "construct with V[i]";
    }
}

Dynamic Programming / 動的計画法

Knapsack DP / ナップサックDP

ll arr[N];
ll dp[N][M];

void solve(ll n, ll m) {
    "base (dp[i][0])";
    for (ll i=1; i<=n; ++i) {
        for (ll j=1; j<=m; ++j) {
            "update dp[i][j] with dp[i-1][f(arr[i-1])]";
        }
    }
}

Digit Dp / 桁DP

ll arr[N];
ll dp[N][M][2];

void solve(ll n, ll m) {
    "base (dp[0][0][1])";
    for (ll i=0; i<n; ++i) {
        for (ll j=0; j<=m; ++j) {
            "transfer dp[i][j][0] to dp[i+1][f(0~9)       ][0]";
            "transfer dp[i][j][1] to dp[i+1][f(0~arr[i]-1)][0]";
            "transfer dp[i][j][1] to dp[i+1][f(arr[i])    ][1]";
        }
    }
}

llerval DP / 区間DP

ll arr[N];
ll dp[N][N]; // fill -1

"base (dp[i][i], dp[i][i+1])";

ll rec(ll l, ll r) {
    if (dp[l][r]!=-1)
        return dp[l][r];
    "update dp[l][r] with rec(l, i), rec(i+1, r), rec(l+1, r-1)";
    return dp[l][r];
}

Bit DP / ビットDP

ll arr[N];
ll dp[2^N][N]; // fill -1

"base (dp[1LL<<i][i], dp[s][0])";

ll rec(ll s, ll v) {
    if (dp[s][v]!=-1)
        return dp[s][v];
    "update dp[s][v] with rec(s^(1LL<<v), i)";
    return dp[s][v];
}

Binary Search / 二分探索

Binary Search / 二分探索

ll arr[M];
bool check(ll x);

ll search(ll n, ll t) {
    ll l=-1, r=n;
    while (r-l>1) {
        ll m = l + (r-l)/2;
        if (t<arr[m]) // if (check(m))
            r = m;
        else
            l = m;
    }
    return r; // arr[l] <= t < arr[r]
}

ll a[N];
vector<ll> v; // deque
set<ll> s; // map

void search(ll n, ll t) {
    sort(a, a+n);
    ll lb = lower_bound(a, a+n, t) - a; // first >= t
    ll ub = upper_bound(a, a+n, t) - a; // first > t
}

void search(ll t) {
    sort(v.begin(), v.end());
    ll lb = lower_bound(v.begin(), v.end(), t) - v.begin(); // first >= t
    ll ub = upper_bound(v.begin(), v.end(), t) - v.begin(); // first > t
}

void search(ll t) {
    auto li = s.lower_bound(t); // first >= t
    auto ui = s.upper_bound(t); // first > t
}

Ternary Search / 三分探索

ll arr[N];

ll search(ll n) {
    ll l=-1, r=n;
    while (r-l>2) {
        ll m1 = l + (r-l)/3;
        ll m2 = r - (r-l)/3;
        if (arr[m1]<arr[m2])
            l = m1;
        else
            r = m2;
    }
    return l+1; // peak
}

Data Structure / データ構造

Standard Library / 標準ライブラリ

void binary_heap() {
    priority_queue<ll> q;
    // priority_queue<ll, vector<ll>, greater<ll>> q;
    q.push("value");
    q.pop();
    ll "value" = q.top();
}

void binary_search_tree() {
    set<ll> s;
    s.insert("value");
    s.erase("value");
    auto "iterator" = s.find("value");
}

void binary_search_tree() {
    map<ll, ll> m;
    m["key"] = "value";
    ll "value" = map["key"];
    auto "iterator" = m.find("key");
}

void hash_table() {
    unordered_set<ll> s;
    s.insert("value");
    s.erase("value");
    auto "iterator" = s.find("value");
}

void hash_table() {
    unordered_map<ll, ll> m;
    m["key"] = "value";
    ll "value" = m["key"];
    auto "iterator" = m.find("key");
}

Disjoll Set Union / Union-Find木

ll par[N], siz[N];

void make_set(ll n) {
    for (ll i=0; i<n; ++i) {
        par[i] = i;
        siz[i] = 1;
    }
}

ll find_set(ll v) {
    if (par[v] == v)
        return v;
    return par[v] = find_set(par[v]);
}

void union_set(ll a, ll b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (siz[a] < siz[b])
            swap(a, b);
        par[b] = a;
        siz[a] += siz[b];
    }
}

Prefix Sum / 累積和

ll arr[N], pre[N];

void build(ll n) {
    // for (l~r: k) {
    //     pre[l] += k;
    //     pre[r+1] -= k;
    // }
    for (ll i=1; i<=n; ++i) {
        pre[i] = pre[i-1] + arr[i];
        // pre[i] += pre[i-1];
    }
}

ll query(ll l, ll r) {
    return pre[r]-pre[l-1];
    // return pre[p];
}

ll arr[H][W], pre[H][W];

void build(ll h, ll w) {
    // for ("x1~x2, y1~y2: k") {
    //     pre[x1][y1] += k;
    //     pre[x2+1][y1] -= k;
    //     pre[x1][y2+1] -= k;
    //     pre[x2+1][y2+1] += k;
    // }
    for (ll i=1; i<=h; ++i) {
        for (ll j=1; j<=w; ++j) {
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + arr[i][j];
            // pre[i][j] += pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
        }
    }
}

ll query(ll x1, ll y1, ll x2, ll y2) {
    return pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1];
    // return pre[x][y];
}

Fenwick Tree　/ フェニック木

ll arr[N], tree[N];

void build(ll n) {
    for (ll i=1; i<=n; ++i) {
        tree[i] += arr[i];
        ll r = i + (i&-i);
        if (r<=n)
            tree[r] += tree[i];
    }
}

void update(ll p, ll x, ll n) {
    while (p<=n) {
        tree[p] += x;
        p += (p&-p);
    }
}

ll query(ll l, ll r) {
    ll s = 0;
    while (r>0) {
        s += tree[r];
        r -= (r&-r);
    }
    l -= 1;
    while (l>0) {
        s -= tree[l];
        l -= (l&-l);
    }
    return s;
}

ll bound(ll t, ll n) {
    ll p = 0;
    ll s = 1;
    while ((s<<1)<=n)
        s <<= 1;
    for (; s>0; s>>=1) {
        if (p+s<=n && tree[p+s]<t) { // or <=t
            p += s;
            t -= tree[p];
        }
    }
    return p+1; // first [1,r] >= t or >t
}

Segment Tree / セグメント木

ll arr[N], tree[4*N];

ll merge(ll a, ll b) {
    return "merge a and b";
}

void build(ll v, ll tl, ll tr) {
    if (tl==tr) {
        tree[v] = arr[tl];
        return;
    }
    ll tm = (tl+tr)/2;
    build(v*2+1, tl, tm);
    build(v*2+2, tm+1, tr);
    tree[v] = merge(tree[v*2+1], tree[v*2+2]);
}

void update(ll v, ll tl, ll tr, ll p, ll x) {
    if (tl==tr) {
        tree[v] += x; // = for set
        return;
    }
    ll tm = (tl+tr)/2;
    if (p<=tm)
        update(v*2+1, tl, tm, p, x);
    else
        update(v*2+2, tm+1, tr, p, x);
    tree[v] = merge(tree[v*2+1], tree[v*2+2]);
}

ll query(ll v, ll tl, ll tr, ll l, ll r) {
    if (tl==l && tr==r)
        return tree[v];
    ll tm = (tl+tr)/2;
    if (r<=tm)
        return query(v*2+1, tl, tm, l, r);
    if (l>tm)
        return query(v*2+2, tm+1, tr, l, r);
    ll q1 = query(v*2+1, tl, tm, l, tm);
    ll q2 = query(v*2+2, tm+1, tr, tm+1, r);
    return merge(q1, q2);
}

ll arr[N], tree[4*N], lazy[4*N];

ll merge(ll a, ll b) {
    return "merge a and b";
}

void push(ll v, ll tl, ll tr) {
    // if (lazy[v]==INF) return; for set
    ll tm = (tl+tr)/2;
    tree[v*2+1] += "lazy[v] or lazy[v]*(tm-tl+1)"; // = for set
    tree[v*2+2] += "lazy[v] or lazy[v]*(tr-tm)  "; // = for set
    lazy[v*2+1] += lazy[v]; // = for set
    lazy[v*2+2] += lazy[v]; // = for set
    lazy[v] = 0; // INF for set
}

void build(ll v, ll tl, ll tr) {
    if (tl==tr) {
        tree[v] = arr[tl];
        return;
    }
    ll tm = (tl+tr)/2;
    build(v*2+1, tl, tm);
    build(v*2+2, tm+1, tr);
    tree[v] = merge(tree[v*2+1], tree[v*2+2]);
}

void update(ll v, ll tl, ll tr, ll l, ll r, ll x) {
    if (tl==l && tr==r) {
        tree[v] += "x or x*(tr-tl+1)"; // = for set
        lazy[v] += x; // = for set
        return;
    }
    push(v, tl, tr);
    ll tm = (tl+tr)/2;
    if (r<=tm)
        update(v*2+1, tl, tm, l, r, x);
    else if (l>tm)
        update(v*2+2, tm+1, tr, l, r, x);
    else {
        update(v*2+1, tl, tm, l, tm, x);
        update(v*2+2, tm+1, tr, tm+1, r, x);
    }
    tree[v] = merge(tree[v*2+1], tree[v*2+2]);
}

ll query(ll v, ll tl, ll tr, ll l, ll r) {
    if (tl==l && tr==r)
        return tree[v];
    push(v, tl, tr);
    ll tm = (tl+tr)/2;
    if (r<=tm)
        return query(v*2+1, tl, tm, l, r);
    if (l>tm)
        return query(v*2+2, tm+1, tr, l, r);
    ll q1 = query(v*2+1, tl, tm, l, tm);
    ll q2 = query(v*2+2, tm+1, tr, tm+1, r);
    return merge(q1, q2);
}

Graph / グラフ

Graph Traversal / グラフ探索

Depth First Search / 深さ優先探索

vector<ll> adj[N];
ll vis[N], dis[N], par[N];
// fill dis INF, fill par -1

void dfs(ll v, ll d, ll p) {
    vis[v] = 1;
    dis[v] = d;
    par[v] = p;
    for (ll u : adj[v]) {
        // if (u!=p && vis[u])
        //     "cycle from u (undirected)";
        if (!vis[u]) { // tree: if (u!=p)
            dfs(u, d+1, v);
        }
    }
}

vector<ll> adj[N];
ll col[N], tmi[N], tmo[N];
ll tmr;

void dfs(ll v) {
    col[v] = 1;
    tmi[v] = tmr++;
    for (ll u : adj[v]) {
        // if (col[u]==1)
        //     "cycle from u (directed)";
        if (col[u]==0) {
            dfs(u);
        }
    }
    col[v] = 2;
    tmo[v] = tmr++;
}

Breadth First Search / 幅優先探索

vector<ll> adj[N];
ll vis[N], dis[N], par[N];
// fill dis INF, fill par -1

void bfs(ll s) {
    queue<ll> q;
    vis[s] = 1;
    dis[s] = 0;
    par[s] = -1;
    q.push(s);
    while (!q.empty()) {
        ll v = q.front();
        q.pop();
        for (ll u : adj[v]) {
            if (!vis[u]) {
                vis[u] = 1;
                dis[u] = dis[v] + 1;
                par[u] = v;
                q.push(u);
            }
        }
    }
}

vector<pll> adj[N];
ll vis[N], dis[N], par[N];
// fill dis INF, fill par -1

void bfs(ll s) {
    deque<ll> q;
    dis[s] = 0;
    par[s] = -1;
    q.push_front(s);
    while (!q.empty()) {
        ll v = q.front();
        q.pop_front();
        if (vis[v])
            continue;
        vis[v] = 1;
        for (pll e : adj[v]) {
            ll u = e[0];
            ll w = e[1];
            if (dis[v]+w<dis[u]) {
                dis[u] = dis[v] + w;
                par[u] = v;
                if (w==1)
                    q.push_back(u);
                else
                    q.push_front(u);
            }
        }
    }
}

Topological Sort / トポロジカルソート

vector<ll> adj[N];
vector<ll> vis(N), arr;

void dfs(ll v) {
    vis[v] = 1;
    for (ll u : adj[v]) {
        if (!vis[u])
            dfs(u);
    }
    arr.push_back(v);
}

void topological_sort(ll n) {
    for (ll i=1; i<=n; ++i) {
        if (!vis[i])
            dfs(i);
    }
    reverse(arr.begin(), arr.end());
}

vector<ll> adj[N];
vector<ll> idg(N), arr;

void topological_sort(ll n) {
    for (ll i=1; i<=n; ++i) {
        for (ll j : adj[i])
            idg[j] += 1;
    }
    queue<ll> q;
    for (ll i=1; i<=n; ++i) {
        if (idg[i]==0)
            q.push(i);
    }
    while (!q.empty()) {
        ll v = q.front();
        q.pop();
        arr.push_back(v);
        for (ll u : adj[v]) {
            idg[u] -= 1;
            if (idg[u]==0)
                q.push(u);
        }
    }
    // if (arr.size()<n)
    //     "cycle (directed)";
}

Connectivity / 連結性

Connected Component / 連結成分

vector<ll> adj[N];
ll vis[N], com[N];

void dfs(ll v, ll c) {
    vis[v] = 1;
    com[v] = c;
    for (ll u : adj[v]) {
        if (!vis[u])
            dfs(u, c);
    }
}

void solve(ll n) {
    for (ll i=1; i<=n; ++i) {
        if (!vis[i])
            dfs(i, i);
    }
}

Strongly Connected Component / 強連結成分

vector<ll> adj[N], adj_r[N];
vector<ll> arr, vis(N), com(N);

void dfs1(ll v) {
    vis[v] = 1;
    for (ll u : adj[v]) {
        if (!vis[u])
            dfs1(u);
    }
    arr.push_back(v);
}

void dfs2(ll v, ll c) {
    vis[v] = 1;
    com[v] = c;
    for (ll u : adj_r[v]) {
        if (!vis[u])
            dfs2(u, c);
    }
}

void solve(ll n) {
    for (ll i=1; i<=n; ++i) {
        if (!vis[i])
            dfs1(i);
    }
    reverse(arr.begin(), arr.end());
    fill(vis.begin(), vis.end(), 0);
    for (ll v : arr) {
        if (!vis[v]) {
            dfs2(v, v);
        }
    }
}

Bridge / 橋

vector<ll> adj[N];
ll vis[N], tin[N], low[N];
ll tmr;

void dfs(ll v, ll p) {
    vis[v] = 1;
    tin[v] = low[v] = tmr++;
    for (ll u : adj[v]) {
        if (u==p)
            continue;
        if (vis[u])
            low[v] = min(low[v], tin[u]);
        else {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (low[u]>tin[v]) {
                "bridge: v-u ";
            }
        }
    }
}

Articulation Point / 関節点

vector<ll> adj[N];
ll vis[N], tin[N], low[N];
ll tmr;

void dfs(ll v, ll p) {
    vis[v] = 1;
    tin[v] = low[v] = tmr++;
    ll chd = 0;
    for (ll u : adj[v]) {
        if (u==p)
            continue;
        if (vis[u])
            low[v] = min(low[v], tin[u]);
        else {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (p!=-1 && low[u]>=tin[v]) {
                "articulation point: v";
            }
            chd += 1;
        }
    }
    if (p==-1 && chd>1) {
        "articulation point: v";
    }
}

Shortest Path / 最短経路

Dijkstra’s Algorithm / ダイクストラ法

vector<pll> adj[N];
ll vis[N], dis[N], par[N];
// fill dis INF, fill par -1

void dijkstra(ll s) {
    priority_queue<pll, vector<pll>, greater<pll>> q;
    dis[s] = 0;
    par[s] = -1;
    q.push({0, s});
    while (!q.empty()) {
        ll v = q.top()[1];
        q.pop();
        if (vis[v])
            continue;
        vis[v] = 1;
        for (pll e : adj[v]) {
            ll u = e[0];
            ll w = e[1];
            if (dis[v]+w<dis[u]) {
                dis[u] = dis[v]+w;
                par[u] = v;
                q.push({dis[v]+w, u});
            }
        }
    }
}

ll adj[N][N];
ll vis[N], dis[N], par[N];
// fill dis INF, fill par -1

void dijkstra(ll s, ll n) {
    dis[s] = 0;
    par[s] = -1;
    for (ll i=0; i<n; ++i) {
        ll v = -1;
        for (ll j=1; j<=n; ++j) {
            if (!vis[j] && (v==-1 || dis[j]<dis[v]))
                v = j;
        }
        if (dis[v]==INF)
            break;
        vis[v] = 1;
        for (ll u=1; u<=n; ++u) {
            if (adj[v][u]<INF && dis[v]+adj[v][u]<dis[u]) {
                dis[u] = dis[v]+adj[v][u];
                par[u] = v;
            }
        }
    }
}

Bellman–Ford Algorithm / ベルマン–フォード法

struct edge{
    ll a, b, w;
};

vector<edge> edges;
ll dis[N], par[N];
// fill dis INF, fill par -1

void bellman_ford(ll s, ll n) {
    dis[s] = 0;
    par[s] = -1;
    ll x = -1;
    for (ll i=0; i<n; ++i) {
        x = -1;
        for (edge e : edges) {
            if (dis[e.a]<INF && dis[e.a]+e.w<dis[e.b]) {
                dis[e.b] = dis[e.a] + e.w;
                par[e.b] = e.a;
                x = e.b;
            }
        }
        if (x==-1)
            break;
    }
    // if (x!=-1) {
    //     for (ll i=0; i<n; ++i)
    //         x = par[x];
    //     "negative cycle from x";
    // }
}

Floyd–Warshall Algorithm / ワーシャル–フロイド法

ll dis[N][N], par[N][N];
// fill dis INF, fill par -1

void floyd_warshall(ll n) {
    "for edge: dis[v][u]=w, par[v][u]=v";
    "for vert: dis[v][v]=0, par[v][v]=v";
    for (ll k=1; k<=n; ++k) {
        for (ll i=1; i<=n; ++i) {
            for (ll j=1; j<=n; ++j) {
                if (dis[i][k]<INF && dis[k][j]<INF && dis[i][k]+dis[k][j]<dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    par[i][j] = par[k][j];
                }
            }
        }
    }
    // for (ll i=0; i<n; ++i)
    //     if (dis[i][i]<0) 
    //         "negative cycle from i";
}

Minimum Spanning Tree / 最小全域木

Prim’s Algorithm / プリム法

vector<pll> adj[N];
ll vis[N], dis[N], par[N];
// fill dis INF, fill par -1

ll prim(ll s, ll n) {
    ll wt = 0;
    ll cnt = 0;
    priority_queue<pll, vector<pll>, greater<pll>> q;
    dis[s] = 0;
    par[s] = -1;
    q.push({0, s});
    while (!q.empty()) {
        ll v = q.top()[1];
        q.pop();
        if (vis[v])
            continue;
        vis[v] = 1;
        cnt += 1;
        wt += dis[v];
        for (pll e : adj[v]) {
            ll u = e[0];
            ll w = e[1];
            if (!vis[u] && w<dis[u]) {
                dis[u] = w;
                par[u] = v;
                q.push({dis[u], u});
            }
        }
    }
    if (cnt<n)
        return INF;
    return wt;
}

ll adj[N][N];
ll vis[N], dis[N], par[N];
// fill dis INF, fill par -1

ll prim(ll s, ll n) {
    ll wt = 0;
    dis[s] = 0;
    par[s] = -1;
    for (ll i=0; i<n; ++i) {
        ll v = -1;
        for (ll j=1; j<=n; ++j) {
            if (!vis[j] && (v==-1 || dis[j]<dis[v]))
                v = j;
        }
        if (dis[v]==INF)
            return INF;
        vis[v] = 1;
        wt += dis[v];
        for (ll j=1; j<=n; ++j) {
            if (!vis[j] && adj[v][j]<dis[j]) {
                dis[j] = adj[v][j];
                par[j] = v;
            }
        }
    }
    return wt;
}

Kruskal’s Algorithm / クラスカル法

struct edge {
    ll a, b, w;
    bool operator<(edge const& other) const {
        return w < other.w;
    }
};

vector<edge> edges;
ll par[N], siz[N];

void make_set(ll n) {
    for (ll i=1; i<=n; ++i) {
        par[i] = i;
        siz[i] = 1;
    }
}

ll find_set(ll v) {
    if (par[v] == v)
        return v;
    return par[v] = find_set(par[v]);
}

void union_set(ll a, ll b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (siz[a] < siz[b])
            swap(a, b);
        par[b] = a;
        siz[a] += siz[b];
    }
}

ll kruskal(ll n) {
    ll wt = 0;
    ll cnt = 0;
    make_set(n);
    sort(edges.begin(), edges.end());
    for (edge e : edges) {
        if (find_set(e.a) != find_set(e.b)) {
            wt += e.w;
            cnt += 1;
            union_set(e.a, e.b);
        }
    }
    if (cnt<n-1)
        return INF;
    return wt;
}

Network Flow / ネットワークフロー

Maximum Flow / 最大流

struct edge{
    ll v, u, c;
};

vector<ll> adj[N];
vector<edge> edges;
vector<ll> lev(N), ptr(N);

void add_edge(ll v, ll u, ll c) {
    ll m = edges.size();
    adj[v].push_back(m);
    adj[u].push_back(m+1);
    edges.push_back({v, u, c});
    edges.push_back({u, v, 0}); // undirected: {u, v, c}
}

bool bfs(ll s, ll t) {
    fill(lev.begin(), lev.end(), -1);
    lev[s] = 0;
    queue<ll> q;
    q.push(s);
    while (!q.empty()) {
        ll v = q.front();
        q.pop();
        for (ll id : adj[v]) {
            edge e = edges[id];
            if (e.c>0 && lev[e.u]==-1) {
                lev[e.u] = lev[e.v] + 1;
                q.push(e.u);
            }
        }
    }
    return lev[t]!=-1;
}

ll dfs(ll v, ll t, ll p) {
    if (v==t)
        return p;
    for (ll& cid=ptr[v]; cid<(ll)adj[v].size(); ++cid) {
        ll id = adj[v][cid];
        edge e = edges[id];
        if (e.c>0 && lev[e.u]==lev[e.v]+1) {
            ll tr = dfs(e.u, t, min(p, e.c));
            if (tr>0) {
                edges[id].c -= tr;
                edges[id^1].c += tr;
                return tr;
            }
        }
    }
    return 0;
}

ll dinic(ll s, ll t) {
    ll f = 0;
    while (bfs(s, t)) {
        fill(ptr.begin(), ptr.end(), 0);
        while (ll p = dfs(s, t, INF)) {
            f += p;
        }
    }
    return f; // also minimum cut
}

Minimum-Cost Flow / 最小費用流

struct edge {
    ll v, u, c, w;
};

vector<ll> adj[N];
vector<edge> edges;
vector<ll> dis(N), par_e(N), inq(N);

void add_edge(ll v, ll u, ll c, ll w) {
    ll m = edges.size();
    adj[v].push_back(m);
    adj[u].push_back(m+1);
    edges.push_back({v, u, c, w});
    edges.push_back({u, v, 0, -w});
}

bool spfa(ll s, ll t) {
    fill(dis.begin(), dis.end(), INF);
    fill(inq.begin(), inq.end(), 0);
    queue<ll> q;
    dis[s] = 0;
    q.push(s);
    inq[s] = 1;
    while (!q.empty()) {
        ll v = q.front();
        q.pop();
        inq[v] = 0;
        for (ll id : adj[v]) {
            edge e = edges[id];
            if (e.c>0 && dis[e.v]<INF && dis[e.v]+e.w<dis[e.u]) {
                dis[e.u] = dis[e.v] + e.w;
                par_e[e.u] = id;
                if (!inq[e.u]) {
                    q.push(e.u);
                    inq[e.u] = 1;
                }
            }
        }
    }
    return dis[t]<INF;
}

pll solve(ll s, ll t, ll k) {
    ll f = 0;
    ll w = 0;
    while (f<k) {
        if (!spfa(s, t))
            break;
        ll p = k-f;
        ll cur = t;
        while (cur!=s) {
            ll id = par_e[cur];
            p = min(p, edges[id].c);
            cur = edges[id].v;
        }
        cur = t;
        while (cur!=s) {
            ll id = par_e[cur];
            edges[id].c -= p;
            edges[id^1].c += p;
            w += p * edges[id].w;
            cur = edges[id].v;
        }
        f += p;
    }
    return {f, w}; // max_flow <=k, then min_cost
}

Bipartite Matching / 二部マッチング

vector<ll> adj[N];
vector<ll> vis(N), mat(M);

bool dfs(ll v) {
    if (vis[v])
        return false;
    vis[v] = 1;
    for (ll u : adj[v]) {
        ll w = mat[u];
        if (w==-1 || dfs(w)) {
            mat[u] = v;
            return true;
        }
    }
    return false;
}

ll solve(ll n) {
    ll f = 0;
    fill(mat.begin(), mat.end(), -1);
    for (ll i=1; i<=n; ++i) {
        fill(vis.begin(), vis.end(), 0);
        if (dfs(i))
            f += 1;
    }
    return f;
}

Tree Algorithm / 木アルゴリズム

Tree Diameter / 木の直径

vector<ll> adj[N];
vector<ll> par(N);

pll dfs(ll v, ll d, ll p) {
    par[v] = p;
    pair<ll, ll> res{d, v};
    for (ll u : adj[v]) {
        if (u!=p)
            res = max(res, dfs(u, d+1, v));
    }
    return res;
}

ll solve() {
    ll s = dfs(1, 0, -1)[1];
    ll d = dfs(s, 0, -1)[0];
    // ll t = dfs(s, 0, -1)[1];
    // while (t!=-1) {
    //     arr.push_back(t);
    //     t = par[t];
    // }
    return d;
}

Tree DP / 木DP

vector<ll> adj[N];
ll dp[N][S];

void dfs(ll v, ll p) {
    "base (dp[v][s])";
    for (ll u : adj[v]) {
        if (u==p)
            continue;
        dfs(u, v);
        "update dp[v][i] with dp[u][j]";
    }
}

vector<ll> adj[N];
ll siz[N], dp[N][S];

void dfs(ll v, ll p) {
    siz[v] = 1;
    "base (dp[v][s])";
    for (ll u : adj[v]) {
        if (u==p)
            continue;
        dfs(u, v);
        vector<ll> tp(S);
        for (ll i=0; i<siz[v]; ++i) {
            for (ll j=0; j<siz[u]; ++j) {
                "update tp[s] with dp[v][i] & dp[u][j]";
            }
        }
        siz[v] += siz[u];
        for (ll s=0; s<siz[v]; ++s)
            dp[v][s] = tp[s];
    }
}

Euler Tour / オイラーツアー

vector<ll> arr;
ll tmi[N], tmo[N], tmr;

void dfs(ll v, ll p) {
    tmi[v] = tmr++;
    arr.push_back(v);
    for (ll u : adj[v]) {
        if (u!=p) {
            dfs(u, v);
        }
    }
    tmo[v] = tmr;
}

vector<ll> arr;
ll occ[N], dep[N];

void dfs(ll v, ll p, ll d) {
    occ[v] = (ll)arr.size();
    dep[v] = d;
    arr.push_back(v);
    for (ll u : adj[v]) {
        if (u!=p) {
            dfs(u, v, d+1);
            arr.push_back(v);
        }
    }
}

Lowest Common Ancestor / 最近共通祖先

vector<ll> adj[N];
ll dep[N], par[N][LogN];

void dfs(ll v, ll d, ll p) {
    dep[v] = d;
    par[v][0] = p;
    for (ll u : adj[v]) {
        if (u!=p)
            dfs(u, d+1, v);
    }
}

void build(ll n, ll l_n) {
    dfs(1, 0, 0);
    for (ll s=1; s<l_n; ++s) {
        for (ll i=1; i<=n; ++i)
            par[i][s] = par[par[i][s-1]][s-1];
    }
}

ll lca(ll a, ll b, ll l_n) {
    if (dep[a]<dep[b])
        swap(a, b);
    for (ll s=l_n-1; s>=0; --s) {
        if ((dep[a]-dep[b])&(1LL<<s))
            a = par[a][s];
    }
    if (a==b)
        return a;
    for (ll k=l_n-1; k>=0; --k) {
        if (par[a][k]!=par[b][k]) {
            a = par[a][k];
            b = par[b][k];
        }
    }
    return par[a][0];
}

vector<ll> adj[N], arr;
ll dep[N], occ[N];
ll lg[2*N], st[2*N][LogN+1];

void dfs(ll v, ll d, ll p) {
    occ[v] = arr.size();
    dep[v] = d;
    arr.push_back(v);
    for (ll u : adj[v]) {
        if (u!=p) {
            dfs(u, d+1, v);
            arr.push_back(v);
        }
    }
}

void build(ll s) {
    dfs(s, 0, 0);
    ll m = arr.size();
    lg[1] = 0;
    for (ll i=2; i<=m; ++i)
        lg[i] = lg[i/2]+1;
    for (ll i=0; i<m; ++i)
        st[i][0] = arr[i];
    for (ll j=1; j<=lg[m]; ++j) {
        for (ll i=0; i+(1LL<<j)<=m; ++i) {
            ll v1 = st[i][j-1];
            ll v2 = st[i+(1LL<<(j-1))][j-1];
            st[i][j] = (dep[v1]<dep[v2])?v1:v2;
        }
    }
}

ll lca(ll a, ll b) {
    ll l=occ[a], r=occ[b];
    if (l>r)
        swap(l, r);
    ll k = lg[r-l+1];
    ll v1 = st[l][k];
    ll v2 = st[r-(1LL<<k)+1][k];
    return (dep[v1]<dep[v2])?v1:v2;
}

Centroid Decomposition / 重心分解

vector<ll> adj[N];
ll siz[N], cen[N];

void calsize(ll v, ll p) {
    siz[v] = 1;
    for (ll u : adj[v]) {
        if (u==p || cen[u])
            continue;
        calsize(u, v);
        siz[v] += siz[u];
    }
}

ll centroid(ll v, ll p, ll t) {
    for (ll u : adj[v]) {
        if (u==p || cen[u])
            continue;
        if (siz[u]>t/2)
            return centroid(u, v, t);
    }
    return v;
}

void build(ll v) {
    calsize(v, -1);
    ll c = centroid(v, -1, siz[v]);
    cen[c] = 1;
    for (ll u : adj[c]) {
        if (cen[u])
            continue;
        build(u);
    }
}

Math / 数学

Modular Arithmetic / 合同算術

Mod Library / Modライブラリ

ll madd(ll a, ll b) {
    a = (a % MOD + MOD) % MOD;
    b = (b % MOD + MOD) % MOD;
    return (a + b) % MOD;
}

ll msub(ll a, ll b) {
    a = (a % MOD + MOD) % MOD;
    b = (b % MOD + MOD) % MOD;
    return (a - b + MOD) % MOD;
}

ll mmul(ll a, ll b) {
    a = (a % MOD + MOD) % MOD;
    b = (b % MOD + MOD) % MOD;
    return (a * b) % MOD;
}

ll mpow(ll a, ll n) {
    ll res = 1;
    while (n>0) {
        if (n&1)
            res = mmul(res, a);
        a = mmul(a, a);
        n >>= 1;
    }
    return res;
}

ll minv(ll a) {
    return mpow(a, MOD-2);
}

ll mdiv(ll a, ll b) {
    return mmul(a, minv(b));
}

Binary Exponentiation / 繰り返し二乗法

ll binpow(ll a, ll n, ll m) {
    ll res = 1;
    while (n>0) {
        if (n&1)
            res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

Modular Inverse / モジュラ逆数

ll modinv(ll a, ll m) { // m is prime
    return binpow(a, m-2, m);
}

ll modinv(ll a, ll m) { // a m coprime
    ll x, y;
    extgcd(a, m, x, y);
    return ((x % m) + m) % m;
}

Binomial Coefficient / 二項係数

ll fac[N], inv[N], finv[N];

void init(ll n, ll m) {
    fac[0] = inv[0] = finv[0] = 1;
    fac[1] = inv[1] = finv[1] = 1;
    for (ll i=2; i<=n; ++i) {
        fac[i] = fac[i-1] * i % m;
        inv[i] = m - inv[m%i] * (m/i) % m;
        finv[i] = finv[i-1] * inv[i] % m;
    }
}

ll binom(ll n, ll k, ll m) {
    if (k<0 || k>n)
        return 0;
    return fac[n] * (finv[n-k] * finv[k] % m) % m; 
}

ll binom(ll n, ll k, ll m) {
    if (k<0 || k>n)
        return 0;
    k = min(k, n-k);
    ll a = 1;
    ll b = 1;
    for (ll i=1; i<=k; ++i) {
        a = a * (n-i+1) % m;
        b = b * i % m;
    }
    return a * binpow(b, m-2, m) % m;
}

Divisor & Prime / 約数と素数

Euclidean Algorithm / ユークリッドの互除法

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

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

ll extgcd(ll a, ll b, ll& x, ll& y) {
    if (b==0) {
        x = 1;
        y = 0;
        return a;
    }
    ll g, x1, y1;
    g = extgcd(b, a%b, x1, y1);
    x = y1;
    y = x1 - y1*(a/b);
    return g;
}

Divisor Enumeration / 約数列挙

vll divisor(ll n) {
    vector<ll> res;
    for (ll i=1; i*i<=n; ++i) {
        if (n%i==0) {
            res.push_back(i);
            if (n/i!=i)
                res.push_back(n/i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

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

Prime Factorization / 素因数分解

vector<pll> factor(ll n) {
    vector<pll> res;
    for (ll i=2; i*i<=n; ++i) {
        if (n%i==0) {
            ll p = 0;
            while (n%i==0) {
                n /= i;
                p += 1;
            }
            res.push_back({i, p});
        }
    }
    if (n!=1)
        res.push_back({n, 1});
    return res;
}

ll phi(ll n) {
    ll res = n;
    for (ll i=2; i*i<=n; ++i) {
        if (n%i==0) {
            while (n%i==0)
                n /= i;
            res -= res / i;
        }
    }
    if (n!=1)
        res -= res / n;
    return res;
}

Sieve of Eratosthenes / エラトステネスの篩

bool prime[N];

void sieve(ll n) {
    prime[0] = prime[1] = false;
    for (ll i=2; i<=n; ++i)
        prime[i] = true;
    for (ll i=2; i*i<=n; ++i) {
        if (!prime[i])
            continue;
        for (ll j=i*i; j<=n; j+=i)
            prime[j] = false;
    }
}

vector<ll> lp(N), pr;

void sieve(ll n) {
    for (ll i=2; i<=n; ++i) {
        if (lp[i]==0) {
            lp[i] = i;
            pr.push_back(i);
        }
        for (ll j=0; j<(ll)pr.size() && pr[j]*i<=n; ++j) {
            lp[i*pr[j]] = pr[j];
            if (pr[j]==lp[i])
                break;
        }
    }
}

// is prime: lp[i]==i
// factorize: while (x>1) x/=lp[x]

Linear Algebra / 線型代数

Matrix Exponentiation / 行列累乗

mll matmul(mll& A, mll& B, ll m) {
    mll C(A.size(), vll(B[0].size()));
    for (ll i=0; i<A.size(); ++i) {
        for (ll j=0; j<B[0].size(); ++j) {
            for (ll k=0; k<A[0].size(); ++k)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % m;
        }
    }
    return C;
}

mll matpow(mll X, ll n, ll m) {
    mll R(X.size(), vll(X.size()));
    for (ll i=0; i<X.size(); ++i)
        R[i][i] = 1;
    while (n>0) {
        if (n&1)
            R = matmul(R, X, m);
        X = matmul(X, X, m);
        n >>= 1;
    }
    return R;
}

Chinese Remainder Theorem / 中国剰余定理

ll extgcd(ll a, ll b, ll& x, ll& y) {
    if (b==0) {
        x = 1;
        y = 0;
        return a;
    }
    ll g, x1, y1;
    g = extgcd(b, a%b, x1, y1);
    x = y1;
    y = x1 - y1*(a/b);
    return g;
}

ll modinv(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return ((x % m) + m) % m;
}

pll CRT(vll& A, vll& B, vll& M) {
    ll x=0, m=1;
    for (ll i=0; i<A.size(); ++i) {
        ll a=A[i]*m, b=B[i]-A[i]*x, d=gcd(a, M[i]);
        if (b%d!=0)
            return {0, -1};
        ll y = (b/d) * modinv(a/d, M[i]/d) % (M[i]/d);
        x += m*y;
        m *= M[i]/d;
    }
    return {(x%m+m)%m, m}; // {a, b}: x ≡ a (mod b)
}

Gaussian Elimination / ガウスの消去法

vector<ld> gauss(mll A, vll& B) { // ll gauss(vll A, ll B)
    ll n = A.size();
    ll m = A[0].size(); // ll m = max_bit
    vector<vector<ld>> M(n, vector<ld>(m+1)); // vector<ll> M(n);
    for (ll i=0; i<n; ++i) {
        for (ll j=0; j<m; ++j) // M[i] = A[i] | (((B>>i)&1)<<m);
            M[i][j] = A[i][j]; //
        M[i][m] = B[i];        //
    }
    vector<ll> piv(m, -1);
    ll r = 0;
    for (ll c=0; c<m; ++c) {
        ll p = r;
        for (ll i=r; i<n; ++i) {
            if (abs(M[i][c])>abs(M[p][c])) // if ((M[i]>>c)&1)
                p = i;
        }
        if (abs(M[p][c])<EPS) // if (!((M[p]>>c)&1))
            continue;
        swap(M[r], M[p]);
        piv[c] = r;
        for (ll i=0; i<n; ++i) {
            if (i==r)
                continue;
            ld f = M[i][c] / M[r][c];   // if ((M[i]>>c)&1)
            for (ll j=c; j<=m; ++j)     //     M[i] ^= M[r];
                M[i][j] -= M[r][j] * f; //
        }
        r += 1;
        if (r>=n)
            break;
    }
    for (ll i=r; i<n; ++i) {
        if (abs(M[i][m])>EPS) // if ((M[i]>>m)&1)
            return {}; // return -1;
    }
    vector<ld> res(m); // ll res=0;
    for (ll j=0; j<m; ++j) {
        if (piv[j]!=-1)
            res[j] = M[piv[j]][m] / M[piv[j]][j]; 
            // res |= (((M[piv[j]]>>m)&1)<<j);
        else
            res[j] = INF; // return INF;
    }
    return res;
}

vector<ld> bas[M]; // ll bas[M];

bool insert(vector<ld> x) { // bool insert(ll x)
    ll m = x.size(); // ll m = max_bit;
    for (ll j=m-1; j>=0; --j) {
        if (abs(x[j])<EPS) // if((x&(1LL<<j))==0)
            continue;
        if (bas[j].size()>0) { // if (bas[j]!=0)
            ld c = x[j] / bas[j][j];   // x ^= bas[j];
            for (ll k=j; k>=0; --k)    //
                x[k] -= bas[j][k] * c; //
        }
        else {
            bas[j] = x;
            return 1;
        }
    }
    return 0;
}

Fast Fourier Transform / 高速フーリエ変換

void fft(vector<pt>& a, bool inv) {
    ll n = a.size();
    for (ll i=1, j=0; i<n; ++i) {
        ll b = n>>1;
        for (; j&b; b>>=1)
            j ^= b;
        j ^= b;
        if (i<j)
            swap(a[i], a[j]);
    }
    for (ll l=2; l<=n; l*=2) {
        ld ag = 2*PI / l * (inv?-1:1);
        pt wl(cos(ag), sin(ag));
        for (ll i=0; i<n; i+=l) {
            pt w(1);
            for (ll j=0; j<l/2; ++j) {
                pt u = a[i+j];
                pt v = a[i+j+l/2]*w;
                a[i+j] = u+v;
                a[i+j+l/2] = u-v;
                w *= wl;
            }
        }
    }
    if (inv) {
        for (ll i=0; i<n; ++i)
            a[i] /= n;
    }
}

vll conv(vll& a, vll& b) {
    if (min(a.size(), b.size())<=60) {
        vector<ll> res(a.size()+b.size()-1);
        for (ll i=0; i<(ll)a.size(); ++i) {
            for (ll j=0; j<(ll)b.size(); ++j)
                res[i+j] += a[i]*b[j];
        }
        return res;
    }
    vector<pt> fa(a.begin(), a.end());
    vector<pt> fb(b.begin(), b.end());
    ll s = a.size()+b.size()-1;
    ll n = 1;
    while (n<s)
        n *= 2;
    fa.resize(n);
    fb.resize(n);
    fft(fa, 0);
    fft(fb, 0);
    for (ll i=0; i<n; ++i) 
        fa[i] *= fb[i];
    fft(fa, 1);
    vector<ll> res(s);
    for (ll i=0; i<s; ++i)
        res[i] = round(fa[i].real());
    return res;
}

ll binpow(ll a, ll n, ll m) {
    ll res = 1;
    while (n>0) {
        if (n&1)
            res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

void ntt(vector<ll>& a, bool inv, ll m, ll r) { 
    ll n = a.size();
    for (ll i=1, j=0; i<n; ++i) {
        ll b = n>>1;
        for (; j&b; b>>=1)
            j ^= b;
        j ^= b;
        if (i<j)
            swap(a[i], a[j]);
    }
    for (ll l=2; l<=n; l*=2) {
        ll wl = binpow(r, (m-1)/l, m);
        if (inv)
            wl = binpow(wl, m-2, m);
        for (ll i=0; i<n; i+=l) {
            ll w = 1;
            for (ll j=0; j<l/2; ++j) {
                ll u = a[i+j];
                ll v = a[i+j+l/2] * w % m;
                a[i+j] = (u+v) % m;
                a[i+j+l/2] = (u-v+m) % m;
                w = w * wl % m;
            }
        }
    }
    if (inv) {
        ll ninv = binpow(n, m-2, m);
        for (ll i=0; i<n; ++i)
            a[i] = a[i] * ninv % m;
    }
}

// m=998244353, r=3
vll conv(vll& a, vll& b, ll m, ll r) {
    if (min(a.size(), b.size())<=60) {
        vector<ll> res(a.size()+b.size()-1);
        for (ll i=0; i<(ll)a.size(); ++i) {
            for (ll j=0; j<(ll)b.size(); ++j)
                res[i+j] = (res[i+j]+a[i]*b[j]) % m;
        }
        return res;
    }
    vector<ll> fa(a.begin(), a.end());
    vector<ll> fb(b.begin(), b.end());
    ll s = a.size()+b.size()-1;
    ll n = 1;
    while (n<s)
        n *= 2;
    fa.resize(n);
    fb.resize(n);
    ntt(fa, 0, m, r);
    ntt(fb, 0, m, r);
    for (ll i=0; i<n; ++i)
        fa[i] = fa[i] * fb[i] % m;
    ntt(fa, 1, m, r);
    fa.resize(s);
    return fa;
}

🍊 Geometry / 幾何

Geometry Library / 幾何ライブラリ

ld dist(pt a, pt b) {
    return abs(b-a);
}

ld dot(pt a, pt b) {
    return a.real()*b.real() + a.imag()*b.imag();
}

ld det(pt a, pt b) {
    return a.real()*b.imag() - a.imag()*b.real();
}

ld ang(pt a, pt b) {
    return atan2(det(a, b), dot(a, b));
}

pt rot(pt a, ld ang) {
    return a * pt{cos(ang), sin(ang)};
}

pt proj(pt a, pt b, pt c) { // a-b, c
    ld t = dot(c-a, b-a) / norm(b-a);
    return a + (b-a)*t;
}

pt inter(pt a, pt b, pt c, pt d) { // a-b, c-d
    ld s = det(b-a, d-c);
    ld t = det(c-a, d-c);
    if (abs(s)<EPS)
        return {1/EPS, 1/EPS};
    return a + (b-a)*t/s;
}

Convex Hull / 凸包

ld det(const pt &a, const pt &b) {
    return a.real()*b.imag() - a.imag()*b.real();
}

bool cmp(const pt &a, const pt &b) {
    return a.real()!=b.real() ? a.real()<b.real() : a.imag()<b.imag();
}

vector<pt> solve(vector<pt> pts) {
    sort(pts.begin(), pts.end(), cmp);
    ll n=pts.size(), p=0;
    vector<pt> res(2*n);
    for (ll i=0; i<n; ++i) {
        while (p>1 && det(res[p-1]-res[p-2], pts[i]-res[p-1])<EPS)
            p--; // <EPS: lower hull, >-EPS: upper hull
        res[p++] = pts[i];
    }
    for (ll i=n-2, t=p; i>=0; --i) {
        while (p>t && det(res[p-1]-res[p-2], pts[i]-res[p-1])<EPS)
            p--; // <EPS: upper hull, >-EPS: lower hull
        res[p++] = pts[i];
    }
    res.resize(p-1); // first hull only: resize(p)
    return res;
}

Sweep Line / 平面走査

void solve(ll n) {
    vector<pair<double, ll>> v;
    for (ll i=0; i<n; ++i) {
        v.push_back({"<x_left[i]>", i});
        v.push_back({"<x_right[i]>", i+n});
    }
    sort(v.begin(), v.end());
    set<pair<double, ll>> s;
    for (auto p : v) {
        ll i = p.second%n;
        if (p.second<n) {
            set<pair<double, ll>>::iterator it = "<binary search y[i]>";
            "<construct solution>":
            s.insert({"<y[i]>", i});
        }
        else
            s.erase({"<y[i]>", i});
    }
}

Plane Divide and Conquer / 平面の分割統治法

using Poll = complex<double>;

bool compare_x(const Poll &a, const Poll &b) {
    return a.real()<b.real();
}

bool compare_y(const Poll &a, const Poll &b) {
    return a.imag()<b.imag();
}

vector<Poll> ps;

void rec(ll l, ll r) {
    if (l==r)
        "<base case>";
    ll m = (l+r)/2;
    rec(l, m);
    rec(m+1, r);
    inplace_merge(ps.begin()+l, ps.begin()+m+1, ps.begin()+r+1, compare_y);
    "<combine>";
}

sort(ps.begin(), ps.end(), compare_x);

Others / その他の

Technique / テクニック

Two Pointers / しゃくとり法

ll arr[N];

ll solve(ll n, ll t) {
    ll ans = 0;
    ll s = 0;
    for (ll l=0, r=0; r<n; ++r) {
        s += arr[r];
        for (;l<=r && s>t; ++l) {
            s -= arr[l];
        }
        "[l, r] with s<=t";
    }
    return ans;
}

Coordinate Compression / 座標圧縮

vector<ll> xs;
unordered_map<ll, ll> id;

void solve() {
    for ("segment [l, r)") {
        xs.push_back(l);
        xs.push_back(r);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for (ll i=0; i<(ll)xs.size(); ++i)
        id[xs[i]] = i;
    for (ll i=0; i+1<(ll)xs.size(); ++i) {
        "compressed [xs[i], xs[i+1])";
    }
}

Binary Lifting / ダブリング

ll nxt[N][LogD];

void build(ll n, ll l_d) {
    for (ll i=0; i<n; ++i)
        nxt[i][0] = "next position";
    for (ll s=1; s<l_d; ++s) {
        for (ll i=0; i<n; ++i) {
            nxt[i][s] = nxt[nxt[i][s-1]][s-1];
        }
    }
}

ll query(ll p, ll d, ll l_d) {
    for (ll s=0; s<l_d; ++s) {
        if (d&(1LL<<s))
            p = nxt[p][s];
    }
    return p;
}

Meet in the Middle / 半分全列挙

void solve(ll n) {
    ll n1 = n/2, n2 = n-n/2;
    map<ll,ll> m1, m2; // set, vector
    for (ll s=0; s<(1LL<<n1); ++s) {
        for (ll i=0; i<n1; ++i) {
            if (s&(1LL<<i))
                "select i";
        }
        "insert to m1";
    }
    for (ll s=0; s<(1LL<<n2); ++s) {
        for (ll i=0; i<n2; ++i) {
            if (s&(1LL<<i))
                "select n/2+i";
        }
        "insert to m2";
    }
    for ("iterate m1") {
        if ("match m2") {
            "update ans";
        }
    }
}

Sparse Table / スパーステーブル

ll arr[N];
ll lg[N], st[N][LogN];

void build(ll n) {
    lg[1] = 0;
    for (ll i=2; i<=n; ++i)
        lg[i] = lg[i/2]+1;
    for (ll i=0; i<n; ++i)
        st[i][0] = arr[i];
    for (ll j=1; j<=lg[n]; ++j) {
        for (ll i=0; i+(1LL<<j)<=n; ++i) {
            st[i][j] = min(st[i][j-1], st[i+(1LL<<(j-1))][j-1]);
        }
    }
}

ll query(ll l, ll r) {
    ll k = lg[r-l+1];
    return min(st[l][k], st[r-(1LL<<k)+1][k]);
}

Sqrt Decomposition / 平方分割

struct query {
    ll l, r, id;
};

ll arr[N], ans[Q];
vector<query> qs;

void solve(ll n) {
    ll bs = sqrt(n)+1;
    sort(qs.begin(), qs.end(), [&](query a, query b) {
        if (a.l/bs != b.l/bs)
            return a.l/bs < b.l/bs;
        if ((a.l/bs) & 1)
            return a.r > b.r;
        return a.r < b.r;
    });
    ll l=0, r=-1, cur=0;
    for (auto q : qs) {
        while (r < q.r) {
            r += 1;
            "extend r";
        }
        while (l > q.l) {
            l -= 1;
            "extend l";
        }
        while (r > q.r) {
            "remove r";
            r -= 1;
        }
        while (l < q.l) {
            "remove l";
            l += 1;
        }
        ans[q.id] = cur;
    }
}

String / 文字列

String Hashing / 文字列ハッシュ化

ll hashing(string& s) {
    ll p = 257;
    ll h = 0;
    for (char c : s)
        h = (h*p + c) % MOD;
    return h;
}

ll preh[N], ppow[N];

void build(string& s) {
    ll p = 257;
    ppow[0] = 1;
    for (ll i=0; i<(ll)s.size(); ++i) {
        preh[i+1] = (preh[i]*p + s[i]) % MOD;
        ppow[i+1] = (ppow[i] * p) % MOD;
    }
}

ll query(ll l, ll r) {
    ll res = preh[r+1] - preh[l]*ppow[r-l+1];
    res = (res % MOD + MOD) % MOD;
    return res;
}

KMP Algorithm / KMP法

ll pi[M];

void build(string& t) {
    pi[0] = 0;
    ll l = 0;
    for (ll i=1; i<t.size(); ++i) {
        while (l>0 && t[l]!=t[i])
            l = pi[l-1];
        if (t[l]==t[i])
            l += 1;
        pi[i] = l;
    }
}

void search(string& s, string& t) {
    ll j = 0;
    for (ll i=0; i<s.size(); ++i) {
        while (j>0 && s[i]!=t[j])
            j = pi[j-1];
        if (s[i]==t[j])
            j += 1;
        if (j==t.size()) {
            "match from i-j+1";
            j = pi[j-1];
        }
    }
}

Suffix Array / 接尾辞配列

vector<ll> sa;
vector<ll> lcp;

void build(string s) {
    s += '$';
    ll n=s.size(), cls=256;
    vector<ll> p(n), c(n), pn(n), cn(n), cnt(max(cls, n));
    for (ll i=0; i<n; ++i) {
        p[i] = i;
        c[i] = s[i];
    }
    for (ll h=1; h/2<n; h*=2) {
        for (ll i=0; i<n; ++i)
            p[i] = (p[i]+n-h/2)%n;
        fill(cnt.begin(), cnt.begin()+cls, 0);
        for (ll i=0; i<n; ++i)
            cnt[c[p[i]]] += 1;
        for (ll i=1; i<cls; ++i)
            cnt[i] += cnt[i-1];
        for (ll i=n-1; i>=0; --i)
            pn[--cnt[c[p[i]]]] = p[i];
        cn[pn[0]] = 0;
        cls = 1;
        for (ll i=1; i<n; ++i) {
            pair<ll,ll> cur = {c[pn[i]], c[(pn[i]+h/2)%n]};
            pair<ll,ll> pre = {c[pn[i-1]], c[(pn[i-1]+h/2)%n]};
            if (cur!=pre)
                cls += 1;
            cn[pn[i]] = cls-1;
        }
        p.swap(pn);
        c.swap(cn);
        if (cls==n)
            break;
    }
    for (ll i=1; i<n; ++i)
        sa.push_back(p[i]);
    n = sa.size();
    vector<ll> rk(n);
    for (ll i=0; i<n; ++i)
        rk[sa[i]] = i;
    lcp = vector<ll>(n-1);
    ll k = 0;
    for (ll i=0; i<n; ++i) {
        if (rk[i]==n-1) {
            k = 0;
            continue;
        }
        ll j = sa[rk[i]+1];
        while (i+k<n && j+k<n && s[i+k]==s[j+k])
            k += 1;
        lcp[rk[i]] = k;
        if (k>0)
            k -= 1;
    }
}

void search(string& s, string& t) {
    ll l1=-1, r1=sa.size();
    while (r1-l1>1) {
        ll m1 = (l1+r1)/2;
        if (s.compare(sa[m1], t.size(), t)>=0)
            r1 = m1;
        else
            l1 = m1;
    }
    ll l2 = -1, r2=sa.size();
    while (r2-l2>1) {
        ll m2 = (l2+r2)/2;
        if (s.compare(sa[m2], t.size(), t)>0)
            r2 = m2;
        else
            l2 = m2;
    }
    for (ll i=r1; i<r2; ++i)
        "match from sa[i]";
}

AC Automaton / ACオートマトン

ll nod=1, alp=26;
ll nxt[M][S], fil[M], lnk[M];
vector<ll> out[M];

void insert(string& t, ll id) {
    ll v = 0;
    for (char ch : t) {
        ll c = ch-'a';
        if (nxt[v][c]==0)
            nxt[v][c] = nod++;
        v = nxt[v][c];
    }
    out[v].push_back(id);
}

void build() {
    queue<ll> q;
    for (ll c=0; c<alp; ++c) {
        ll v = nxt[0][c];
        if (v!=0) {
            fil[v] = 0;
            lnk[v] = 0;
            q.push(v);
        }
    }
    while (!q.empty()) {
        ll v = q.front();
        q.pop();
        for (ll c=0; c<alp; ++c) {
            ll u = nxt[v][c];
            if (u!=0) {
                fil[u] = nxt[fil[v]][c];
                if (!out[fil[u]].empty())
                    lnk[u] = fil[u];
                else
                    lnk[u] = lnk[fil[u]];
                q.push(u);
            }
            else {
                nxt[v][c] = nxt[fil[v]][c];
            }
        }
    }
}

void search(string& s) {
    ll v = 0;
    for (ll i=0; i<(ll)s.size(); ++i) {
        ll c = s[i]-'a';
        v = nxt[v][c];
        for (ll id : out[v])
            "pattern id match ending at i";
        for (ll u=lnk[v]; u!=0; u=lnk[u]) {
            for (ll id : out[u])
                "pattern id match ending at i";
        }
    }
}

🍊 Game / ゲーム

Nim / Nim

vector<ll> arr(N);

bool nim(ll n) {
    ll x = 0;
    for (ll i=0; i<n; ++i)
        x ^= arr[i];
    return x > 0;
}

Grundy Number / Grundy数

vector<ll> gru(X);

void build(ll x) {
    for (ll i=1; i<=x; ++i) {
        set<ll> s;
        for ("<next state>") {
            s.insert(gru["<next state>"]);
        }
        ll g = 0;
        while (s.count(g)>0)
            g += 1;
        gru[i] = g;
    }
}