プロコン/スライド のバックアップ(No.2)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• プロコン/スライド へ行く。
  • 1 (2016-06-01 (水) 10:27:17)
  • 2 (2016-06-01 (水) 10:37:04)
  • 3 (2016-06-11 (土) 04:50:19)

FrontPage

アルゴリズムスライド †

はじめに †

• アルゴリズム
• 前処理とクエリ（構築と参照）
• 計算量
• モノイド・群（モノイドはどこから計算してもいい＝並列、群は0-indexを計算できるとi-indexにできる（モノイドだとO(log n)で、群だとO(1)でできる））

基本 †

• 標準ライブラリについてるもの
  • Vector
  • Map（平衡二分木）
  • Hash
  • Priority Queue
  • Queue(実はvector swapでできる)
  • Stack
  • List
  • sort
  • をまとめた表
• 全探索
  • n^kの全探索
  • 2^nの全探索
  • n^mの全探索
  • nCrの全探索
  • n!の全探索
  • グラフの全探索
• Union Find
• 累積和（和でなくても）
• 二次元累積和
• ダブリング＝行列累乗
• 二分探索
• しゃくとり法
• 三分探索
• 状態遷移図
• 分数
• 多倍長演算
• 座標圧縮

数論 †

• GCD, LCM
• mod 素数の逆元
• フェルマーの小定理
• 分数のmod
• 素因数分解
  • 二番目が上から抑えられていると最後に余ったものは素数
• 素数判定
  • O(1)
  • O(sqrt(n))
• 素数の幅は意外と小さい
• 素数の個数は意外と多い
• 約数
• XOR
• Upper gauss記号とLower gauss記号

再帰 †

• 配る再帰
• 集める再帰

DP †

• 配るDP
• 集めるDP
• 一方向のみに依存するDP
• 一つ前のみに依存するDP

ゲーム必勝法 †

• アドホック
• Grundy数（二人完全情報ゼロ和不偏ゲーム）
• 後ろから決めていく

グラフ †

• 用語定義(DAG, 頂点、辺)
• ワーシャルフロイド
• ダイクストラ
• 経路復元
• 無向グラフの閉路検出
• 有向グラフの閉路検出とDAG化（強連結分解）
• 最大フロー最小カット定理
• フォードフルカーソン
• Dinic
• 二部マッチング
• 最小費用流

RMQ †

• 3つ合った気がする

木 †

• オイラーツアー
• 木の直径
• Tarjan's Offline LCA
• ダブリングによるLCA
• 重軽分解
• Splay木
• Link-Cut Tree

範囲クエリデータ構造 †

• モノイド・群再び
• モノイド・群、具体例
• Fenwick Tree
• Segment Tree
• 遅延Segment Tree
• 動的Segment Tree

高速フーリエ変換 †

• 畳み込み演算

高速ゼータ変換 †

高速メビウス変換 †

半分全列挙 †

枝刈り全探索 †

文字列 †

• Suffix Array
• 回文

幾何 †

• 多角形の成立条件

置換 †

• どこかでサイクルする

細かいテクニック †

• 確率的判定
  • 多項式判定(mod)
  • 行列のやつ
• nの累乗空間
• ベン図（かぶる）
• 包除原理
• Fibonacchi数列
• 復元
• 正しい括弧列
  • 「'(' の数が ')' の数を下回ることなく進んでいき, 最終的に '(' と ')' の数が等しくなる文字列」
  • mayokoさんのセグ木二分探索解

ソート †

• クイックソート
• バケツソート
• Priority queueで自分でソート（D1E スターウォーズのやつ）

細かい注意 †

• intの*%/はマジ注意
• 数字リテラルはキャストする