この記事では競技プログラミングを忘れてしまったときに、簡単に思い返せるよう、思いつく限りの競技プログラミングのテクニックをまとめていきます（追記予定）。書いている人は現在青色下位です。
全体に関するテクニック
DP(動的計画法)/メモ化再帰
全探索すると計算量が膨大になるときに、部分問題を解いていくことで解を求める方法。(減らせるパラメータを減らす)
pypy では再帰を使うべきでない。
再帰を使う場合は、
import sys
sys.setrecursionlimit(10**6)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
二分探索
O(N)を O(logN)にする方法。ソートされた配列に対して使う。
二分探索を二回使う問題も多いらしい
# ライブラリを使う場合
import bisect
# 配列Aに対して、A[i] >= xを満たす最小のiを求める
i = bisect.bisect_left(A, x)
# 配列Aに対して、A[i] > xを満たす最小のiを求める
i = bisect.bisect_right(A, x)
# めぐる式
def is_ok(a):
"""aはある値以上でTrueを返す関数"""
pass
def meguru_bisect(ng, ok):
"""is_okを満たし、[ok, ng)の範囲で最小の値を求める"""
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ok
累積和
配列の区間和を高速に求める方法
($\sum_{i=l}^{r}A_i = \sum_{i=0}^{r}A_i - \sum_{i=0}^{l-1}A_i$を使う)(逆元を持つ積でありさえすれば、可換である必要はない)
from itertools import accumulate
AAC = [0] + list(accumulate(A))
# 区間[l, r]の和
sum = AAC[r+1] - AAC[l]
ちなみに 2 次元のときは、
AAC = [[0]*(len(A[0])+1) for _ in range(len(A)+1)]
for i in range(len(A)):
for j in range(len(A[0])):
AAC[i+1][j+1] = AAC[i+1][j] + AAC[i][j+1] - AAC[i][j] + A[i][j]
# 区間[l1, r1] x [l2, r2]の和
sum = AAC[r1+1][r2+1] - AAC[l1][r2+1] - AAC[r1+1][l2] + AAC[l1][l2]
3 次元でも同様にできる
いもす法
区間に対して一様に値を加算する方法(lazy segment tree で代用可能)
はじめに、各区間に対して加算する値を記録し、その後、累積和を取る
尺取り法
区間を伸ばしたり縮めたりしながら解を求める方法
l,r = 0,0
for l in range(n):
while r < n and 条件を満たす:
r += 1
if 条件を満たす:
# 何か処理
else:
# 何か処理
l += 1
グラフに帰結
状態を n 個のパラメータで表し、n 次元空間において見たり、
変化可能な遷移を有向辺としてグラフに表す。
トポロジカルソートと併用することも
ダブリング
def doubling(f, depth):
n = len(f)
res = [[0]*n for _ in range(depth)]
for i in range(n):
res[0][i] = f[i]
for i in range(1, depth):
for j in range(n):
res[i][j] = res[i-1][res[i-1][j]]
return res
def get_Kth(k, v, doubled_f):
for i in range(len(doubled_f)):
if k & (1<<i):
v = doubled_f[i][v]
return v
有名問題の変形
全探索(ゴリ押しで解く)
bit 全探索、itertools.permutation 使用、再帰(バックトラック)、BFS、DFS、乱択アルゴリズム、
X[i]-i を使う
平均値を最大にする
→ 二分探索:平均値を決め打ちして、それを達成できるかを判定
→ 先に平均値を引くと、最大値を求める問題になる
pypy で TLE したときは、再帰を使っていないか、
重たいライブラリをインポートしていないか確認する
グラフ
トポロジカルソート
DAG(有向非巡回グラフ)に対して、頂点を一列に並べる方法。
出次数が 0 の頂点を取り出し、その頂点から出る辺を削除することを繰り返す。
最大流(フォードファルカーソン法)
二部グラフの最大マッチング
最大流問題に帰着する
[s→左側の頂点→右側の頂点→t]のグラフを考え、最大流を求める
最小全域木(プリム法/クラスカル法)
プリム法:
適当な頂点を集合Sに加え、SからS以外の頂点への最小コストの辺を選び、その先の頂点をSに加える
クラスカル法:
辺をコストの小さい順にソートし、閉路を作らないように辺を追加していく(Union-Find で閉路判定)
構築
上限を考えて、それを常に達成可能
平均を考えて、常にそれを下回らない
偶奇を考えて、常にそれを保つ
Nim/Grundy 数
木
木の重心
木の重心: その頂点を削除したとき、すべての部分木のサイズが最大でも半分になるような頂点
適当な頂点を根としたとき、その部分木のサイズをすべて求める。その後、各頂点について子を根とする部分木のサイズとN-自らの部分木のサイズが最大でも半分になるような頂点を求める(実装上では1度の DFS で求める)
木の直径
木の直径: 任意の 2 頂点間の最短距離
適当な頂点から最も遠い頂点を求め、その頂点から最も遠い頂点までの距離が木の直径
木 DP
全方位木 DP
木の直径の端点
データ構造
DSU/Union-Find
どの要素とどの要素が同じグループに属しているかを管理するデータ構造
超頂点を使ったり、頂点に状態をもたせて情報の矛盾を検出することもできる
Segment Tree
区間に対してクエリを高速に処理するデータ構造
Lazy Segment Tree
区間に対してクエリを高速に処理するデータ構造
整数に関するテクニック
累乗を高速に求める($a^b$)
pow(a, b, p)
$p$が素数のとき、(あるいは、$p$と$a$が互いに素のとき)
逆元を求める($a^{-1}$)
pow(a, -1, p)
素数判定
nに対して、2～n**0.5までの数で割り切れるかを調べる
素因数分解
def prime_factorize(n):
res = []
for i in range(2, int(n**0.5)+1):
while n % i == 0:
res.append(i)
n //= i
if n != 1:
res.append(n)
return res
$n$以下の素数を列挙
ユークリッドの篩を使う
def get_primes(n):
primes = []
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5)+1):
if is_prime[i]:
primes.append(i)
for j in range(i*2, n+1, i):
is_prime[j] = False
return primes
拡張ユークリッドの互除法
$ax+by=gcd(a, b)$を満たす整数$x, y$を求める
def extgcd(a, b):
if b == 0:
return 1, 0
s, t = extgcd(b, a%b)
return t, s - a//b*t
$n%m1=a1, n%m2=a2$を満たす$n$を求める
(ただし$m1$と$m2$が互いに素)
s1, s2 = extgcd(m1, m2)
n = (a1*s2*m2 + a2*s1*m1) % (m1*m2)
xorの性質
- $a \oplus a = 0$
- $a \oplus 0 = a$
- $a \oplus b = b \oplus a$
# 0からNまでのxor(O(1))
def xor(N):
if N % 4 == 3:
return 0
else:
return N ^ xor(N - 1)