概要 †

  • プロコンで必要となる知識のまとめ。
  • 特にこのページはアルゴリズムのまとめ。
  • アルゴリズムが判ってない、計算量が判ってないから、「○○は遅いからダメ」みたいなのをあらゆる状況で言っちゃう人は割と多い。必要なところだけ早くすればいい。
  • 以下の問題を何とかしたいから勉強しているのだけど、キリがないという気分
    1. 正しいと信じてるプログラムが間違ってるケースを減らしたい
    2. 脳内でこうやればできる、というところと実装の溝を減らしたい。実装を単純作業にしたい
    3. トップレベルの人でも普通知らない、非自明かつ一般的なアルゴリズムを使えるようになりない
    4. 典型なのに知らずに解けないケースを減らしたい
↑

記録 †

↑

下位ページ †

↑

目次 †

↑

練習方法 †

  • 解いた問題数を増やすのは良い事なんだけど、解いた問題数を増やすためだけに、簡単な問題を解きまくるのってすげえ時間の無駄
  • Codeforces
    • 黄色の人とかがCFのBCD埋めるのは典型力と非典型力と実装力が程よくついていいと思うけどE埋めは本当に虚無なのでやめた方がいいと思う
    • Eには典型重実装がたくさんあって不毛
  • AOJ-ICPC
    • 多くの人にはオススメできない気がしてきました。
    • 自分はすごい実力ついたと思っていたけれど、赤になってから実装力不足が目立ち始めたから始めただけ
    • 赤になるまでは質の高い問題をひたすら解くべき
↑

参考 †

↑

勉強すべきこと †

  • 重要度順
↑

重要 †

↑

そこそこ †

↑

どうでもいい †

  • ADS
  • 2-SAT
  • Treap, RBST(k-th tree), 平衡二分木
  • デク・優先度付キュー
  • ボロノイ図とデローネイ三角形分割
  • 美術館問題
  • 最短路問題
  • 埋め込み
  • Stern-Brocot木
  • ベルヌーイ数列挙 O(n^2)
  • 分割数 O(n√n)
  • スターリング数 O(n^2)
  • Chordal graph
  • Cograph
  • Stoer-Wagner
  • 永持-茨木法 (全点対最小カット)
  • 有向木の部分木のハッシュ
  • Knuth-Morris-Pratt
  • Aho-Corasick
  • CIPR (最長共通部分列)
  • 編集距離 O(nm)
  • 部分回文列挙
  • Segment Treeでローリングハッシュ
  • Segment treeでflip/count: !libuwi/utils/structure/segtree/SegmentTreeRXQ.java
  • Segment treeで点更新・範囲le/geカウント
  • Skip List
  • Van Emde Boas tree (vEB tree)
  • Fixed Universe Structures
  • 永続的平衡2分探索木
  • BK-tree
  • Trie
  • Meldable heap
  • 削除・更新のできる2分ヒープ
  • Double-ended priority queue
  • キュー with minimum
  • Shunting-yard algorithm
  • 平面グラフ 双対なものが構成できる。
  • 木について
(1) 頂点uの値をxに変える
(2) 頂点u, vを結ぶ最短パスの頂点のうち、最小値を答える
というクエリを、O(log n)で処理できないという結論に至った。（今の僕には）
  • Shunting-yard algorithm

 

↑

ライブラリ †

  • はむこのライブラリ
  • TODO
    • エラトステネスのかわりに区間篩を使って実装。
    • 区間篩じゃないとかなり大きい範囲の素数全列挙はできないという噂
  • まだ追記が必要なものまとめ
アルゴリズム概要計算量
Johnson前処理 O(V E)． 中間処理 O(V E log V)． 後処理 O(V^2)．
Warshall Floyd全点から全点への最小コスト。O(V^3)、だが漸化式が単純なので速い。
Dijkstra1点から全点への最小コスト。コストは正でなければならない。O(E log V)
K ShortestO(k E log V)
Prim最小重み無向全域木＝重みつき無向グラフの全域木の中で、重みが最小のものを求める。根は指定する。O(E log V)
Cuninghame-Green最小直径無向全域木＝重みつき無向グラフの全域木の中で，直径が最小のものを求める前処理O(V^3), 端点計算O(VE)
Chu-Liu/Edmond最小重み有向全域木＝重み付き有向グラフの全域木の中で、重みが最小のものを求める。根は指定する。O(VE)
Dreyfus-Wagner最小重みシュタイナー木＝頂点群Tを通る木の中で、重みが最小のものを求める。t=11が限界。時間O(n 3^t + n^2 2^t + n^3)．空間計算量 O(n 2^t)．
Edmonds-Karp有向最大流O(E^2 V)
Goldberg-Tarjan有向最大流O(V^2 sqrt(E))
Nagamochi-Ibaraki無向グラフ最小カットO(VE + V log V)
Gomory-Hu最大流O(V MAXFLOW)
木の高さの最大値木の直径が最小になるような根を計算O(E)
Double Sweep＝木の直径葉と葉の最大距離を計算O(E)
有向オイラー路存在判定すべての辺をちょうど一度通る閉路があるか判定O(E)
無向オイラー路存在判定すべての辺をちょうど一度通る閉路があるか判定O(E)
無向中国人郵便配達問題O(o m log n + o^2 2^o), o=18が限度
最短ハミルトン路すべての頂点をちょうど一度通る閉路を求める。判定もNP困難。O(V^2 2^V), V=18が限度。全探索はO(V!)なので少し落ちてる
レンジ木
Splay木平衡二分木
Interval Tree
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS