toyon-competitive-programming-library

問題を解くときに使用したアルゴリズム、データ構造、考え方を出来るだけ分類していきます。

探索

• ビット全探索
• 順列全探索
• 二分探索
• 二分探索 (最大値の最小化)

データ構造

Union-Find

• Union-Find (rank)
• Union-Find (size)

Priority Queue

• Priority Queue

BIT

• BIT

平方分割

• 平方分割

セグツリー

• セグツリー

DP

累積和

• 一次元累積和
• 二次元累積和
• いもす法

DP パターン例

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

文字列

• ローリングハッシュ
• Z-algorithm

幾何

• 基本処理詰め合わせ

グラフ

DFS・BFS

• DFS (探索)
• DFS (連結成分の数を求める)
• DFS (2部グラフの頂点彩色)
• BFS (重みなしグラフの最短路)

フロー

• 最大流(Dinic) O(EV^2)
• 最小カット=最大流
• 二部マッチング=最大流 (※別解あり)
• 最小費用流

最短路

• 単一始点最短路 (Dijkstra) O(|E|log|V|) ※ 正辺のみ
• 全点対間最短路(Warshall-Floyd) O(V^3)

最小全域木

• 最小全域木(Kruskal)

数学

数論

• GCD, LCM
• 素数判定
• 約数列挙
• 素因数分解
• エラトステネスの篩
• modpow
• xor
• Nim

組合せ

• modint
• 組合せ

行列

• 行列累乗

その他

• ダブリング
• しゃくとり法
• 角度とラジアンの変換
• グリッド