競プロ早見表

C++ 25 topics · 印刷対応 (A4)
各項目は 使う場面 → 図解 → コード → 罠 の順。// 灰色はコメント、計算量は右上。
データ構造 Union-Find 素集合・連結判定 ほぼ O(α(N))

経路圧縮 + size 併合。連結判定 / グループ分け / Kruskal。union は併合したら true。

init   0  1  2  3  4   (各自が根)
u(0,1) 0──1  2  3  4
u(2,3) 0──1  2──3  4
u(1,2) 0──1──2──3  4   same(0,3)=T size=4
find: 根まで辿り親を直付け(経路圧縮)
struct UnionFind {
  vector<int> par, sz;
  UnionFind(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }
  int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
  bool unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;
    if (sz[ra] < sz[rb]) swap(ra, rb);
    par[rb] = ra; sz[ra] += sz[rb]; return true;
  }
  bool same(int a, int b) { return find(a) == find(b); }
  int size(int x) { return sz[find(x)]; }
};
  • size(小)を size(大)に繋ぐ(union by size)で木を低く保つ
  • 辺の削除はできない(追加のみ)。削除込みは別手法
データ構造 BIT (Fenwick) 点加算 + 区間和 / 転倒数 O(log N)

点加算・前方和を O(log N)。転倒数は「右より小さい既出要素の総数」で求まる。

idx は (i & -i) 幅を管理
add(i,v): x += x & -x で上る
sum(i):   x -= x & -x で下り a[0..i] の和
区間 [l,r] = sum(r) - sum(l-1)
転倒数: 後ろから add しつつ sum(a[i]-1)
struct BIT {
  int n; vector<ll> t;
  BIT(int n) : n(n), t(n + 1, 0) {}
  void add(int i, ll v) { for (int x = i + 1; x <= n; x += x & -x) t[x] += v; }
  ll sum(int i) {                     // a[0..i]
    ll s = 0;
    for (int x = i + 1; x > 0; x -= x & -x) s += t[x];
    return s;
  }
};
ll inversions(vector<int>& a) {
  int mx = 0; for (int x : a) mx = max(mx, x);
  BIT bit(mx + 1); ll res = 0;
  for (int i = (int)a.size() - 1; i >= 0; i--) {
    if (a[i] > 0) res += bit.sum(a[i] - 1);
    bit.add(a[i], 1);
  }
  return res;
}
  • 1-indexed で持つ(内部 x=i+1)。0 を add する値域に注意
  • 区間和は IntArray.sum() でなく Long で(溢れ)
グラフ Dijkstra 法 単一始点・非負重み最短路 O((V+E) log V)

優先度キューで未確定のうち最小距離の頂点を順に確定。負辺があると使えない(→Bellman-Ford)。

(0)──5──▶(1)   start = 0
 │        ▲    init  dist=[0, ∞, ∞]
 2        1    pop0  1=5 2=2 →[0,5,2]
 ▼        │    pop2  1=2+1=3 →[0,3,2]
(2)───────┘    pop1  settled
0▶1:5 0▶2:2 2▶1:1      ans [0,3,2]
// g[v] = vector of {to, cost}
vector<ll> dijkstra(vector<vector<pair<int, ll>>>& g, int s) {
  vector<ll> dist(g.size(), 4e18); dist[s] = 0;
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
  pq.push({0, s});
  while (!pq.empty()) {
    auto [d, v] = pq.top(); pq.pop();
    if (d > dist[v]) continue;          // 古い距離は捨てる
    for (auto [to, c] : g[v])
      if (d + c < dist[to]) { dist[to] = d + c; pq.push({dist[to], to}); }
  }
  return dist;
}
  • if (d > dist[v]) continue を必ず入れる(古い距離を捨てる、無いと TLE)
  • INF は加算で溢れない値に。C++ 4e18 / 他 LONG_MAX/4
  • 経路復元は prev[to]=v を更新し終点から逆順
グラフ グリッド BFS 迷路・最少手数 O(HW)

4 近傍を距離 +1 で push。壁 # と訪問済みは skip。最短手数 = 到達時の dist。

grid (#=壁)        dist from S
S . . #            0 1 2 #
. # . .            1 # 3 4
. . . G            2 3 4 5
4近傍↑↓←→を BFS → G = 5
vector<vector<int>> grid_bfs(vector<string>& grid, int sy, int sx) {
  int h = grid.size(), w = grid[0].size();
  vector<vector<int>> dist(h, vector<int>(w, -1));
  int dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1};
  dist[sy][sx] = 0;
  queue<pair<int, int>> q; q.push({sy, sx});
  while (!q.empty()) {
    auto [y, x] = q.front(); q.pop();
    for (int d = 0; d < 4; d++) {
      int ny = y + dy[d], nx = x + dx[d];
      if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
      if (grid[ny][nx] == '#' || dist[ny][nx] != -1) continue;
      dist[ny][nx] = dist[y][x] + 1;
      q.push({ny, nx});
    }
  }
  return dist;
}
  • 到達不可は -1 のまま
  • 8 近傍や重み付きは別 (重みは 0-1 BFS / Dijkstra)
ユーティリティ 累積和 / いもす法 区間和 O(1) / 区間加算 前計算 O(N), クエリ O(1)

累積和で区間和を O(1)。逆操作のいもす法は「区間加算を大量 → 最後に復元」。

a   = [1 2 3 4 5]
sum = [0 1 3 6 10 15]   (1個ずれ)
区間 [l,r) = sum[r] - sum[l]   [1,4)=9
いもす: add(l,r,v)= diff[l]+=v; diff[r]-=v
        最後に累積和で復元
vector<ll> prefix_sum(vector<ll>& a) {       // s[i]=a[0..i-1]; [l,r)=s[r]-s[l]
  vector<ll> s(a.size() + 1, 0);
  for (size_t i = 0; i < a.size(); i++) s[i + 1] = s[i] + a[i];
  return s;
}
struct Imos {
  vector<ll> diff;
  Imos(int n) : diff(n + 1, 0) {}
  void add(int l, int r, ll v) { diff[l] += v; diff[r] -= v; }   // a[l..r-1]+=v
  vector<ll> build() {
    vector<ll> res(diff.size() - 1); ll acc = 0;
    for (size_t i = 0; i < res.size(); i++) { acc += diff[i]; res[i] = acc; }
    return res;
  }
};
  • sum は長さ N+1。区間は半開 [l, r) で扱うと添字ミスが減る
  • いもす法は右端 r を「含まない」位置に -v
数学 mod 演算 / nCr modpow・modinv・組合せ O(log N) / 前計算 O(N)

modpow は繰返し二乗法。modinv はフェルマー(m素数で a^(m-2))。nCr は階乗逆元の前計算。

modpow(a,e): e を 2 進で繰返し二乗
  a^13 = a^8 · a^4 · a^1   (13 = 1101)
modinv(a) = a^(m-2) mod m   (m 素数)
nCr = fact[n]·inv[r]·inv[n-r]   前計算 O(n)
const ll MOD = 998244353;               // or 1000000007
ll modpow(ll a, ll e, ll m = MOD) {
  ll b = a % m, r = 1;
  while (e > 0) { if (e & 1) r = r * b % m; b = b * b % m; e >>= 1; }
  return r;
}
ll modinv(ll a, ll m = MOD) { return modpow(a, m - 2, m); }   // m は素数
struct Comb {
  ll m; vector<ll> fact, inv;
  Comb(int maxN, ll m = MOD) : m(m), fact(maxN + 1), inv(maxN + 1) {
    fact[0] = 1;
    for (int i = 1; i <= maxN; i++) fact[i] = fact[i - 1] * i % m;
    inv[maxN] = modpow(fact[maxN], m - 2, m);
    for (int i = maxN; i >= 1; i--) inv[i - 1] = inv[i] * i % m;
  }
  ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv[r] % m * inv[n - r] % m;
  }
};
  • MOD は問題指定 (998244353 か 1e9+7) を必ず確認
  • 掛け算ごとに % を取る(2 回掛けたら溢れる手前で)
  • Python は組み込み pow(a,e,m) が最速
数学 エラトステネスの篩 素数列挙 O(N log log N)

isPrime[i] を一括計算。i*i から消すのがポイント。約数/素因数のクエリが多いなら最小素因数表へ。

2 3 4 5 6 7 8 9 10 ...
2の倍数除外 → 3の → 5の → ...
消す開始は i*i (それ未満は既出)
残り = 素数  例) ~20: 2 3 5 7 11 13 17 19
vector<char> sieve(int n) {            // is_prime[i]
  vector<char> p(n + 1, 1); p[0] = p[1] = 0;
  for (int i = 2; (ll) i * i <= n; i++)
    if (p[i]) for (int j = i * i; j <= n; j += i) p[j] = 0;
  return p;
}
  • i*i がオーバーフローするなら long で比較
  • 0,1 は素数でない(初期化で false)
数学 gcd / lcm / extGcd ユークリッドの互除法 O(log N)

gcd は互除法。lcm は先に割って溢れ防止。extGcd は ax+by=gcd の (x,y) も求める(mod 逆元・不定方程式)。

gcd(a,b) = gcd(b, a%b),  gcd(a,0)=a
 gcd(12,18)=gcd(18,12)=gcd(12,6)=gcd(6,0)=6
lcm = a / gcd · b    (先に割る)
extGcd: ax + by = gcd の x,y も返す
ll gcdll(ll a, ll b) { return b == 0 ? a : gcdll(b, a % b); }   // C++17 は std::gcd
ll lcmll(ll a, ll b) { return a / gcdll(a, b) * b; }
// ax + by = gcd を返し、x,y を参照で受け取る
ll ext_gcd(ll a, ll b, ll& x, ll& y) {
  if (b == 0) { x = 1; y = 0; return a; }
  ll x1, y1, g = ext_gcd(b, a % b, x1, y1);
  x = y1; y = x1 - (a / b) * y1;
  return g;
}
  • lcm は a*b が溢れる → a/gcd*b の順
  • 負数の gcd 符号に注意(必要なら abs)
動的計画法 ナップサック / 部分和 0-1 / 個数制限 DP O(NW)

容量ごとの最大価値。0-1 は重さを逆順ループ(各品物1回)。部分和は価値の代わりに可否を持つ。

品物(w,v), 容量cap. dp[w]=容量wの最大価値
for 品物: for w = cap .. wi  (逆順!):
   dp[w] = max(dp[w], dp[w-wi] + vi)
逆順=各品物1回。正順だと無制限個
部分和: dp[s] = s を作れるか (bool)
// 0-1: 各品物 1 個まで
ll knapsack01(vector<int>& w, vector<ll>& v, int cap) {
  vector<ll> dp(cap + 1, 0);
  for (size_t i = 0; i < w.size(); i++)
    for (int j = cap; j >= w[i]; j--)       // 重さ逆順
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  return dp[cap];
}
bool subset_sum(vector<int>& a, int target) {
  vector<char> dp(target + 1, 0); dp[0] = 1;
  for (int x : a) for (int s = target; s >= x; s--) if (dp[s - x]) dp[s] = 1;
  return dp[target];
}
  • 0-1 は必ず容量を逆順。正順にすると無制限ナップサックになる
  • 価値は溢れうる → Long で持つ
データ構造 セグメント木 点更新 + 区間クエリ O(log N)

非再帰・抽象化。op はモノイド(結合的 + 単位元 unit)。min/max/和などを区間で。

[5 3 7 1 9] を min セグ木に
         [1]            ← 全体 min
      [3]    [9]
   [3][7] [9][∞]
 [5][3][7][1][9]
update(i,v): 葉→根  query[l,r): 両端から畳む
// op はモノイド(結合的 + 単位元 unit). 例: min/max/和
template <class T>
struct SegTree {
  int size = 1; T unit; function<T(T, T)> op; vector<T> t;
  SegTree(int n, T unit, function<T(T, T)> op) : unit(unit), op(op) {
    while (size < n) size *= 2;
    t.assign(2 * size, unit);
  }
  void update(int i, T v) {
    int x = i + size; t[x] = v;
    for (x >>= 1; x >= 1; x >>= 1) t[x] = op(t[2 * x], t[2 * x + 1]);
  }
  T query(int l, int r) {               // [l, r)
    T res = unit; int lo = l + size, hi = r + size;
    while (lo < hi) {
      if (lo & 1) res = op(res, t[lo++]);
      if (hi & 1) res = op(res, t[--hi]);
      lo >>= 1; hi >>= 1;
    }
    return res;
  }
};
  • query は半開 [l, r)
  • unit は演算の単位元 (min→∞, max→-∞, 和→0)
  • 区間更新が要るなら遅延セグ木に拡張
データ構造 座標圧縮 大きい値 → 0..k-1 O(N log N)

値の大小を保ったまま 0..k-1 に詰める。BIT/セグ木に乗せる前処理、値の種類数。

a    = [100  50 100   7]
sort & distinct = [7 50 100]  (→ 0 1 2)
comp = [  2   1   2   0]
逆引き: 圧縮値 i → vals[i] が元の値
// 値の大小を保ち 0..k-1 に圧縮。圧縮後を返し、vals に元の値
vector<int> compress(vector<ll>& a, vector<ll>& vals) {
  vals = a;
  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());
  vector<int> res(a.size());
  for (size_t i = 0; i < a.size(); i++)
    res[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
  return res;
}
  • 重複は 1 つにまとめる(distinct)
  • 半開区間や境界を扱うなら +1 した値も入れることがある
グラフ Bellman-Ford 法 負辺ありの最短路 O(VE)

全辺を n-1 回緩和。負辺 OK。n 回目でも更新できれば負閉路。Dijkstra が使えない時に。

全辺を n-1 回 緩和(relax)
 dist[t] = min(dist[t], dist[f] + cost)
n 回目でも更新 → 負閉路あり
始点から到達する負閉路だけが検出対象
struct BFEdge { int from, to; ll cost; };
// 負辺ありの最短路。負閉路なら ok=false
vector<ll> bellman_ford(int n, vector<BFEdge>& edges, int s, bool& ok) {
  const ll INF = 4e18;
  vector<ll> dist(n, INF); dist[s] = 0; ok = true;
  for (int i = 0; i < n - 1; i++)
    for (auto& e : edges)
      if (dist[e.from] != INF && dist[e.from] + e.cost < dist[e.to])
        dist[e.to] = dist[e.from] + e.cost;
  for (auto& e : edges)                     // 負閉路
    if (dist[e.from] != INF && dist[e.from] + e.cost < dist[e.to]) ok = false;
  return dist;
}
  • dist[f] が INF の辺は緩和しない(INF + cost で誤更新)
  • 負閉路検出は n-1 回緩和の「後」にもう 1 周
グラフ Warshall-Floyd 法 全点対最短路 O(V³)

中継点 k を全部試す DP。V≤500 まで。負辺 OK(負閉路は dist[v][v]<0 で検出)。

中継点 k = 0..n-1 を全部試す
 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
隣接行列(辺なし=INF, 対角0)を渡し in-place 更新
ループ順は k, i, j の順 (k が最外)
// 全点対最短路。dist は隣接行列(辺なし=INF, 対角0) を in-place 更新
void warshall_floyd(vector<vector<ll>>& dist) {
  const ll INF = 4e18; int n = dist.size();
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++) {
      if (dist[i][k] == INF) continue;
      for (int j = 0; j < n; j++)
        if (dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])
          dist[i][j] = dist[i][k] + dist[k][j];
    }
}
  • ループ順は必ず k を最外に
  • INF 経由の誤更新を防ぐ(INF の行は skip)
グラフ トポロジカルソート DAG の順序付け (Kahn) O(V+E)

入次数 0 をキューから取り出し、辺を消しながら並べる。全頂点出せなければ閉路。

入次数0をキューへ → 取り出しつつ出る辺を消す
 (消した先の入次数が0になったら追加)
全頂点出れば順序確定 / 出きらねば閉路
辞書順最小が要るなら queue → 優先度付き
// Kahn 法。g: 隣接リスト(有向). 閉路なら ok=false
vector<int> topo_sort(vector<vector<int>>& g, bool& ok) {
  int n = g.size(); vector<int> indeg(n, 0);
  for (int v = 0; v < n; v++) for (int to : g[v]) indeg[to]++;
  queue<int> q;
  for (int v = 0; v < n; v++) if (indeg[v] == 0) q.push(v);
  vector<int> order;
  while (!q.empty()) {
    int v = q.front(); q.pop(); order.push_back(v);
    for (int to : g[v]) if (--indeg[to] == 0) q.push(to);
  }
  ok = ((int) order.size() == n);
  return order;
}
  • 出力数 < N なら閉路あり
  • 辞書順最小は ArrayDeque を PriorityQueue に
グラフ Kruskal 法 (MST) 最小全域木 O(E log E)

辺を cost 昇順に見て、端点が別グループなら採用(Union-Find)。全部つなぐ最小コスト。

辺を cost 昇順にソート
 端点が別グループなら採用(UnionFind で併合)
 採用辺が n-1 本で全域木 完成
※ Union-Find のスニペットが必要
struct WEdge { ll cost; int u, v; };
// 最小全域木。UnionFind 必要。非連結なら -1
ll kruskal(int n, vector<WEdge> edges) {
  sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a.cost < b.cost; });
  UnionFind uf(n); ll total = 0; int used = 0;
  for (auto& e : edges)
    if (uf.unite(e.u, e.v)) { total += e.cost; used++; }
  return used == n - 1 ? total : -1;
}
  • 採用辺が n-1 本に満たなければ非連結
  • 同コスト辺の順序は MST 重みに影響しない
ユーティリティ しゃくとり法 連続区間の最長/数え上げ O(N)

窓 [left,right] を右に伸ばし、条件を破ったら左を詰める。単調性が前提(非負配列など)。

[left,right] 窓を右へ伸ばし、破ったら左を詰める
 和<=k 最大長: 超えたら left++ で縮める
 和>=k 個数: 初めて満たせば右端以降は全部OK
単調性(伸ばすと悪化/縮めると改善)が必要
// 和が k 以下の連続区間の最大長 (a は非負)
int longest_at_most(vector<ll>& a, ll k) {
  int best = 0, left = 0; ll sum = 0;
  for (int right = 0; right < (int) a.size(); right++) {
    sum += a[right];
    while (sum > k) { sum -= a[left]; left++; }
    best = max(best, right - left + 1);
  }
  return best;
}
// 和が k 以上の連続区間の総数 (a は非負)
ll count_at_least(vector<ll>& a, ll k) {
  int n = a.size(), right = 0; ll count = 0, sum = 0;
  for (int left = 0; left < n; left++) {
    while (right < n && sum < k) { sum += a[right]; right++; }
    if (sum < k) break;
    count += n - right + 1;
    sum -= a[left];
  }
  return count;
}
  • 負数があると単調性が崩れ使えない
  • right を左に戻さない(各ポインタは単調に進むだけ)
動的計画法 LIS / LCS / 編集距離 部分列 DP O(N log N) / O(NM)

LIS は末尾最小値を二分探索で更新。LCS・編集距離は 2 次元 DP 表。

LIS: tail[k] = 長さ k+1 の増加列の末尾の最小値
 各 x を lower_bound で 置換 or 追加 → 長さが答え
LCS/編集距離: dp[i][j] を表で
 一致なら \+1 / 不一致は周囲の最小から
// LIS (最長増加部分列) O(N log N)
int lis(vector<int>& a) {
  vector<int> tail;
  for (int x : a) {
    auto it = lower_bound(tail.begin(), tail.end(), x);
    if (it == tail.end()) tail.push_back(x); else *it = x;
  }
  return tail.size();
}
// LCS (最長共通部分列) O(NM)
int lcs(const string& s, const string& t) {
  int n = s.size(), m = t.size();
  vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
  for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
    dp[i + 1][j + 1] = (s[i] == t[j]) ? dp[i][j] + 1
                       : max(dp[i][j + 1], dp[i + 1][j]);
  return dp[n][m];
}
// 編集距離 (Levenshtein) O(NM)
int edit_distance(const string& s, const string& t) {
  int n = s.size(), m = t.size();
  vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
  for (int i = 0; i <= n; i++) dp[i][0] = i;
  for (int j = 0; j <= m; j++) dp[0][j] = j;
  for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
    int c = (s[i - 1] == t[j - 1]) ? 0 : 1;
    dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + c});
  }
  return dp[n][m];
}
  • LIS 広義単調増加は lower→upper bound に変える
  • LCS/編集距離は O(NM) メモリ。長いと 1 次元ロールで節約
数学 素因数分解 / 約数 √N の整数論 O(√N)

p=2 から割り続ける素因数分解。約数は d と n/d をペアで集める。素数判定も同様。

factorize: p=2.. (p*p<=v) の間割り続ける
 残った v>1 は最大の素因数
 360 = 2^3 · 3^2 · 5
divisors: d*d<=n, n%d==0 で d と n/d を集める
 12 の約数 = 1 2 3 4 6 12
// 素因数分解 {素因数: 指数} O(√N)
map<ll, int> factorize(ll n) {
  map<ll, int> res; ll v = n;
  for (ll p = 2; p * p <= v; p++)
    while (v % p == 0) { res[p]++; v /= p; }
  if (v > 1) res[v]++;
  return res;
}
// 約数列挙 (ソート済み) O(√N)
vector<ll> divisors(ll n) {
  vector<ll> small, large;
  for (ll d = 1; d * d <= n; d++)
    if (n % d == 0) { small.push_back(d); if (d != n / d) large.push_back(n / d); }
  for (int i = (int) large.size() - 1; i >= 0; i--) small.push_back(large[i]);
  return small;
}
bool is_prime(ll n) {
  if (n < 2) return false;
  for (ll d = 2; d * d <= n; d++) if (n % d == 0) return false;
  return true;
}
  • p*p<=v / d*d<=n で √N 打ち切り(オーバーフローは long)
  • クエリが多いなら篩で最小素因数表(spf)を作り O(log N) に
動的計画法 bitDP (TSP) 巡回セールスマン O(2ᴺN²)

訪問済み集合を bit で持つ DP。N≤16 程度。全頂点を回って戻る最小コスト等。

dp[S][v] = 訪問済み集合 S で今 v にいる最小コスト
 0 から出発: dp[{0}][0] = 0
 S に未訪問 to を足して遷移
最後に全訪問+0へ戻る最小。N<=16 (2^16·16^2)
// bitDP 巡回セールスマン O(2^N N^2). N<=16
ll tsp(vector<vector<ll>>& dist) {
  const ll INF = 4e18; int n = dist.size(), full = 1 << n;
  vector<vector<ll>> dp(full, vector<ll>(n, INF));
  dp[1][0] = 0;
  for (int s = 0; s < full; s++) for (int v = 0; v < n; v++) {
    if (dp[s][v] == INF) continue;
    for (int to = 0; to < n; to++) {
      if (s >> to & 1) continue;
      int ns = s | (1 << to);
      if (dp[s][v] + dist[v][to] < dp[ns][to]) dp[ns][to] = dp[s][v] + dist[v][to];
    }
  }
  ll res = INF;
  for (int v = 1; v < n; v++)
    if (dp[full - 1][v] != INF) res = min(res, dp[full - 1][v] + dist[v][0]);
  return res;
}
  • 1 shl N の集合サイズ。N>20 で破綻
  • 到達不能 (INF) からは遷移しない
文字列 ローリングハッシュ 部分文字列比較 O(1) 構築 O(N) / 比較 O(1)

文字列を多項式ハッシュに。mod 2⁶¹-1 で衝突回避。部分文字列の一致判定が O(1)。

h[i] = s[0..i-1] の多項式ハッシュ (base 進数)
 get(l,r) = h[r] - h[l]·base^(r-l)  (mod 2^61-1)
部分文字列が等しい ⇔ ハッシュ一致 (O(1))
base はランダム、mod は 2^61-1 が安全
// ローリングハッシュ (mod 2^61-1)。部分文字列比較 O(1)
struct RollingHash {
  static const ll MOD = (1LL << 61) - 1;
  static const ll BASE = 1000003;
  vector<ll> h, pw;
  RollingHash(const string& s) {
    int n = s.size();
    h.assign(n + 1, 0); pw.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
      h[i + 1] = mul(h[i], BASE) + s[i];
      if (h[i + 1] >= MOD) h[i + 1] -= MOD;
      pw[i + 1] = mul(pw[i], BASE);
    }
  }
  static ll mul(ll a, ll b) {                     // a*b mod (2^61-1)
    __int128 t = (__int128) a * b;
    ll r = (ll)((t >> 61) + (t & MOD));
    if (r >= MOD) r -= MOD;
    return r;
  }
  ll get(int l, int r) {                          // [l, r)
    ll res = h[r] - mul(h[l], pw[r - l]);
    if (res < 0) res += MOD;
    return res;
  }
};
  • 単一ハッシュは衝突リスク。心配なら 2 種の mod で二重化
  • C++ は __int128、Java/Kotlin は Math.multiplyHigh で 128bit 乗算
幾何 平面幾何 ccw / 線分交差 / 凸包 凸包 O(N log N)

ccw(外積で回転方向)が基礎。線分交差・凸包・面積。誤差は EPS で比較、整数なら Long で。

ccw(a,b,c): 外積の符号で回転方向
  1:反時計 -1:時計 0/±2:一直線上
線分交差: 互いに相手を挟む ⇔ 交差
凸包(Andrew): x昇順→下側→上側
 cross<EPS で pop (左折だけ残す=反時計回り)
const double EPS = 1e-9;
struct Pt { double x, y; };
Pt sub(Pt a, Pt b) { return {a.x - b.x, a.y - b.y}; }
double cross(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }
double dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y; }
// 1:反時計 -1:時計 2:c-a-b -2:a-b-c 0:線分ab上
int ccw(Pt a, Pt b, Pt c) {
  Pt ab = sub(b, a), ac = sub(c, a);
  double cr = cross(ab, ac);
  if (cr > EPS) return 1;
  if (cr < -EPS) return -1;
  if (dot(ab, ac) < -EPS) return 2;
  if (dot(ab, ab) < dot(ac, ac) - EPS) return -2;
  return 0;
}
bool seg_intersect(Pt a, Pt b, Pt c, Pt d) {
  return ccw(a,b,c)*ccw(a,b,d) <= 0 && ccw(c,d,a)*ccw(c,d,b) <= 0;
}
// 凸包(反時計回り) O(N log N)
vector<Pt> convex_hull(vector<Pt> ps) {
  sort(ps.begin(), ps.end(), [](Pt a, Pt b){ return a.x != b.x ? a.x < b.x : a.y < b.y; });
  int n = ps.size();
  if (n <= 2) return ps;
  vector<Pt> h(2 * n); int k = 0;
  for (int i = 0; i < n; i++) {
    while (k >= 2 && cross(sub(h[k-1], h[k-2]), sub(ps[i], h[k-1])) < EPS) k--;
    h[k++] = ps[i];
  }
  for (int i = n - 2, lower = k + 1; i >= 0; i--) {
    while (k >= lower && cross(sub(h[k-1], h[k-2]), sub(ps[i], h[k-1])) < EPS) k--;
    h[k++] = ps[i];
  }
  h.resize(k - 1);
  return h;
}
double polygon_area(vector<Pt>& poly) {            // 反時計回りで正
  double s = 0; int n = poly.size();
  for (int i = 0; i < n; i++) s += cross(poly[i], poly[(i + 1) % n]);
  return s / 2;
}
  • == でなく EPS 比較。退化(同一点・一直線)に注意
  • 整数座標なら Long の cross で誤差ゼロにできる
  • 凸包は一直線上の点を残すなら pop 条件を < -EPS に
グラフ 二部マッチング 増加路 (Hopcroft不要版) O(VE)

左頂点から増加路を DFS で探す。割り当て問題、最大マッチング = 最小頂点被覆(König)。

左→右の辺。各左頂点から増加路を DFS
 右が空 or その相手を押し出せれば マッチ確定
最大マッチング数 = 最小頂点被覆 (König の定理)
used[] を頂点ごとにリセットして探索
// 増加路 DFS O(VE)。左 n, 右 m
struct BipartiteMatching {
  int n, m; vector<vector<int>> g; vector<int> matchR;
  BipartiteMatching(int n, int m) : n(n), m(m), g(n), matchR(m, -1) {}
  void add_edge(int u, int v) { g[u].push_back(v); }
  bool dfs(int u, vector<char>& used) {
    for (int v : g[u]) {
      if (used[v]) continue;
      used[v] = 1;
      if (matchR[v] == -1 || dfs(matchR[v], used)) { matchR[v] = u; return true; }
    }
    return false;
  }
  int solve() {
    int res = 0;
    for (int u = 0; u < n; u++) { vector<char> used(m, 0); if (dfs(u, used)) res++; }
    return res;
  }
};
  • used は左頂点ごとに毎回リセット
  • もっと速くしたいなら Hopcroft-Karp / Dinic
グラフ Dinic 法 (最大流) 最大流 = 最小カット O(V²E)

BFS でレベル分けし、レベル順に DFS で流す。最大流・最小カット・二部マッチングに。

BFS でレベル(最短距離)を付ける
 → レベルが増える辺だけ DFS で流す
 逆辺(rev)に流量を戻し増加路を表現。繰り返す
最大流 = 最小カット。「同時不可の最小除去」に
// Dinic 最大流 O(V^2 E)。最大流=最小カット
struct Dinic {
  struct E { int to; ll cap; int rev; };
  int n; vector<vector<E>> g; vector<int> level, iter;
  Dinic(int n) : n(n), g(n), level(n), iter(n) {}
  void add_edge(int from, int to, ll cap) {
    g[from].push_back({to, cap, (int) g[to].size()});
    g[to].push_back({from, 0, (int) g[from].size() - 1});
  }
  void bfs(int s) {
    fill(level.begin(), level.end(), -1); level[s] = 0;
    queue<int> q; q.push(s);
    while (!q.empty()) {
      int v = q.front(); q.pop();
      for (auto& e : g[v]) if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); }
    }
  }
  ll dfs(int v, int t, ll f) {
    if (v == t) return f;
    for (; iter[v] < (int) g[v].size(); iter[v]++) {
      E& e = g[v][iter[v]];
      if (e.cap > 0 && level[v] < level[e.to]) {
        ll d = dfs(e.to, t, min(f, e.cap));
        if (d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; }
      }
    }
    return 0;
  }
  ll max_flow(int s, int t) {
    ll flow = 0;
    while (true) {
      bfs(s);
      if (level[t] < 0) return flow;
      fill(iter.begin(), iter.end(), 0);
      ll f;
      while ((f = dfs(s, t, (ll) 4e18)) > 0) flow += f;
    }
  }
};
  • 容量は溢れない型(Long)。INF も大きすぎない値
  • iter[] で見た辺を再訪しない(これが効率の肝)