プロコン/スライド

プロコン

コンセプト †

• 構造化する。
• アルゴリズムを主体に置く
• 概要をきちんとかく
• 条件と入出力を大切にする
• 図解と具体例
  • アルゴリズムは図解が命！
• 工学応用
  • プロコンに限らず

アルゴリズムスライド †

はじめに †

• アルゴリズム
• 前処理とクエリ（構築と参照）
• 計算量
• モノイド・群（モノイドはどこから計算してもいい＝並列、群は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の*%/はマジ注意
• 数字リテラルはキャストする