O(sqrt(N))のアルゴリズム

これはCompetitive Programming Advent Calendar Div2012に投稿された記事です。
さて、 $N=1,000,000,000$ みたいな数値を見ると、 $O(N)$ は無理だから $O(\log N)$ かとか、もしくは $N=100,000$ だと $O(N\log N)$ と思ってしまう人は多いでしょう。ですが、 $\log N$ まで行かなくてももう少し悪い計算量が想定解の場合もあります。というわけで、今回は $O(\sqrt{N})$ だとか $O(N^{1.5})$ という、ルートが入ったあまり見ない計算量のアルゴリズムを紹介します。

等差数列の和

$N=\sum_{x=1}^yax+b$ となるようなyを見つける問題はO(1)で解けますが、Nになるまで愚直に足していけば $O(\sqrt{N})$ で解けます。こんなもんどこで使うんだと思う人もいるかもしれませんが、手計算が面倒な場合とか証明したい場合に使います。

素数判定

素数判定は $O(\sqrt{N})$ までの数値で試し割りすることによって判定できます。もちろんミラーラビン法などを使えばもっと高速に判定できますが*1手軽に使えるというメリットがあります。

floorの分割

$f(N)=\sum_{x=1}^Ng({\rm floor}(N/x))$ みたいな式があったとしましょう。ただし、 $g({\rm floor}(N/x))$ は $O(1)$ で計算できるとします。
この式を愚直に計算すると、もちろん $O(N)$ かかってしまいます。ここで ${\rm floor}(N/x)$ が同一のものをまとめて処理することにします。すると $f(N)=\sum_{y\in S}c(y)g(y)$ となります。ただしSはfloor(N/x)の値域、c(y)はfloor(N/x)=yとなるxの個数とします。
Sのサイズを計算すると実は $O(\sqrt{N})$ で抑えることができます。なぜ、Sのサイズが $O(\sqrt{N})$ で抑えることができるかとういと、 ${\rm floor}(N/x)=y \le \sqrt{N}$ となるyはもちろん $\sqrt{N}$ 個以下しか存在しません。一方で ${\rm floor}(N/x)=y > \sqrt{N}$ となるには $x < \sqrt{N}$ という条件を満たさなければならないのでこれも $\sqrt{N}$ 個以下しか存在しません。なのでこの式を $O(\sqrt{N})$ で計算することができます。
問題例：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3558

離散対数問題

離散対数問題とはa,b,Nがgivenの下で $a^m \equiv b {\rm mod} N$ となるようなmを見つける問題です。
この問題は効率的な解法が見つかってませんが*2、baby-step giant-stepを使えば $O(\sqrt{N})$ で解くことができます。
まず、 $m=x+y\sqrt{N}$ と分割し、 $a^0, a^1, \ldots, a^{\sqrt{N}}$ までは普通に計算しハッシュなどに結果を保持しておきます。次に $a^x\equiv ba^{-y\sqrt{N}} {\rm mod} N$ を考えます。yを[0, $\sqrt{N}$ ]の範囲で全探索すると右辺は値が固定されるので、先程計算しておいたハッシュに値が含まれているかどうか確認すればxが求まります。
前処理も全探索の処理も両方 $O(\sqrt{N})$ なので、 $O(\sqrt{N})$ で答えが見つかります。
問題例：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3067

平方根分割

主にクエリの平方根分割と配列の平方根分割があります。
クエリの平方根分割はクエリを $\sqrt{Q}$ 個処理するごとにデータ構造を作り直し、それぞれの区間で使われていない値を無視することにより各クエリを $O({\sqrt{Q})$ くらいで処理できるようにします。
配列の平方根分割は配列を $\sqrt{N}$ のブロックごとに分割し、[l,r]の範囲クエリが来た時にブロックを全て含む部分は高速に処理し、端っこの部分は愚直に処理します。ブロックの数は $O(\sqrt{N})$ 個しかないし、端っこの部分は $O(\sqrt{N})$ 個のデータしかないので1つのクエリあたり $O(\sqrt{N})$ で処理できます。
ここらは毎回使うデータ構造が微妙に異なってくるので、回数をこなして慣れましょう。ちなみに平方根分割の問題はだいたい平衡二分木や動的木などを使えば計算量が落ちる上に、ライブラリを持っているとそっちの方が実装が楽になります。

問題例（クエリの平方根分割）：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235
問題例（クエリの平方根分割）：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=288&page=show_problem&problem=1962
問題例（配列の平方根分割）：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3154
問題例（配列の平方根分割）：http://codeforces.com/problemset/problem/121/E
問題例（Block Linked List）：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3073

二部マッチング

Hopcroft-Karpアルゴリズムを使えば二部マッチングは $O(E\sqrt{V})$ で解けます。
Hopcroft-KarpとはDinicのアルゴリズムを二部マッチングに適用したものです。つまり、フェーズごとにレベルグラフ*3を作り、各フェーズで増加パスが存在する限りフローを流すアルゴリズムです。
計算量の解析としては、まず容量が1なので各フェーズの処理が $O(E)$ に落ちます。次に、 $\sqrt{V}$ のフェーズを過ぎると増加パスの長さが $\sqrt{V}$ 以上になりますが、解のマッチングとの対象差(辺集合のxor)を比べた時に残る点素な増加パスはたかだか $\sqrt{V}$ 個なので*4、残りのフェーズの数は $O(\sqrt{V})$ 個で抑えられます。両方を合わせると $O(E\sqrt{V})$ となります。
問題例：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2279

最大流問題

最大流問題のアルゴリズムはEdmonds-KarpやDinic、藤重のアルゴリズムなど色々あります。
そして、Goldberg-Tarjanアルゴリズムは最大流問題を $O(V^2\sqrt{E})$ で解きます。
藤重のアルゴリズム（ $O(VE\log u_{\rm max})$ ）は計算量に容量がはいっていて、ナイーブなDinicは $O(V^2E)$ なので、これらのアルゴリズムよりも理論上は高速に動きます*5。計算量の証明をすると長くなるので省略しますが、各フェーズで不飽和プッシュの起こる回数を $\sqrt{E}$ 以下と以上に分割することにより $\sqrt{E}$ がかかっています。
さて、Dinicの計算量は $O(V^2E)$ と書きましたが辺の容量が1であるという制約がかかっている場合は $O(\min (V^{2/3},\sqrt{E})E)$ まで計算量が落ちます。なぜ $\sqrt{E}$ になっているかというと、 $\sqrt{E}$ 回目のフェーズであればレベルグラフのd層目とd+1層目の間に辺が $\sqrt{E}$ 以下しかない所が出てくるため*6、残りの増加パスはたかだか $\sqrt{E}$ 個しかない、つまり残りフェーズがたかだか $\sqrt{E}$ 個しかないことが言えるからです。 $V^{2/3}$ も辺が頂点に変わっただけでほぼ同じ証明でできます。

まとめ

$\sqrt{N}$ が入っているアルゴリズムを色々紹介しました。
$\log N$ の方はたびたび出ますが、時々でいいから $\sqrt{N}$ のことも思い出してやってください。
たまに出てくるので。

参考文献

Wikipedia Baby-step giant-step：http://en.wikipedia.org/wiki/Baby-step_giant-step
Wikipedia Hopcroft-Karp：http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
組合せ最適化：http://www.amazon.co.jp/dp/4431100210
どっかの大学の講義資料：http://people.orie.cornell.edu/dpw/orie633/LectureNotes/lecture9.pdf

*1:感覚的には $N\le 10^9$ で $O(100)$ くらい

*2:入力ビット数について多項式時間で解く方法は見つかっていない

*3:全頂点について始点からの距離がを求めておいて、距離が+1される箇所にのみ辺を張ったグラフ

*4:頂点の数÷増加パスの長さ≧点素な増加パスの個数なので $V / \sqrt{V} = \sqrt{V}$ となり $\sqrt{V}$ 個以下になる

*5:最大流問題の計算量の解析はフェーズが $V-1$ 個あるとか、ブロックフローの計算に $O(VE)$ かかるとか、不飽和プッシュが $O(V^2\sqrt{E})$ 回行われるとか普通起こらないことを前提としているため、実際に動かすと計算量以上に速く動く。競技プログラミングではDinicで十分なことがほとんど。

*6:辺の数÷層の数＝ $E/\sqrt{E}=\sqrt{E}$ ≧各層で使われている辺の数の最小値なので