[[プロコン]]
*コンセプト [#z440aba9]
-構造化する。
-アルゴリズムを主体に置く
-概要をきちんとかく
-条件と入出力を大切にする
-図解と具体例
--アルゴリズムは図解が命！
-工学応用
--プロコンに限らず
*アルゴリズムスライド [#b576cd8c]
**はじめに [#l50a704b]
-アルゴリズム
-前処理とクエリ（構築と参照）
-計算量
-モノイド・群（モノイドはどこから計算してもいい＝並列、群は0-indexを計算できるとi-indexにできる（モノイドだとO(log n)で、群だとO(1)でできる））
**基本 [#ue254467]
-標準ライブラリについてるもの
--Vector
--Map（平衡二分木）
--Hash
--Priority Queue
--Queue(実はvector swapでできる)
--Stack
--List
--sort
--をまとめた表
-全探索
--n^kの全探索
--2^nの全探索
--n^mの全探索
--nCrの全探索
--n!の全探索
--グラフの全探索
-Union Find
-累積和（和でなくても）
-二次元累積和
-ダブリング＝行列累乗
-二分探索
-しゃくとり法
-三分探索
-状態遷移図
-分数
-多倍長演算
-座標圧縮
**数論 [#y86c91e7]
-GCD, LCM
-mod 素数の逆元
-フェルマーの小定理
-分数のmod
-素因数分解
--二番目が上から抑えられていると最後に余ったものは素数
-素数判定
--O(1)
--O(sqrt(n))
-素数の幅は意外と小さい
-素数の個数は意外と多い
-約数
-XOR
-Upper gauss記号とLower gauss記号
**再帰 [#aa61cfe2]
-配る再帰
-集める再帰
**DP [#l3a72254]
-配るDP
-集めるDP
-一方向のみに依存するDP
-一つ前のみに依存するDP
**ゲーム必勝法 [#tca28f96]
-アドホック
-Grundy数（二人完全情報ゼロ和不偏ゲーム）
-後ろから決めていく
**グラフ [#d5e9b881]
-用語定義(DAG, 頂点、辺)
-ワーシャルフロイド
-ダイクストラ
-経路復元
-無向グラフの閉路検出
-有向グラフの閉路検出とDAG化（強連結分解）
-最大フロー最小カット定理
-フォードフルカーソン
-Dinic
-二部マッチング
-最小費用流
**RMQ [#l64c020f]
-3つ合った気がする
**木 [#n4c8298b]
-オイラーツアー
-木の直径
-Tarjan's Offline LCA
-ダブリングによるLCA
-重軽分解
-Splay木
-Link-Cut Tree
**範囲クエリデータ構造 [#q05f3280]
-モノイド・群再び
-モノイド・群、具体例
-Fenwick Tree
-Segment Tree
-遅延Segment Tree
-動的Segment Tree
**高速フーリエ変換 [#d142d8a7]
-畳み込み演算
**高速ゼータ変換 [#c3777dca]
**高速メビウス変換 [#r171cb10]
**半分全列挙 [#h607242b]
**枝刈り全探索 [#i94890d4]
**文字列 [#j49a69f0]
-Suffix Array
-回文
**幾何 [#w65b4d4d]
-多角形の成立条件
**置換 [#x2cd123a]
-どこかでサイクルする
**細かいテクニック [#md53a97b]
-確率的判定
--多項式判定(mod)
--行列のやつ
-nの累乗空間
-ベン図（かぶる）
-包除原理
-Fibonacchi数列
-復元
-正しい括弧列
-- 「'(' の数が ')' の数を下回ることなく進んでいき, 最終的に '(' と ')' の数が等しくなる文字列」
--mayokoさんのセグ木二分探索解
**ソート [#c58be668]
-クイックソート
-バケツソート
-Priority queueで自分でソート（D1E スターウォーズのやつ）
**細かい注意 [#dbcb3ae1]
-intの*%/はマジ注意
-数字リテラルはキャストする
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
