線形でできる予計算的な処理まとめ
この記事は、 Competitive Programming (1) Advent Calendar 2019 16日目の記事として執筆されました。
今回は、 線形時間、すなわち \(O(N)\) でできる予計算的な処理をいろいろとまとめてみようと思います。思いつくがままに並べているだけなので、ヌケモレがけっこうあると思いますが、「こういうのも線形前処理だよ～」みたいなのがあればTwitterとかで連絡していただければ随時足していこうと思います。なお、ここでの予計算的とは完全に個人の主観でちょっとでも「予計算っぽい感じあるかな」って思えば入れています。かなり基準が適当なのでそのへんはご容赦を。
数値計算系
順列の生成
\(1,2,...,N\) からなるランダムな順列が1つ欲しい時、これは \(O(N)\) で可能です。マラソンとか乱択とかで役に立つ時が多分あります。具体的には以下のような手順です。
\(A \leftarrow \{1,2,...,N\}\) の順列(1-indexed)とする。
for \(i=N..1\) step \(-1\)
\(p \leftarrow (1\) から \(i\) までの乱数)
\(A[p]\) と \(A[i]\) とをスワップする。
累乗の予計算
\(A[k] = X^k\) のテーブルをあらかじめ構成するのも \(O(N)\) で可能です。但し、 \(A[i+1] \leftarrow A[i] \times X\) というように安直に求めてしまうと、Xが実数である場合に誤差が蓄積してしまいかねません。ここでは、各要素についてその値に至るまでに行われた乗算の回数が \(O(\log N)\) となる実装を紹介します。
// \(A[i] = X^i\) となるようにしたい
\(A[0] \leftarrow 1\)
\(A[1] \leftarrow X\)
for \(i=2..N\)
\(A[i] \leftarrow A[i/2] \times A[i/2\ +\ i\%2]\)
ちなみに、行われた乗算の回数が \(O(\log N)\) となる理由は、 dp[行われた乗算の回数]\(=\{max(dp[i/2],dp[i/2\ +\ i\%2])+1\}\) というようなDPをイメージすると理解できます。
nCrをO(1)で求めるための予計算、逆元
\(nCr = \frac{n!}{r!(n-r)!}\) なので、これを \(O(1)\) で求めるためには \(k!\) とその逆元が求まっていればよいです。 \(k!\) を求めるのは容易ですがその逆元を愚直に求めていると予計算テーブルの構成に \(O(N \log mod)\) かかってしまいます。
しかし、以下のように求めると \(O(N+\log mod)\) で計算可能です。 \(N >> \log mod\) なのでこれは線形です。誰が何を言おうと線形です。
\(A[i] \leftarrow \{i!\}\) と求めておく。
\(B[N]\) を \(A[N](=N!)\) の逆元とする。
for \(i=(N-1)..0\) step \(-1\)
\(B[i] \leftarrow B[i+1]*(i+1)\)
//ここで、 \(B[i+1]\) は \(i!\times(i+1)\) の逆元なので、ここに \(i+1\) を掛けると \(i!\) の逆元となる。
逆元についての説明など、さらに詳しくは 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita を参照してください。
また、いくつかの数の逆元をまとめてとることも \(O(N+\log mod)\) で出来ます。詳しくは 逆元 - yukicoder Wiki を参照してください。
素数テーブル+(1を除く)最小の約数テーブルの構築
素数テーブルをO(n)で構築する - 裏紙 で示されているものなのですが、エラトステネスの篩を使って \(O(N \log \log N)\) かかる素数テーブルの構築を \(O(N)\) でできます。副産物として、mind[i] = {iの(1を除く)最小の約数} という配列もまとめて \(O(N)\) で得られます。
データ構造系
配列の初期化
これはとても自明な前処理レベルのことですが、配列の各要素の初期化は \(O(N)\) で可能です。いい感じにループを回せば任意の値で初期化できたり、乱数表を格納したりもできます。逆に、配列を重いループの中で愚直に初期化してしまうと重いループの中で線形かかってしまうので、「逆の手で初期状態に戻せる」ような状況ならそちらがベターです。
バケットソート
バケットソートは、値の最大値にも多少計算量が依存しますが、基本的に要素数に線形な時間で backet[i]={iが配列中にいくつ含まれるか}という配列が構成できます。値の最大値が \(10^5\) 程度もしくは座標圧縮してその程度にできるなら、ソートとしてバケットソートを意識してから問題を解くと見通しがいいことがあります。
0/1配列において自分まで何連続で1が続いたかをまとめて求める
要素数 \(N\) の0/1配列\(arr\)について、\(A[i] = ([i-k+1,i]\)がすべて1である最大の\(k)\)が求めたいとします。例えば、\(arr=\{01101111\}\)に対して\(A=\{0,1,2,0,1,2,3,4\}\)です。これは、以下の単純なアルゴリズムで配列全体で \(O(N)\) で求まります。
\(A[0] \leftarrow 0\)
for \(i=1..N\)
if \(arr[i]=0\) then \(A[i]=0\)
else \(A[i]=A[i-1]+1\)
これは二次元、それもグリッドっぽい感じの問題で頻出な処理で、この処理を使うと見通しが良くなる問題も結構あります。
BITやSegment Treeの初期化
それぞれのデータ構造については、 http://hos.ac/slides/20140319_bit.pdf , Binary indexed tree , セグメントツリー入門 , セグメント木 - 個人的な競プロメモ などを参照してください。
BITの初期化が \(O(N)\) というのは見るからに要素をN個しか使っていないため自明ですが、Segment Treeの場合だと、ノード数が \(2N\) 程度であるという事実があるので0初期化以外の初期化も \(O(N)\) で可能、というわけです。愚直な初期化だと \(O(N \log N)\) かかってしまうので、初期化についていい感じの実装をしてやると(計算時間的に)お得です。
累積和
何らかの値が入った配列 \(A\) があるとします。ここで、この配列に対して \(L_i\) 番目から \(R_i\) 番目までの和をたくさん求めたいとします。(例えば、DPをするときにkeyが \([L_i,R_i]\) のものだけを遷移させたいとか)
以下のような線形予計算をしておくと、これはクエリあたり \(O(1)\) で可能です。
\(B[0] \leftarrow 0\)
for \(i=1..N\)
\(B[i] \leftarrow B[i-1] + A[i]\)
クエリに対しての回答( \(L_i\) 番目の要素から \(R_i\) 番目の要素の総和)は、
\(B[R_i] - B[L_i-1]\)
詳しくは 累積和を何も考えずに書けるようにする！ - Qiita も参照してください。
imos法
先ほどの累積和の応用、言わずと知れた いもす法 - いもす研 (imos laboratory) です。これも線形前処理っちゃそうかな～という感じなので入れます。
全ての要素が0である長さ \(N\) の配列に、「範囲 \([L_i,R_i]\) の要素すべてにちょうど \(X\) を加える」という形のクエリが \(Q\) 個あるとします。
このクエリが最初にあらかじめ与えられるなら、以下のような処理でクエリをすべてまとめて \(O(N+Q)\) (配列の長さ+クエリ数に線形)で実行可能です。
\(A \leftarrow \{0\) で初期化された長さ \(N+1\) の配列\(\}\)
for \(i=1..Q\)
\(A[L_i]\)に\(X\)加算、\(A[R_i+1]\)を\(X\)減算
for \(i=1..N-1\)
\(A[i+1]\) に \(A[i]\) を加算
このimos法の次元を引き上げれば、「二次元上のある長方形の範囲に \(X\) 加算する」といったことも可能です。そちらも先ほどのリンクを参照してください。
文字列系
文字列の長さを求める
非常に自明なことですが、文字列の長さを求めるのには \(O(N)\) かかります。逆に言うと、文字列の長さを求める関数では1回あたり \(O(N)\) かかってしまいます。場合によっては一度求めた長さを保存しておくなどすることが必要です。
シーザー暗号的なもの
これは予計算というよりもはや前処理なのですが、convert[(変換前の文字)] = {変換後の文字}というような配列を構成しておけば、例えばconvert[(小文字)] = {そのまま}、convert[(大文字)] = {同じ文字の小文字} のような配列を作っておくと、大文字小文字吸収にかかる処理時間が文字列の長さに対して線形となります。
Trieの構成
Trieは、ざっくり言うと複数の文字列(の接頭辞)を管理するデータ構造です。詳しくは トライ木 - Wikipedia をご覧ください。このTrieの構成も文字列の長さに対して線形で可能です(実際は文字種が多いと実装によってはそれだけ定数が大きくなりますが)。ちなみに、文字列の追加が発生しないような条件下で、子が1つしかないノードをつぶして圧縮するといったことが要求されることもあり、この圧縮もノード数に対して線形で可能です。 E - Lexicographical disorder がその例です。(これを行うと検索にかかる時間が「文字列の長さに線形」から「絡む分岐の数」へと高速になります)
RollingHash
文字列 \(S\) からある区間を取ってきたときに、「区間と与えられた文字列が等しいか?」や「区間同士が等しいか?」などを(確率的に)判定したいときに重宝するのがこのRollingHashです。
ここでは、ある長さ \(K\) の文字列 \(s(=s[1]s[2]s[3]...s[K])\) のハッシュ値を
\(hash(s) = id(s[1]) \times base^{K - 1} + id(s[2]) \times base^{K-2} + ... + id(s[K - 1]) \times base + id(s[K]) \mod M \)
\(id\) は、 \(id('a') = 1,id('b') = 2,...,id('z') = 26\) のような、文字を相異なる数値に変換するなにかしらの関数。
\(M\) は、適当な定数。(これは素数が推奨される)
と定義し、これを高速に求めることを考えます。文字列が等しければこの値が一致しますが、逆は成り立ちません。(但し、異なる文字列が同じハッシュ値を取ってしまう確率は実際には低いです。)
まず、長さ \(N\) の文字列 \(str(=str[1]str[2]str[3]...str[N])\) に以下のような線形の予計算をかけます。
\(A[0] \leftarrow 0\)
for \(i=1..N\)
\(A[i] \leftarrow A[i-1] \times base + id(str[i]) \mod M\)
すると、区間 \([i,j]\) を抜き出した文字列 \(str[i]str[i+1]...str[j]\) に対してのハッシュ値は
\(A[j] - A[i-1] \times base^{j-(i-1)} \mod M\)
と、1回あたり \(O(\log N)\) で求められます。
ハッシュやRollingHashの詳しい説明はハッシュ関数 - Wikipediaや安全で爆速なRollingHashの話 - Qiitaを参照してください。
文字列に関する線形アルゴリズム
文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ でいくつかの文字列に関する線形時間のアルゴリズムについて有名になりました。詳細や実装は出題された時に写経すればどうとでもなるとしても、どのアルゴリズムを使えば何が線形でできるか知っておいて損はないでしょう。
Z-Algorithm: table[i] = (i文字目を先頭にして、文字列全体の接頭辞と何文字目まで一致するか)
Manacher: table[i] = (i文字目を中心にする、最長の回文の半径はいくらか)
KMP: table[i] = (先頭からi-1文字目までを抜き出したとき、接頭辞と接尾辞が最大何文字一致するか)
という長さ \(N\) の配列をそれぞれ全体で \(O(N)\) で求めることができます。
<あとがき>
線形で出来る予計算、いろいろまとめてみたら面白いかもな～って思い立ってまとめてみましたが、結構あるけど思ったよりはない…って感じの分量になりました(引き出しの狭さを痛感しています)。たぶんまだけっこうあると思うので、これも入れてほしい!みたいなものがあればご一報ください。知識の幅をどんどん増やして線形爆速アルゴリズマーになりましょう!(?)
