はてなブックマーク

説明 最小費用流問題は，始点 s から終点 t までの流量 F のフローでコストが最小のものを求める問題である．Primal Dual は最小費用流問題を最短路反復で解くアルゴリズムである． 最短路反復アルゴリズムとは始点から終点までの重みの最短路を求め，そこに流せる限り流す．これを流したい分だけ流しきるまで (または流せなくなるまで) 繰り返す．といった原理に基づくアルゴリズムのことである．この最短路の計算を保守的なポテンシャルを用いて Dijkstra で行うものが Primal-Dual 法である． 計算量 O( V^2 U C )，ただし U は容量合計，C は費用合計． 使い方 グラフは有向で逆辺は無いものとする． Graph &g 有向で，任意の辺 (u,v,capacity,cost) に対して逆辺 (u,v,0,-cost) があるグラフ．この条件を満たす上で単純グラフでな

解説 Andrew's Monotone Chain は凸包を求めるアルゴリズムで，Graham Scan における角度計算を ccw に置き換えてロバストにしたものである． 点列を x 座標でソートした後，下側凸包と上側凸包を別々に求め，併合して凸包を構成する．下側凸包を求めるときは点集合を左から右に見ていき，進行方向が左側であるような最も右よりの点を取っていく．上側凸包の場合は右から左に見ていく以外は全く同一である．進行方向に対して同一直線上にある場合は，最も近いものを取ることで凸包上にある点を取りこぼすことなく凸包に入れることができる． 使い方 vector<point> convex_hull(vector<point> ps) 点集合 ps に対してその凸包を求める．ps は三点以上あることを仮定する． 計算量 O(n log n)． ソースコード vector<point> c

説明 巡回セールスマン問題とは，グラフが与えられたとき，全ての頂点を一度ずつ通る巡回路で，経路長が最短のものを求める問題である． この問題は（判定問題にして）NP 完全であることが知られているので，多項式時間の解法は期待できない．単純に全ての経路を試すアルゴリズムは O(V!) 程度の計算量がかかるが，動的計画法に基づくアルゴリズムでは O(V 2^V) 程度の計算量に軽減できる． X[j][S + {j}] = E[j][i] + X[i][S] ここで X[i][S] は始点から i に至る S のすべての頂点を通る最小重み巡回路である．状態 S をビットで管理することによってプログラムが簡潔になる． 計算量 O(n 2^n)． ソースコード void rec(vector< vector<int> >& Y, int i, int S, vector<int>& path) { if

説明 浮動小数点計算に由来する誤差を避けるための最終兵器．一応数理に区分しているが，本当にこれが必要になるのは，幾何の問題のほうが多い． ひととおり定義すべきものを定義してあるので，普通の数を使っているところを形式的に rational に置き換えればだいたい動く．しかし繰り返し計算をしていると分子・分母ともに大きな数となり，オーバーフローすることがあるので，過信は禁物である． ソースコード typedef long long Integer; Integer gcd(Integer a, Integer b) { return a > 0 ? gcd(b % a, a) : b; } struct rational { Integer p, q; void normalize() { // keep q positive if (q < 0) p *= -1, q *= -1; Inte

説明 Fenwick木は，累積値を計算するためのデータ構造である．扱える代数構造を制限することにより，Range Minimum Query の記憶容量を節約したものと見なすこともできる． Fenwick 木は次の操作を許すデータ構造である． z[k] = z[k] + a と更新する． z[i] + z[i+1] + ... + z[j] を計算する． 取り扱える演算子 + には結合性，可換性，可逆性を要求する．すなわち加群である必要がある． 計算量 add: O(log n)． sum: O(log n)， 使い方 add(k, a) == v[k] = v[k] + a sum(i, j) == v[i] + ... + v[j] (両端を含む) ソースコード template <class T> struct fenwick_tree { vector<T> x; fenwick_

Software Engineer, Meta, Inc.1 Rathbone Square, Fitzrovia, London, W1T 1FB, United Kingdom Takanori Maehara is a Software Engineer at Meta (previously known as Facebook). Before joining Meta, he spend 8 years in academia as Post-Doctoral Researcher at National Institute of Informatics, Assistant Professor at Shizuoka University, and Unit Leader at RIKEN Center for Advanced Intelligence Project. He

説明 Trie は文字列のための多分探索木である．各頂点はアルファベットで指定できる枝の集合を持つ．文字列ひとつが根からアルファベットで辺を手繰ることで行き着く頂点に対応する． アルファベットサイズを定数と見たとき，文字列の数に対して trie のサイズは O(m) である．ただし m は蓄えられている文字列の長さの総和．これは通常の二分木で蓄えるのに対して特に不利ではない．検索性能は検索文字列の長さ n に対して O(n) である．これはうまく実装された二分木が O(n + log m) であることと比較して高速である． 結論として，文字列に対して std::map を使いたい場合は trie で代用できないか考えるべきである． 計算量 検索: O(n)，ただし n は検索する文字列長． 使い方 Trie *find(char *t, Trie *v); t に対応する Trie の頂点

説明 再帰下降型構文解析は BNF で与えられた文法を解析する手法である．与えられた BNF を直接書き下すことでパーシングを行うことができる．ここでは LL(1) パーザの例として四則演算パーザを題材に，作成法を示す． 1. BNF を書く 再帰下降型のパーザを書くためには，まず BNF を書かなければならない．BNF でかける文法は二型文法(文脈自由文法)とよばれるクラスになる．これは実用上最も有用なクラスなので，多くの用途にはこれで足りる． 四則演算の BNF は次のようになる．どうせ自分でパーザを書くので BNF のきちんとしたルールに従っていなくても書ける気がすれば適当なルールを追加してよい． equation := equation + factor | factor factor := factor * term | term term := (equation) | Num

Software Engineer, Meta, Inc.1 Rathbone Square, Fitzrovia, London, W1T 1FB, United Kingdomtmaehara@fb.com (work), tmaehara@acm.org (private)Takanori Maehara is a Software Engineer at Meta (previously known as Facebook). Before joining Meta, he spend 8 years in academia as Post-Doctoral Researcher at National Institute of Informatics, Assistant Professor at Shizuoka University, and Unit Leader at R

説明 点の集合が与えられる．領域が与えられたとき，その領域に含まれる点をすべて報告せよ．という問題を領域探索問題という．これは点位置決定問題の双対問題である．幾何学的な問題だけでなく「年齢 20～30 歳，年収 500～1000 万の人をすべて探せ」などのデータベース問い合わせもこの問題に帰着する． この問題を解くために使える構造が kd 木である．これは一次元における二分探索木の拡張であって，探索木の各段階で x における比較，y における比較を切り替えるものである．点が一様に散らばっている場合，二分探索木と同様に平均計算量 O(log n) となる． 以下では問い合わせ領域は直交領域，すなわち x 軸と y 軸に平行な辺をもつ長方形に限っている．しかしどんな形状の領域でも，bounding box をとるなどしてそれが半平面のどちらに位置するかを高速に判定できれば問い合わせ可能である．

Suffix Array (Larsson-Sadakane) 説明 Suffix Arrayとは，与えられた文字列の接尾辞の集合を辞書順ソートしたものである．近年，これを用いることによって多くの文字列の問題が解かれることがわかってきた． Larsson-Sadakane は Suffix Array を O(n (log n)^2) 時間で構成するアルゴリズムである．Mamber-Myers と同様のアイデアによって文字列長を倍加させ，O(log n) 回の multikey quicksort を行うことにより，全体で O(n (log n)^2) の計算量を達成する．詳しくは適当な文献を参照． Suffix Array を用いて解けるもっとも典型的な問題は，文字列の検索である．Suffix Array 上で二分探索を行えば，O(m log n) でパターンの検索ができる．また，Suf

説明 無向グラフが与えられたとき，その全域の最小カットを求める． まず，グラフの最大隣接順序を計算する（適当な頂点 v_1 からスタートし，それに隣接する最大頂点を選ぶ．これを繰り返す）．それを [v_1, ..., v_{n-1}, v_n] とする．このとき，次の定理が成り立つ：「v_n と v_{n-1} を分けるカットの中で最小のものは，v_n とそれ以外に分けた場合のものである」．したがって，これを計算した後に v_n と v_{n-1} をまとめた頂点を作ってこの操作を繰り返せばグラフ全域の最小カットが求まる． このアルゴリズムははじめに Nagamochi-Ibaraki によって提案され，Stoer-Wagner が簡単化したという経緯がある． 計算量 最大隣接順序はフィボナッチヒープを用いて O(E + log V) で計算でき，縮約は高々 V 回で終わるので合計 O(V

説明 グラフ G と始点終点の対 (s,t) が与えられたとき，s-t パスの中で k 番目に短いものを求める問題を k-最短路問題という． この問題に対する最も基本的な解法は，優先度付きキューを用いてダイクストラ調にグラフを探索し，通常なら最短距離が確定した頂点を切り捨てるところを k 個の最短距離が確定した頂点を切り捨てるようにすることである（以下に実装を示した）．この方法で計算量 O(k E log V) が達成できる．多くの応用ではこれで十分だと考えられる． 理論的にはもっと頭の良い解法が提案されており，例えば Eppstein による deviation に基づくアルゴリズムは O(k + E + V log V) を達成する．しかし，このアルゴリズムはパスを管理するデータ構造を持たなければならず，シンプルに実装するのは難しい．そこで以下では Eppstein の方法を参考にした

愛用エディタ Vim の設定ファイル．なんでこんな設定にしたのかもはや覚えていないものも多数． _vimrc " user configuration file " indentation set ts=2 set sw=2 set expandtab filetype plugin indent on " dir settings set backup set backupdir=c:/tmp set directory=c:/tmp " move displayingline-wise nnoremap j gj nnoremap k gk " autodate let autodate_disable = 0 let autodate_lines = 1000 let autodate_keyword_pre = "Last Modified: " let autodate_keyw

説明 複数のパターン文字列からなる集合と長い文字列が与えられる．長い文字列に対してマッチするパターン文字列をすべて求めるアルゴリズムが Aho Corasick である．これは複数パターン文字列をあらかじめ trie に変換してから KMP を実行し，パターンマッチング・オートマトンを構成していることになる． 詳しくは適当な成書や http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf などを参考のこと． 計算量 構築 O(m)． 検索 O(n + m)． ただし m はパターンの文字列長の総和，n は検索テキスト長． 使い方 struct PMA; を適宜設定のこと． buildPMA(char *p[], int m) 0 ... m-1 の複数の検索パターンから，パターンマッチング・オートマトンを構築する． match(c

説明 Union Find は互いに素な集合を扱うための道具である．Union Find を用いると以下の操作を高速に行うことができる． union_set(x,y): x が入っている集合と y が入っている集合を併合する． find_set(x,y): x と y が同じ集合に入っているかを判定する． make_set(x): x のみが入る集合 {x} を作る． アルゴリズムは次の考え方による．集合を多分木で管理し，木の根を集合の代表元とみなす．集合の併合は木の併合，二つの要素が同じ集合に入るかどうかは代表元が等しいかどうかの比較で行う． これらの走査を単純な木で行った場合，検索や併合に最悪 O(n) かかってしまう．そこで平衡操作を取る．具体的には木の要素を手繰ったとき，それらの親ポインタをすべて根に張り替える．このときの計算量を見積もるのは複雑だが，ならし解析によって O(A(n

解説 ドロネー三角形分割を逐次添加 - 辺フリップ法で行う． 計算量 O(n^2) (各点について O(n) でそれを含む三角形を得，平均 O(log n) で更新．これを n 回行う)． 使い方 double deaunay(vector<point> &P) 点集合 P を与え，ドロネー三角形分割する．E がドロネーグラフを表現する． TODO コード長の短縮とか，ひどい #define をなんとかするとか． 三角形分割木を構成すれば計算量が O(n log n) になるはずだが． ソースコード bool incircle(point a, point b, point c, point p) { a -= p; b -= p; c -= p; return norm(a) * cross(b, c) + norm(b) * cross(c, a) + norm(c) * cross(