Python3で実装しています。
インタラクティブ
二分探索
分数の端数処理
最大公約数 ((拡張)ユークリッドの互除法)
階乗
モジュラ逆数
中国余剰定理
原始根
離散対数問題 (Baby-step giant-step)
素数mod上の平方根 (Tonelli-Shanks algorithm)
Stern-Brocot tree
ベルヌーイ数
素因数分解 (試し割り法)
素因数分解 (Pollard’s rho algorithm)
素数を求める篩(ふるい)法
確率的素数判定
オイラーのφ関数
カーマイケル関数
メビウス関数
写像12相
カタランの三角形
ナップサック問題 (重みが小さいケース)
ナップサック問題 (価値が小さいケース)
0-1ナップサック問題 (半分全列挙)
最長部分増加列
最長共通部分列
点の線対称
多角形の面積
多角形の点包含判定
線分同士の交差判定
線分と頂点の最短距離
直線同士の交点
直線(線分)と円の交点
円同士の交点
2つの円の共通部分の面積
円の共通接線の接点/接線
三角形の外接円/内接円/傍接円
凸包 (Graham Scan)
凸多角形の点包含判定
凸多角形同士の交差判定/交点
直線による凸多角形の切断
凸多角形と直線の交差判定/交点
点から凸多角形への接線
最遠点対 (キャリパー法)
最近点対 (分割統治法)
座標圧縮
ビット集合演算
素集合データ構造 (Union-Find)
部分永続Union-Find
Treap
Randomized Binary Search Tree (RBST)
永続RBST
赤黒木
Splay tree
Scapegoat tree
Binary Indexed Tree
Range Minimum Query (セグメント木)
Range Update Query (セグメント木)
RSQ and RAQ (BIT)
RMQ and RUQ (遅延評価セグメント木)
RMQ and RAQ (遅延評価セグメント木)
RSQ and RUQ (遅延評価セグメント木)
Merge Sort Tree
Link-Cut Tree
Sliding Window Minimum
Convex Hull Trick (Li-Chao (Segment) Tree)
Convex Hull Trick (Deque)
Convex Hull Trick (平衡二分探索木)
深さ優先探索
全点対最短経路 (ワーシャルフロイド法)
全点対最短経路 (Johnson’s Algorithm)
単一始点最短経路 (BFS)
単一始点最短経路 (BFS, 格子グラフ)
単一始点最短経路 (0-1-BFS)
単一始点最短経路 (ベルマンフォード法)
単一始点最短経路 (ダイクストラ法, 二分ヒープ)
単一始点最短経路 (ダイクストラ法, Radix Heap)
単一始点最短経路 (Dial’s Algorithm)
単一始点最短経路 (D’Esopo-Pape Algorithm)
単一始点最短経路 (SPFA)
牛ゲー
木の直径 (double sweep method)
トポロジカルソート (Kahn’s Algorithm)
強連結成分分解 (Kosaraju’s Algorithm)
2-SAT
橋検出 (Path-based DFS)
関節点検出 (LowLink)
橋検出と関節点検出 (chain decomposition)
Dominator (Lengauer-Tarjan Algorithm)
Dominator (SEMI-NCA Algorithm)
最小全域木 (クラスカル法)
最小全域木 (プリム法)
最小全域木の二分木変換
最小全域有向木 (Chu-Liu/Edmonds' Algorithm)
最小シュタイナー木 (Dreyfus-Wagner Algorithm)
最小共通祖先 (ダブリング)
最小共通祖先 (セグメント木)
最小共通祖先 (Sparse Table)
最小共通祖先 (Disjoint Sparse Table)
最小共通祖先 (平方分割)
最小共通祖先 (Heavy-Light Decomposition)
最小共通祖先 (オフライン)
Auxiliary Tree (LCAベース)
オイラー路構築 (Hierholzer’s Algorithm)
最大クリーク問題 (Bron-Kerbosch Algorithm)
全域最小カット (Stoer-Wagner Algorithm)
最大マッチング (Edmonds' Algorithm)
dsu on tree
最大フロー (Ford-Fulkerson Algorithm)
最大フロー (Dinic’s Algorithm)
最大フロー (Push-Relabel Algorithm, FIFO selection)
最大フロー (Push-Relabel Algorithm, highest selection)
最大二部マッチング (Hopcroft-Karp Algorithm)
最小費用流問題 (Primal Dual Algorithm)
行列乗算 (naive)
連立一次方程式 (掃き出し法)
反転数
ビット行列 (Bit-Parallel Algorithm)
フィボナッチ数列
きたまさ法
Fast Fourier Transform
Fast Modulo Transform
ラグランジュ補完
KMP法
Rolling Hash
Suffix Array (Manber and Myers Algorithm)
Suffix Array (Rolling Hash)
Suffix Array (SA-IS)
Aho-Corasick Algorithm
最長回文 (Manacher’s algorithm)
Z algorithm
サイコロ
日付変換
構文解析
コードゴルフテクニックメモ (gist)
戻る