Need help with algorithm?
Click the “chat” button below for chat support from the developer who created it, or find similar developers for support.

About the developer

drken1215
168 Stars 9 Forks Creative Commons Zero v1.0 Universal 209 Commits 0 Opened issues

Description

Implementation of various algorithms

Services available

!
?

Need anything else?

Contributors list

No Data

様々なアルゴリズムの実装例

データ構造や数論的アルゴリズムまで、様々な分野のアルゴリズムたちを C++17 で実装しています。
アルゴリズム系の研究開発において計算機実験が必要になる場面や、 プログラミングコンテストに参加する場面などを想定して、 「実装例」または「ライブラリ」として使用することを念頭に置いています。

 

|分類|内容|具体例| |---|---|---| |MathNumberTheory|整数論的アルゴリズム|素因数分解、最大公約数など| |MathCombinatorics|組合せ論的アルゴリズム|modint、Nim など| |MathAlgebra|代数的アルゴリズム|行列計算など| |DataStructure|データ構造|Union-Find、セグメント木など| |DataStructureOnTree|木上のクエリに答えるためのデータ構造|Euler ツアー、HL 分解など| |GraphTheory|グラフアルゴリズム|強連結成分分解、木の直径など| |GraphNetworkFlow|ネットワークフローアルゴリズム|Ford-Fulkerson 法など| |DP|定型的な動的計画法やその他の処理|いもす法、LIS、CHT など| |Geometry|計算幾何|円の交点など| |String|文字列アルゴリズム|ローリングハッシュ、Suffix Array など| |Others|その他|xorshift、サイコロなど|

 

MathNumberTheory

整数論的アルゴリズムたちです

約数, 倍数

素数

エラトステネスの篩

方程式

有理数

その他

 

MathCombinatorics

組合せ論的アルゴリズムたちです

mod, 二項係数

様々な数

  • 重複組合せ
  • カタラン数
  • 分割数
  • スターリング数
  • ベル数
  • ベルヌーイ数

ソート

  • クイックソート
  • マージソート
  • ヒープソート
  • コムソート
  • Radix ソート
  • 挿入ソート
  • その他のソート達

マトロイド

  • マトロイド上の Greedy 法
  • マトロイド交差

その他

 

MathAlgebra

行列計算など代数的計算に関するアルゴリズムです

行列

多項式, 方程式

  • 二次方程式
  • 多項式 (実数係数)
  • 多項式 (mod. p 係数)
  • きたまさ法 (俗称)
  • きたまさ法 with FFT (俗称)
  • 多項式補間

畳み込み計算

形式的冪級数

最適化

  • 二分探索法 (方程式の解を 1 つ求める)
  • 三分探索法
  • 黄金探索法
  • Newton 法
  • 単体法
  • 分枝限定法

 

DataStructure

各種データ構造の実装です

Union-Find

セグメント木

Binary Indexed 木

RMQ

平方分割

平衡二分探索木

  • RBST
  • Treap 木
  • AVL 木
  • Splay 木
  • 赤黒木

永続データ構造

  • 永続配列
  • 完全永続 Union-Find 木
  • 永続セグメント木
  • 永続赤黒木

ハッシュ

  • Zobrist hash
  • 木に対する hash

ヒープ

  • Skew Heap (マージ可能)
  • Paring Heap (マージ可能)
  • Radix Heap
  • Fibonacci Heap

その他

 

DataStructureOnTree

ツリー上のクエリ処理のためのデータ構造たちの実装です

木全般

LCA

テクニック

その他の問題

  • Level Ancester

 

GraphTheory

グラフ理論全般のアルゴリズムです

DFS・BFS

  • DFS (連結成分を数える)
  • BFS (重みなしグラフの最短路)
  • トポロジカルソート (DFS)
  • トポロジカルソート (BFS)
  • サイクル検出 (DFS)
  • サイクル検出 (BFS)
  • サイクル検出 (Union-Find)
  • 二部グラフ判定 (DFS)
  • 二部グラフ判定 (BFS)
  • 二部グラフ判定 (Union-Find)

連結成分分解

ツリー

最短路

  • 重みなしグラフの最短路 (BFS)
  • 重みが 0, 1 のみのグラフの最短路 (0-1 BFS)
  • 単一始点最短路 (Dijkstra 法, 正辺のみ)
  • 単一始点最短路 (Bellman-Ford 法, 負辺対応)
  • 全頂点対間最短路 (Floyd-Warshall 法)
  • 全頂点対間最短路 (Johnson 法)
  • k-最短路
  • SPFA

その他

 

GraphNetworkFlow

グラフネットワークフロー関連のアルゴリズムです

最大流

最小費用流

カット

  • 最小カット (= 最大流)
  • 全域最小カット(Stoer-Wanger 法)
  • 全頂点対間最小カット (Nagamochi-Ibaraki 法)
  • Gomory-Hu 木

マッチング

 

DP

定型的な動的計画法やその他の処理です

典型処理

典型的 DP

  • 転倒数
  • LIS
  • LCS
  • 編集距離
  • 重みつき区間スケジューリング問題
  • ヒストグラム長方形面積最大化
  • 最適二分探索木
  • Set Cover
  • k-Cover (O(n 2^n))
  • k-partition (O(n^3 2^n))

DP パターン例

  • ナップサック DP
  • 区間分割型ナップサック DP
  • bitDP
  • 桁 DP
  • 部分列 DP
  • ダブリング DP
  • 木 DP
  • 全方位木 DP (俗称)
  • 二乗の木 DP (俗称)

DP 高速化テクニック

 

Geometry

幾何ライブラリです

点, 線分, 三角形などの位置関係

射影, 交差判定, 距離

直線や円の交点

多角形

接線

三次元幾何

その他

  • 最近点対
  • 最近円対
  • 線分併合
  • 線分アレンジメント
  • 3 点を通る円
  • アポロニウスの円
  • 最小包含円
  • 双対変換
  • kd 木

 

String

文字列アルゴリズムです

構文解析

  • LL(1) 再帰降下パーサ

文字列検索

文字列系アルゴリズム

文字列系データ構造

その他

 

Others

その他のアルゴリズムです

グリッド

ビット演算テクニック

探索法

  • α-β 探索
  • 焼き鈍し法
  • A*
  • IDA*
  • Baby-Step Giant-Step 法
  • 平面走査法

その他

 

License

These codes are licensed under CC0. CC0

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.