経路圧縮 + 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: 根まで辿り親を直付け(経路圧縮)
class UnionFind:
def __init__(self, n):
self.par = list(range(n))
self.sz = [1] * n
def find(self, x):
while self.par[x] != x:
self.par[x] = self.par[self.par[x]] # 経路圧縮(半分)
x = self.par[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.sz[ra] < self.sz[rb]:
ra, rb = rb, ra
self.par[rb] = ra
self.sz[ra] += self.sz[rb]
return True
def same(self, a, b):
return self.find(a) == self.find(b)
def size(self, x):
return self.sz[self.find(x)]
点加算・前方和を 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)
class BIT:
def __init__(self, n):
self.n = n
self.t = [0] * (n + 1)
def add(self, i, v):
x = i + 1
while x <= self.n:
self.t[x] += v
x += x & -x
def sum(self, i): # a[0..i]
x, s = i + 1, 0
while x > 0:
s += self.t[x]
x -= x & -x
return s
def inversions(a):
bit = BIT((max(a) if a else 0) + 1)
res = 0
for x in reversed(a):
if x > 0:
res += bit.sum(x - 1)
bit.add(x, 1)
return res
優先度キューで未確定のうち最小距離の頂点を順に確定。負辺があると使えない(→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]
import heapq # g[v] = list of (to, cost) def dijkstra(g, s): dist = [float('inf')] * len(g); dist[s] = 0 pq = [(0, s)] # (dist, vertex) while pq: d, v = heapq.heappop(pq) if d > dist[v]: continue # 古い距離は捨てる for to, c in g[v]: if d + c < dist[to]: dist[to] = d + c heapq.heappush(pq, (dist[to], to)) return dist
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
from collections import deque
def grid_bfs(grid, sy, sx):
h, w = len(grid), len(grid[0])
dist = [[-1] * w for _ in range(h)]
dist[sy][sx] = 0
q = deque([(sy, sx)])
while q:
y, x = q.popleft()
for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
ny, nx = y + dy, x + dx
if not (0 <= ny < h and 0 <= nx < w):
continue
if grid[ny][nx] == '#' or dist[ny][nx] != -1:
continue
dist[ny][nx] = dist[y][x] + 1
q.append((ny, nx))
return dist
答えの単調性(F..FT..T)で二分。ok=満たす側, ng=満たさない側の初期値を渡す。
pred 単調: F F F T T T
ng ──┬── ok m=(ok+ng)/2
lowerBound: a[i] >= x の最小 i
upperBound: a[i] > x の最小 i
[1 3 3 5 7] x=3 → lower=1 upper=3 個数=2
# pred(ok)=True, pred(ng)=False となる初期値を渡す def bisect_meguru(ok, ng, pred): while abs(ok - ng) > 1: m = (ok + ng) // 2 if pred(m): ok = m else: ng = m return ok # 配列なら標準ライブラリが速い: from bisect import bisect_left, bisect_right # bisect_left(a, x) -> a[i] >= x の最小 i (lower_bound) # bisect_right(a, x) -> a[i] > x の最小 i (upper_bound)
累積和で区間和を 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
最後に累積和で復元
from itertools import accumulate def prefix_sum(a): # s[i]=a[0..i-1]; [l,r)=s[r]-s[l] return list(accumulate(a, initial=0)) class Imos: def __init__(self, n): self.diff = [0] * (n + 1) def add(self, l, r, v): # a[l..r-1] += v self.diff[l] += v self.diff[r] -= v def build(self): return list(accumulate(self.diff))[:-1]
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)
MOD = 998244353 # or 10**9 + 7 def modpow(a, e, m=MOD): return pow(a, e, m) # 組み込み pow が高速 def modinv(a, m=MOD): return pow(a, m - 2, m) # m は素数 class Comb: def __init__(self, max_n, m=MOD): self.m = m self.fact = [1] * (max_n + 1) for i in range(1, max_n + 1): self.fact[i] = self.fact[i - 1] * i % m self.inv = [1] * (max_n + 1) self.inv[max_n] = pow(self.fact[max_n], m - 2, m) for i in range(max_n, 0, -1): self.inv[i - 1] = self.inv[i] * i % m def nCr(self, n, r): if r < 0 or r > n: return 0 return self.fact[n] * self.inv[r] % self.m * self.inv[n - r] % self.m
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
def sieve(n): # is_prime[i]
p = [True] * (n + 1)
p[0] = p[1] = False
i = 2
while i * i <= n:
if p[i]:
for j in range(i * i, n + 1, i):
p[j] = False
i += 1
return p
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 も返す
from math import gcd # 標準で gcd / lcm(3.9+) def lcm(a, b): return a // gcd(a, b) * b def ext_gcd(a, b): # ax+by=gcd の (g, x, y) if b == 0: return a, 1, 0 g, x, y = ext_gcd(b, a % b) return g, y, x - (a // b) * y
容量ごとの最大価値。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)
def knapsack01(w, v, cap): # 各品物 1 個まで dp = [0] * (cap + 1) for wi, vi in zip(w, v): for j in range(cap, wi - 1, -1): # 重さ逆順 dp[j] = max(dp[j], dp[j - wi] + vi) return dp[cap] def subset_sum(a, target): # bitset で高速化 dp = 1 # s ビット目 = s を作れるか for x in a: dp |= dp << x return (dp >> target) & 1 == 1
非再帰・抽象化。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): 両端から畳む
class SegTree:
# op はモノイド(結合的 + 単位元 unit). 例: min, max, 和
def __init__(self, n, unit, op):
self.unit, self.op = unit, op
self.size = 1
while self.size < n:
self.size *= 2
self.t = [unit] * (2 * self.size)
def update(self, i, v):
x = i + self.size
self.t[x] = v
x >>= 1
while x:
self.t[x] = self.op(self.t[2 * x], self.t[2 * x + 1])
x >>= 1
def query(self, l, r): # [l, r)
res = self.unit
lo, hi = l + self.size, r + self.size
while lo < hi:
if lo & 1:
res = self.op(res, self.t[lo]); lo += 1
if hi & 1:
hi -= 1; res = self.op(res, self.t[hi])
lo >>= 1; hi >>= 1
return res
値の大小を保ったまま 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] が元の値
def compress(a):
# 値の大小を保ち 0..k-1 に圧縮。(圧縮後, 元の値) を返す
vals = sorted(set(a))
idx = {v: i for i, v in enumerate(vals)}
return [idx[x] for x in a], vals
全辺を n-1 回緩和。負辺 OK。n 回目でも更新できれば負閉路。Dijkstra が使えない時に。
全辺を n-1 回 緩和(relax) dist[t] = min(dist[t], dist[f] + cost) n 回目でも更新 → 負閉路あり 始点から到達する負閉路だけが検出対象
def bellman_ford(n, edges, s):
# edges: list of (from, to, cost). 負閉路があれば None
INF = float('inf')
dist = [INF] * n; dist[s] = 0
for _ in range(n - 1):
for f, t, c in edges:
if dist[f] != INF and dist[f] + c < dist[t]:
dist[t] = dist[f] + c
for f, t, c in edges: # n 回目で更新 → 負閉路
if dist[f] != INF and dist[f] + c < dist[t]:
return None
return dist
中継点 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 が最外)
def warshall_floyd(dist):
# dist: 隣接行列(辺なし=inf, 対角0) を in-place 更新
n = len(dist)
INF = float('inf')
for k in range(n):
for i in range(n):
if dist[i][k] == INF:
continue
dik = dist[i][k]
row = dist[i]
for j in range(n):
if dik + dist[k][j] < row[j]:
row[j] = dik + dist[k][j]
入次数 0 をキューから取り出し、辺を消しながら並べる。全頂点出せなければ閉路。
入次数0をキューへ → 取り出しつつ出る辺を消す (消した先の入次数が0になったら追加) 全頂点出れば順序確定 / 出きらねば閉路 辞書順最小が要るなら queue → 優先度付き
from collections import deque
def topo_sort(g):
# g: 隣接リスト(有向). 閉路があれば None
n = len(g)
indeg = [0] * n
for v in range(n):
for to in g[v]:
indeg[to] += 1
q = deque(v for v in range(n) if indeg[v] == 0)
order = []
while q:
v = q.popleft(); order.append(v)
for to in g[v]:
indeg[to] -= 1
if indeg[to] == 0:
q.append(to)
return order if len(order) == n else None
辺を cost 昇順に見て、端点が別グループなら採用(Union-Find)。全部つなぐ最小コスト。
辺を cost 昇順にソート 端点が別グループなら採用(UnionFind で併合) 採用辺が n-1 本で全域木 完成 ※ Union-Find のスニペットが必要
def kruskal(n, edges):
# edges: list of (cost, u, v). UnionFind 必要。非連結なら None
uf = UnionFind(n)
total = used = 0
for c, u, v in sorted(edges):
if uf.union(u, v):
total += c; used += 1
return total if used == n - 1 else None
窓 [left,right] を右に伸ばし、条件を破ったら左を詰める。単調性が前提(非負配列など)。
[left,right] 窓を右へ伸ばし、破ったら左を詰める 和<=k 最大長: 超えたら left++ で縮める 和>=k 個数: 初めて満たせば右端以降は全部OK 単調性(伸ばすと悪化/縮めると改善)が必要
def longest_at_most(a, k):
# 和が k 以下の連続区間の最大長 (a は非負)
best = s = left = 0
for right in range(len(a)):
s += a[right]
while s > k:
s -= a[left]; left += 1
best = max(best, right - left + 1)
return best
def count_at_least(a, k):
# 和が k 以上の連続区間の総数 (a は非負)
n = len(a)
count = s = right = 0
for left in range(n):
while right < n and s < k:
s += a[right]; right += 1
if s < k:
break
count += n - right + 1
s -= a[left]
return count
bit 全探索で選ぶ/選ばない 2ⁿ 通り(n≤20)。next permutation で全順列(n≤10)。
bit全探索: mask 0..2^n-1, i bit目で i 番目採用 for mask: for i: if (mask>>i & 1) use i 順列: 末尾から増加位置を探し交換→反転 012 021 102 120 201 210 (n! 通り)
# bit 全探索: for mask in range(1 << n): [i for i in range(n) if mask >> i & 1] # 順列は標準が簡単: from itertools import permutations # for p in permutations(range(n)): ... # n! 通り def next_permutation(a): # 辞書順で次の順列に in-place。なければ False i = len(a) - 2 while i >= 0 and a[i] >= a[i + 1]: i -= 1 if i < 0: return False j = len(a) - 1 while a[j] <= a[i]: j -= 1 a[i], a[j] = a[j], a[i] a[i + 1:] = a[i + 1:][::-1] return True
LIS は末尾最小値を二分探索で更新。LCS・編集距離は 2 次元 DP 表。
LIS: tail[k] = 長さ k+1 の増加列の末尾の最小値 各 x を lower_bound で 置換 or 追加 → 長さが答え LCS/編集距離: dp[i][j] を表で 一致なら \+1 / 不一致は周囲の最小から
from bisect import bisect_left
def lis(a):
# 最長増加部分列 O(N log N)。広義単調増加なら bisect_right に
tail = []
for x in a:
p = bisect_left(tail, x)
if p == len(tail):
tail.append(x)
else:
tail[p] = x
return len(tail)
def lcs(s, t): # 最長共通部分列 O(NM)
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(m):
dp[i + 1][j + 1] = dp[i][j] + 1 if s[i] == t[j] \
else max(dp[i][j + 1], dp[i + 1][j])
return dp[n][m]
def edit_distance(s, t): # 編集距離 O(NM)
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
c = 0 if s[i - 1] == t[j - 1] else 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]
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
def factorize(n): # {素因数: 指数} O(√N) res = {} v, p = n, 2 while p * p <= v: while v % p == 0: res[p] = res.get(p, 0) + 1 v //= p p += 1 if v > 1: res[v] = res.get(v, 0) + 1 return res def divisors(n): # 約数 (ソート済み) O(√N) small, large = [], [] d = 1 while d * d <= n: if n % d == 0: small.append(d) if d != n // d: large.append(n // d) d += 1 return small + large[::-1] def is_prime(n): if n < 2: return False d = 2 while d * d <= n: if n % d == 0: return False d += 1 return True
訪問済み集合を bit で持つ DP。N≤16 程度。全頂点を回って戻る最小コスト等。
dp[S][v] = 訪問済み集合 S で今 v にいる最小コスト
0 から出発: dp[{0}][0] = 0
S に未訪問 to を足して遷移
最後に全訪問+0へ戻る最小。N<=16 (2^16·16^2)
def tsp(dist):
# bitDP 巡回セールスマン O(2^N N^2). N<=16
INF = float('inf')
n = len(dist); full = 1 << n
dp = [[INF] * n for _ in range(full)]
dp[1][0] = 0
for s in range(full):
for v in range(n):
if dp[s][v] == INF:
continue
for to in range(n):
if s >> to & 1:
continue
ns = s | (1 << to)
cost = dp[s][v] + dist[v][to]
if cost < dp[ns][to]:
dp[ns][to] = cost
return min((dp[full - 1][v] + dist[v][0]
for v in range(1, n) if dp[full - 1][v] != INF), default=INF)
文字列を多項式ハッシュに。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 が安全
class RollingHash:
# mod 2^61-1。Python は多倍長なので素直に書ける
MOD = (1 << 61) - 1
BASE = 1_000_003
def __init__(self, s):
n = len(s)
self.h = [0] * (n + 1)
self.pw = [1] * (n + 1)
for i, ch in enumerate(s):
self.h[i + 1] = (self.h[i] * self.BASE + ord(ch)) % self.MOD
self.pw[i + 1] = self.pw[i] * self.BASE % self.MOD
def get(self, l, r): # [l, r)
return (self.h[r] - self.h[l] * self.pw[r - l]) % self.MOD
ccw(外積で回転方向)が基礎。線分交差・凸包・面積。誤差は EPS で比較、整数なら Long で。
ccw(a,b,c): 外積の符号で回転方向 1:反時計 -1:時計 0/±2:一直線上 線分交差: 互いに相手を挟む ⇔ 交差 凸包(Andrew): x昇順→下側→上側 cross<EPS で pop (左折だけ残す=反時計回り)
EPS = 1e-9
def sub(a, b): return (a[0] - b[0], a[1] - b[1])
def cross(a, b): return a[0] * b[1] - a[1] * b[0]
def dot(a, b): return a[0] * b[0] + a[1] * b[1]
def ccw(a, b, c):
# 1:反時計 -1:時計 2:c-a-b -2:a-b-c 0:線分ab上
ab, ac = sub(b, a), sub(c, a)
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
def seg_intersect(a, b, c, d):
return ccw(a, b, c) * ccw(a, b, d) <= 0 and ccw(c, d, a) * ccw(c, d, b) <= 0
def convex_hull(ps): # 反時計回り O(N log N)
s = sorted(set(ps))
if len(s) <= 2: return s
h = []
def build(floor, pts):
for p in pts:
while len(h) > floor and cross(sub(h[-1], h[-2]), sub(p, h[-1])) < EPS:
h.pop()
h.append(p)
build(1, s); lower = len(h); build(lower, s[::-1][1:])
return h[:-1]
def polygon_area(poly): # 符号付き面積(反時計回りで正)
n = len(poly)
return sum(cross(poly[i], poly[(i + 1) % n]) for i in range(n)) / 2
左頂点から増加路を DFS で探す。割り当て問題、最大マッチング = 最小頂点被覆(König)。
左→右の辺。各左頂点から増加路を DFS 右が空 or その相手を押し出せれば マッチ確定 最大マッチング数 = 最小頂点被覆 (König の定理) used[] を頂点ごとにリセットして探索
class BipartiteMatching:
# 増加路 DFS O(VE)。左 n, 右 m
def __init__(self, n, m):
self.n, self.m = n, m
self.g = [[] for _ in range(n)]
self.match_r = [-1] * m
def add_edge(self, u, v):
self.g[u].append(v)
def _dfs(self, u, used):
for v in self.g[u]:
if used[v]:
continue
used[v] = True
if self.match_r[v] == -1 or self._dfs(self.match_r[v], used):
self.match_r[v] = u
return True
return False
def solve(self):
res = 0
for u in range(self.n):
if self._dfs(u, [False] * self.m):
res += 1
return res
BFS でレベル分けし、レベル順に DFS で流す。最大流・最小カット・二部マッチングに。
BFS でレベル(最短距離)を付ける → レベルが増える辺だけ DFS で流す 逆辺(rev)に流量を戻し増加路を表現。繰り返す 最大流 = 最小カット。「同時不可の最小除去」に
from collections import deque
class Dinic:
# 最大流 O(V^2 E)。各辺 [to, cap, rev]
def __init__(self, n):
self.n = n
self.g = [[] for _ in range(n)]
def add_edge(self, fr, to, cap):
self.g[fr].append([to, cap, len(self.g[to])])
self.g[to].append([fr, 0, len(self.g[fr]) - 1])
def _bfs(self, s, t):
self.level = [-1] * self.n
self.level[s] = 0
q = deque([s])
while q:
v = q.popleft()
for to, cap, _ in self.g[v]:
if cap > 0 and self.level[to] < 0:
self.level[to] = self.level[v] + 1
q.append(to)
return self.level[t] >= 0
def _dfs(self, v, t, f):
if v == t:
return f
while self.it[v] < len(self.g[v]):
e = self.g[v][self.it[v]]
if e[1] > 0 and self.level[v] < self.level[e[0]]:
d = self._dfs(e[0], t, min(f, e[1]))
if d > 0:
e[1] -= d
self.g[e[0]][e[2]][1] += d
return d
self.it[v] += 1
return 0
def max_flow(self, s, t):
flow = 0
while self._bfs(s, t):
self.it = [0] * self.n
while True:
f = self._dfs(s, t, float('inf'))
if f == 0:
break
flow += f
return flow