libalgo

競技プログラミングでよく使われるアルゴリズムをてきとーに実装してみた．詳しくは About を見てください。

基本

• テンプレート
  code/template.cc
• STL コンテナの ostream 出力
  code/container-printer.cc, code/container-printer-test.cc
• ICPC 開始直後の準備
  code/emacs, code/bashrc, code/Makefile, code/template_icpc.cc

グラフ

• テンプレート
  code/graph/template.cc
• 単一始点最短路 (Dijkstra; Heap)
  code/graph/dijkstra.cc
• 単一始点最短路 (Dijkstra; Matrix)
  code/graph/dijkstra-matrix.cc
• 単一始点最短路 (Bellman Ford)
  code/graph/bellman-ford.cc
• 単一始点最短路 (SPFA)
  code/graph/spfa.cc
• 全点間対最短路 (Warshall Floyd)
  code/graph/warshall-floyd.cc
• 両側ダイクストラによる二点間最短路 (有向グラフ対応)
  code/graph/bidirectional-dijkstra.cc
• 最小全域木 (Prim)
  code/graph/prim.cc
• 最小全域木 (Kruskal)
  code/graph/kruskal.cc
• トポロジカルソート (Kahn)
  code/graph/tsort.cc
• トポロジカルソート
  code/graph/tsort-dfs.cc
• 強連結成分分解 (Kosaraju)
  code/graph/kosaraju.cc
• 強連結成分分解 (Tarjan)
  code/graph/tarjan-scc.cc
• 二点連結成分分解・関節点の列挙
  code/graph/articulation-point.cc
• 二辺連結成分分解・橋の列挙
  code/graph/bridge.cc
• 巡回セールスマン問題
  code/graph/tsp.cc
• 中国人郵便配達問題
  code/graph/cpp.cc
• 最大流 (Ford-Fulkerson)
  code/graph/ford-fulkerson.cc
• 最大流 (Edmonds-Kerp)
  code/graph/edmonds-kerp.cc
• 最大流 (Sparse Dinic)
  code/graph/dinic-sparse.cc
• 最大流 (Dinic)
  code/graph/dinic.cc
• 流量の下限制約付き最大流 [new]
  code/graph/flow_with_lower_bound.cc
• 2部グラフの最大マッチング
  code/graph/bipartite_matching.cc
• 最小費用流
  code/graph/primal-dual.cc
• 最短路木
  code/graph/shortest-path-tree.cc
• 有名かもしれない事実
  

木

• 木の直径
  code/graph/double-sweep.cc
• 根付き木の最小共通祖先 (ダブリング)
  code/graph/lca-doubling.cc
• 根付き木の最小共通祖先 (オイラーツアー)
  code/graph/lca-eulertour.cc
• 根付き木に変換
  code/graph/to_rooted.cc

整数・数え上げ

• 最小公倍数・最大公約数
  code/math/gcdlcm.cc
• 拡張ユークリッドの互除法
  code/math/extgcd.cc
• 2進GCD
  code/math/binary-gcd.cc
• 素数判定表・素数リスト
  code/math/eratosthenes.cc
• 素因数分解
  code/math/prime-factor-decomp.cc
• 冪乗の剰余
  code/math/modpow.cc
• 文字列で表現した整数の剰余
  code/math/modstr.cc
• 逆元
  code/math/modinv.cc
• 中国剰余定理
  code/math/crt.cc
• 離散対数問題
  code/math/babystep-giantstap.cc
• 確率的素数判定 [new]
  code/math/miller-rabin.cc
• MOD 取り構造体
  code/math/mint.cc
• n!, nPr, nCr, nHr 構造体
  code/math/comb.cc
• 組み合わせ係数 nCr DP
  code/math/comb-dp.cc
• 分割数
  code/math/partition-number.cc
• カタラン数
  
• モンモール数
  

数値

• 二分探索
  code/numeric/binary-search.cc
• 三分探索
  code/numeric/ternary-search.cc
• 二分法
  code/numeric/bisection.cc
• 二次方程式
  code/numeric/quadratic-equation.cc
• 三次方程式
  code/numeric/cubic-equation.cc
• 数値積分
  code/numeric/simpson.cc
• ラグランジュ補間
  code/numeric/lagrange_interpolation.cc
• ガウスの消去法
  code/numeric/gauss-jordan.cc

探索

• グリッド上の幅優先探索 [new]
  code/search/grid_bfs.cc

データ構造

• セグメントツリー (点変更・区間クエリ) [new]
  code/data-structure/segtree_monoids.cc
• セグメントツリー (区間 add, 区間 max)
  code/data-structure/segtree-add-max.cc
• セグメントツリー (区間 add, 区間 sum)
  code/data-structure/segtree-add-sum.cc
• 平方分割
  code/data-structure/sqrt-decomp.cc
• Sparce Table [new]
  code/data-structure/sparce_table.cc
• Binary Indexed Tree (Fenwick Tree)
  code/data-structure/fenwick_tree.cc
• 木の周遊路 (Euler Tour)
  code/data-structure/eular-tour.cc
• 平衡二分探索木 (Treap)
  code/data-structure/treap.cc
• 平衡二分探索木 (AVL Tree) [new]
  code/data-structure/avl_tree.cc
• 木の平方分割
  code/data-structure/sqrt-decomp-tree.cc
• 木の HL 分解
  code/data-structure/hld.cc
• 素集合データ構造
  code/data-structure/union-find.cc
• 両端ヒープ
  code/data-structure/double-ended-heap.cc

文字列

• 最長回文半径のテーブル
  code/string/manacher.cc
• 連続する部分文字列のハッシュ
  code/string/rolling-hash.cc

動的計画法

• 累積和で区間に一次関数を加算 [new]
  code/dp/cumulative_sum_linear.cc
• 2次元累積和
  code/dp/cumulative_sum_2d.cc
• 最長増加部分列
  code/dp/lis.cc
• レーベンシュタイン距離
  code/dp/levenshtein_distance.cc
• 最長共通部分列
  code/dp/lcs.cc

幾何

• テンプレート
  code/geometry/template.cc
• 交差判定・交点・距離・射影
  code/geometry/intersection.cc
• 円がかかわる交差判定・交点
  code/geometry/intersection-circle.cc
• 多角形の面積
  code/geometry/polygon-area.cc
• 凸包
  code/geometry/convex-hull.cc
• 凸多角形の切断
  code/geometry/convex-cut.cc
• 凸多角形の直径
  code/geometry/convex-diameter.cc
• 線分アレンジメント
  code/geometry/segment-arrangement.cc
• 最小包含円
  code/geometry/minball.cc
• 最近点対
  code/geometry/closest-pair.cc

その他

• クイックソート
  code/util/quicksort.cc
• マージソート
  code/util/mergesort.cc
• シェルソート
  code/util/shellsort.cc
• ヒープソート
  code/util/heapsort.cc
• 基数ソート [new]
  code/util/radixsort.cc
• Range-based for 用クラス (範囲と集合のイテレーション)
  code/util/range-obj.cc
• ヒストグラム中の面積最大長方形
  code/util/max-rect.cc
• スライド最小値
  code/util/slide-min.cc
• 日付関係
  code/util/date.cc
• ローマ数字とアラビア数字の変換
  code/util/roman-number.cc
• サイコロ
  code/util/dice.cc
• スタック拡張マクロ
  code/util/extend-stack.cc
• 乱数 (xor-shift)
  code/util/random.cc
• ビット数のカウント
  code/util/popcount.cc
• タイマー
  code/util/timer.cc

Rust

• テンプレート (IO・スレッド生成) [new]
  code/rust/template.rs
• Randomized binary search trees (RBST)
  code/rust/rbst.rs
• AVL tree [new]
  code/rust/avl_tree.rs
• Scapegoat tree [new]
  code/rust/scapegoat_tree.rs
• Union find tree
  code/rust/union_find.rs
• XorShift (Xor128)
  code/rust/xor128.rs
• Simple unsafe rand
  code/rust/rand.rs
• Chrono
  code/rust/chrono.rs