編集距離
説明
文字列 $S$ と文字列 $T$ との編集距離の遷移の考え方は図の通り。
$ s_i = t_j $ のとき $ ed(S_i, T_j) = ed(S_{i-1}, T_{j-1})$
$ s_i \not= t ...
サイクル検出(DFS)
説明
DFSしながら訪問直後はその頂点を「処理中」としておき、DFSの途中で「処理中」ノードに到達したらサイクルがあったことになる。
WHITE = 0 # 未訪問GRAY = 1 # 処理中BLACK = 2 # 処理完了def ...トポロジカルソート(DFS)
説明
DFSしながら帰りがけ順に頂点を記録することでトポロジカルソートする
def dfs(u, graph, visited, order): visited = True for v in graph: if visited: ...多次元配列を多重ループを回してアクセスするときの注意事項（戒め）
説明
多次元配列を多重ループを回してアクセスするとき多次元配列の定義とループを回す順番を合わせないと遅くなる件。
何度もやらかしてそのたびに反省しているのだが、ついついうっかりしてしまうので戒めのために記事にしておく
トポロジカルソート(Kahnのアルゴリズム)
説明
Kahnのアルゴリズムでトポロジカルソートする
参考
順列の辞書順での前後を求める
説明
ある順列が与えられたとき、辞書順でその順列の前後を求める
def next_permutation(p): ''' 1. 末尾から降順になっている最長の部分列を探す⇒ p_last とする 2. p_lastの長さがlen( ...セグメント木
説明
セグメント木
class SegTree: def __init__(self, n, operator=max, identity=-INFTY): ''' 1-indexedのセグメント木用配列を用意 operator, ...高速な素因数分解 (osa_k法)
説明
準備に $O(A\log \log A)$ かかるが、素因数分解は $ O(\log A)$ で可能な方法
参考:
マンハッタン距離
説明
マンハッタン距離で $D$ 移動することは $ z = x + y $、$ w = x – y $ として $ z = \pm D $ または、$ w = \pm D $ 移動することに等しい
マンハッタン距離 ...
逆元の計算方法
説明
フェルマーの小定理を使った逆元の計算方法
xinv = pow(x, MOD-2, MOD)# 逆元を求めるには x と MOD は互いに素である必要がある。