\(\Theta(n \polylog(n))\) 時間で解くのは簡単だけど、実際には \(\Theta(n)\) 時間で解けるよーという問題はちょくちょくあります。 競プロ界隈では log を削ることに意欲的な人は一部だけな気がします*1が、話として知っておいても損はあまりない気がするので、挙げてみます。
ここではざっくり紹介するに留め、詳細は各自調べてもらうようなスタンスになっています。
紹介
RMQ
長さ \(n\) の配列 \(a = (a_0, a_1, \dots, a_{n-1})\) に対して、区間最小値 \(\min_{l\le i\lt r} a_i\) をクエリ形式で答えよ。ただし、更新クエリは来ない*2。
セグ木を使うと \(\angled{\Theta(n), O(\log(r-l))}\) で解けるものの、クエリ時間も \(O(1)\) にしたいです。
これは、sparse table と MoFR (method of Four Russians) で \(\angled{O(n), O(1)}\) で処理でき、線形 RMQ*3とか \(\angled{O(n), O(1)}\)-RMQ などの言い方で言及されがちです。
CS166 スライド など。
中央値
長さ \(n\) の配列 \(a = (a_0, a_1, \dots, a_{n-1})\) に対して、\(a\) を昇順にソートした列 \(b\) を考える。\(a\) の中央値 \(b_{\floor{n/2}}\) を答えよ*4。
ソートして真ん中を答えればよいですが、ソートのために最悪 \(\Omega(n\log(n))\) 時間かかってしまいます。
これは、median of medians と呼ばれるアルゴリズムで \(O(n)\) 時間で求めることができます。 AtCoder で Median of Medians と呼ばれる別の設定の問題が出題されたため、検索しにくい感じがあります。
Introduction to Algorithms などに載っています。
篩による素数判定
正整数 \(n\) が与えられる。長さ \(n\) の整数列 \(p = (p_1, p_2, \dots, p_n)\) であって、\(i\) が素数のとき \(p_i = 1\)、そうでないとき \(p_i = 0\) となるものを答えよ。
Eratosthenes の篩と呼ばれるアルゴリズムで \(O(n\log(\log(n)))\) 時間ですが、線形篩と呼ばれる \(O(n)\) のアルゴリズムが存在します。 配る DP っぽく遷移しながら篩っていくのですが、素因数分解の一意性によって遷移の個数が \(O(n)\) 個に抑えられるような遷移をします。
実際には Atkin の篩などの劣線形*5アルゴリズムもありますが、競プロ界隈ではあまり見ないです。他の篩アルゴリズムもあった気がします。
過半数
長さ \(n\) の配列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられる。\(a\) のうち過半数を占める要素があればそれを出力し、なければその旨を報告せよ。 ただし、\(x\) が過半数を占めるとは、\(|\{i\mid a_i = x\}| \gt |\{i\mid a_i \ne x\}|\) を満たすことを言う。
ソートなり連想配列を使うなりしてカウントすれば求められはします。ソートしたり木ベースの連想配列を使ったりすると log がついてしまいます。 あるいは、ハッシュベースの連想配列では最悪計算量が保証できなくなってしまいます。
Boyer–Moore majority vote algorithm というのがあります。 ある要素 \(x\) に対して、それと異なる要素 \(y\) をペアにして消していくのを繰り返すと、消えずに残った（高々一種類の）要素が過半数の候補となります。 そこで、その候補の個数を数えればよいです。
ペアにして消すのは先頭から順に見ていけばよいので \(O(n)\) 時間でできます。大小判定 (\(\lt, =, \gt\)) ではなく同値判定 (\(=, \ne\)) しか必要ないのも汎用的ですごいです。
Boyer, Robert S., and J. Strother Moore. “MJRTY—a fast majority vote algorithm.” In Automated Reasoning, pp. 105–117. Springer, Dordrecht, 1991.
wikipedia にも載っています。
行最小値
\(n\) 行 \(m\) 列の行列 \(a = (a_{i, j})\) が与えられる。ただし陽には与えられず、\(a_{i, j} = f(i, j)\) なる \(f\) を呼び出すことで値が得られるとする。 このとき、各 \(i\) に対して \(i\) 行目の最小値を持つ列 \(\argmin_j a_{i, j}\) を求めよ。
ただし、\(a_{i, j}\) は totally monotone であるとする。すなわち、\(i\lt i'\), \(j\lt j'\) に対して \(f(i, j) \gt f(i, j') \implies f(i', j) \gt f(i', j')\) とする。 簡単のため、\(a\) は distinct とする。
totally monotone より弱い条件である monotone の性質として、\(i \lt i' \implies \argmin_j a_{i, j} \le \argmin_j a_{i', j}\) というのがあります。 これを利用した簡単な分割統治のアルゴリズムによって \(O(n + m\log(n))\) 時間で解けます。
分割統治のアルゴリズム
まず、\(n/2\) 行目の最小値を持つ列 \(j' = \argmin_j a_{n/2, j}\) を \(O(m)\) 時間で求めます。 それより上の列については \(j'\) 列目以下のみ、下の列については \(j'\) 列目以上のみを探索すればよいです。
SMAWK algorithm というのがあります。
まず偶数行目についてのみ（うまいこと再帰して）求め、奇数行目については偶数行目での答えと total monotonicity を利用して線形時間で求めます。 全体で \(O(n+m)\) 時間です。
行列のアクセス順に関して、\(i\) 行目の最小値を求めるまでは \(i\) 列目 \(f(\bullet, i)\) の値を得られないという制約を追加した問題設定もあります。 これは、ある種の DP の言い換えと見ることができる（状態 \(i\) への遷移コストの最小値が \(i\) 行目の最小値に、状態 \(j\) に最小コストで遷移してから状態 \(i\) に遷移したときのコストが \(f(i, j)\) に対応する）のですが、これも \(O(n)\) 時間で求めることができます。LARSCH algorithm と呼ばれるアルゴリズムです。
- Aggarwal, Alok, Maria M. Klawe, Shlomo Moran, Peter Shor, and Robert Wilber. “Geometric applications of a matrix-searching algorithm.” Algorithmica 2, no. 1 (1987): 195-208.
- Larmore, Lawrence L., and Baruch Schieber. “On-line dynamic programming with applications to the prediction of RNA secondary structure.” Journal of Algorithms 12, no. 3 (1991): 490–515.
接尾辞配列
長さ \(n\) の文字列 \(s = s_0 s_1 \dots s_{n-1}\) が与えられる。各 \(i \in\halfopen{0}{n}\) に対して、\(s\) の接尾辞 \(s_{i\dots}\) を \(s_i s_{i+1} \dots s_{n-1}\) と定義する。また、\(s_{n\dots}\) は空文字列とする。
このとき、\(\{0, 1, \dots, n\}\) の順列 \(p = (p_0, p_1, \dots, p_n)\) であって、\(s_{p_0\dots} \lt s_{p_1\dots} \lt \dots \lt s_{p_n\dots}\) となるものを求めよ。
ここでの \(p\) が接尾辞配列 (suffix array, SA) と呼ばれるものです。 これは、愚直に接尾辞を毎回作りながらソートすると \(\Omega(n^2\log(n))\) 時間かかりそうです。 蟻本などには \(\Theta(n\log(n)^2)\) の方法が載っていたり、\(\Theta(n\log(n))\) 時間のアルゴリズムが知られていたりします。
アルファベットを \(\Sigma = \{0, 1, \dots, \sigma-1\}\) (\(\sigma = n^{O(1)}\)) と仮定します。すなわち \(s_i\in\Sigma\) です。 このとき、SA-IS (suffix array, induced sorting) と呼ばれるアルゴリズムがあり、\(O(n)\) 時間でできます。
Nong, Ge, Sen Zhang, and Wai Hong Chan. “Two efficient algorithms for linear time suffix array construction.” IEEE transactions on computers 60, no. 10 (2010): 1471-1484. や CS166 のスライド など。
SA-IS の登場以前にもいくつか SA の線形時間構築のアルゴリズムは存在していたようです。
最深共通祖先
頂点 \(r\) を根とする \(n\) 頂点の木が与えられます。頂点対 \( (u, v)\) の最深共通祖先をクエリ形式で答えよ。ここで、\(u\) の祖先でもあり \(v\) の祖先でもある頂点のうち、\(r\) から最も遠い頂点を \( (u, v)\) の最深共通祖先 (lowest common ancestor, LCA) という。
Euler tour を \(O(n)\) 時間で求め、区間最小値に帰着する方法は競プロ界隈でも有名です。ここで線形 RMQ を使えばよく、\(\angled{O(n), O(1)}\) で解けます。
クエリの先読みができる状況では、別のアルゴリズムもあります。
Decremental neighbor query
集合に対する以下のクエリを処理せよ。
- \(A \subseteq \{0, 1, \dots, n-1\}\) が与えられ、\(S \gets A\) で初期化。
- 与えられた \(i\) に対し、\(A \gets A \setminus\{i\}\) で更新。
- 与えられた \(i\) に対し、\(\min\,\{j\in A\mid j\ge i\}\) を出力。
- 与えられた \(i\) に対し、\(\max\,\{j\in A\mid j\le i\}\) を出力。
std::set や std::collections::BTreeSet 系の、平衡木などを使えば \(\angled{O(n), O(\log(n))}\) で処理できます。
あるいは、van Emde Boas tree などを使うと \(\angled{O(n), O(\log(\log(n)))}\) などになります。
\(\angled{O(n), O(1)}\) になります。\(O(1)\) 時間で更新できるのってすごいですよね。
Level ancestor
頂点 \(r\) を根とする \(n\) 頂点の木が与えられます。頂点と非負整数の対 \( (u, k)\) に対して level ancestor をクエリ形式で答えよ。ここで、\(u\) の祖先のうち、\(r\) からの距離が \(k\) である頂点を答える問題を level ancestor (LA) という。
ダブリングで求める方法や HL 分解で求める方法などが有名そうですが、最悪 \(\angled{\Theta(n), \Theta(\log(n))}\) や \(\angled{\Theta(n\log(n)), \Theta(\log(n))}\) です。
ladder algorithm や jump-pointers algorithm と MoFR を組み合わせることで、\(\angled{O(n), O(1)}\) のアルゴリズムが得られます。
Bender, Michael A., and Martin Farach-Colton. “The level ancestor problem simplified.” In Latin American Symposium on Theoretical Informatics, pp. 508–515. Springer, Berlin, Heidelberg, 2002.
SWAG
モノイド \( (S, \circ, \mathrm{id}_{\circ})\) がある。これに関する以下のクエリを \(n\) 個処理せよ。
- キューを空で初期化。\(q\gets ()\)。
- 与えられた \(x\in S\) をキューの末尾に追加。\(q \gets q \concat (x)\)。
- キューの先頭を削除。\(q = (q_0, q_1, \dots, q_{n-1})\) のとき \(q \gets (q_1, \dots, q_{n-1})\)。
- キューの \(\circ\)-fold を出力。\(q = (q_0, q_1, \dots, q_{n-1})\) のとき \(\mathrm{id}_{\circ} \circ q_0 \circ q_1 \circ \dots \circ q_{n-1}\)。
これは、two-stack queue と呼ばれる、スタック二つを用いてキューを実装する手法で、\(\circ\)-fold の値も（累積和のように）管理することで、ならし \(O(1)\) 時間で可能です。代わりに two-stack deque を使うことで、両方向の出し入れが可能です。
蟻本にある、いわゆる「スライド最小値」より広い問題設定に対応できます*6。
とはいえ、蟻本のスライド最小値（と、その直前にあるスタックによる最大長方形）で使うような、大小関係を利用する発想をできるようになっておくのも大事そうです。えびちゃんは苦手です。
SWAG (sliding window aggregation) という呼称は、競プロ界隈では上記の問題を解くデータ構造の意味合いで使われがちですが、下記の文献などを見た感じだと、もっと広い問題設定（あるいはデータ構造のインタフェース？）の意味合いで使われていそうです。
Hirzel, Martin, Scott Schneider, and Kanat Tangwongsan. “Sliding-window aggregation algorithms: Tutorial.” In Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems, pp. 11–14. 2017.
Gray code の利用
\(n\) 要素の集合に対して、ビット全探索で \(2^n\) 通りの集合を列挙して各々に対して \(\Theta(n)\) 時間で処理をするケースは頻出です。 このとき、\(\Theta(n\cdot 2^n) = \Theta(2^n\log(2^n))\) 時間かかっています。
ところで、\(2^n\) 通りの集合を列挙する順序のうち、以下を満たすようなものが常に存在し、かつ簡単に得ることができます。
- \(\emptyset\) から始まる。
- 最後に出力した集合に、1 つの要素を追加または削除することで次の集合を得る。
たとえば、3 要素であれば 000 → 001 → 011 → 010 → 110 → 111 → 101 → 100 といった具合です。
元々 \(\Theta(n)\) 時間かけていた処理が、差分のみの更新が \(O(1)\) 時間で可能なものであれば、上記の列挙順を利用することで \(\Theta(2^n)\) 時間になります。
±1 配列の転倒数
長さ \(n\) の配列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられる。配列 \(a\) の転倒数 \(|\{(i, j) \mid i \lt j \wedge a_i \gt a_j\}|\) を答えよ。
ただし、\(a_i \in\N\) であり、\(a_0 = 0\) かつ \(|a_i - a_{i+1}| \le 1\) とする。
一般の配列 \(a\) に対する転倒数は、平面走査なり分割統治なりで \(O(n \log(n))\) 時間で求められ、有名です。
上記の制約がある場合は、maspy さんの記事 のような方法で \(O(n)\) 時間にできます。
0/1 配列に対する転倒数は、\(w\)-bit 整数に \(w\) 個の要素を詰めて与えられるとすると、\(O(n/w\cdot \log(w)^2)\) 時間でも解けそうです。もしかしたらもっと速くなる？ わかりません。
周期検出
初期値 \(x_0 \in S\) (\(|S| \lt \infty\)) と関数 \(f: S\to S\) が与えられる。ただし、\(f\) は \(O(1)\) 時間で計算できる設定とする。
\(i \gt 0\) に対して \(x_i = f(x_{i-1})\) で定義するとき、ある \(\lambda\gt 0\) に対して \(x_{\mu} = x_{\mu + \lambda}\) と書けるような最小の \(\mu\ge 0\) と、それを満たす最小の \(\lambda\) を求めよ。
\(n = \mu+\lambda\) とおきます。
連想配列を用いると \(\Theta(n\log(n))\) 時間などで、空間も \(\Theta(n)\) になります。
tortoise and hare algorithm を用いることで、\(O(n)\) 時間、\(O(1)\) 空間で可能です。前述の majority voting のように、同値判定だけで済むのもおもしろいです。
周期検出 2
\(n\) 頂点の functional graph、すなわち \(n\) 本の有向辺 \(i, f(i)\) (\(0\le i\lt n\)) があるグラフが与えられる。 このとき、各 \(0\le i\lt n\) について、\(x_0 = i\) としたときの上記の問題の \( (\mu, \lambda)\) を求めよ。
がちゃがちゃやると \(O(n)\) 時間でできます。あんまりおもしろくはないかも。
その他メモ
同じ値で \(k\) 回の二分探索を行う際、愚直には \(\Theta(k \log(n))\) 時間になるが、fractional cascading を使うと \(O(k+\log(n))\) 時間に落とすことができる。
https://cs.brown.edu/courses/cs252/misc/resources/lectures/pdf/notes08.pdf
配る DP で区間加算が必要になるとき、双対セグ木を使わずに imos 法を on-the-fly で更新していくことで log をつけずにできる。えびちゃんはよくバグらせる。かわいそう。
union-find は十分な回数クエリするとならし \(O(1)\) 時間になるので、そういう場合は BFS するのと比べて損せずに済む。
文字列アルゴリズム界隈や簡潔データ構造界隈、線形時間前処理かつ定数時間クエリじゃないと気が済まないみたいな印象がある。
CHT で仮定を置くと log が消えるやつ。こっちの方が有名そうな印象はある。
\(n\) 以下の逆元の列挙。最近あんまり話題にならないね。
Fibonacci heap を使うと Dijkstra 法や Prim 法の \(O(m\log(n))\) が \(O(m+n\log(n))\) になるやつ。
個数制限ありナップサック問題を log なしで解くやつ。最近 ABC でそんな感じでやっても log がつかない（？）やつがあったような？
なんか忘れてるかも。思い出したら書く。
おわり
いくつ実装したことがありましたか？ いろいろな log なしアルゴリズムを実装していろいろな知見を得ましょう〜〜。
log ありで困ることがあるかと言われると微妙な感はありますが、log を消すアルゴリズムたちは（競プロであまり見慣れていないせいもあってか）天才に感じることが多く、面白いがちです。分割統治や MoFR などはそれ自体は典型的ですが、それらが使える形に変形するのは天才がちな気がします。
「これが log なしで解けるのか〜〜」という感情が生えるきっかけになれたらうれしいです。
ところで、\(n \log(n)\) が \(n\) になると log が消えた感があるのに、\(n\) が \(n/\log(n)\) になると log が消えた感はないですね。\(\log(n)\) で割れる系アルゴリズムもあまり有名でない感じがします。あるいは \(\log(\log(n))\) 系のものもあまり有名でない気がしますね。
