CODE FESTIVAL 2016 予選B E. Lexicographical disorder

日本語につき問題文は略。

code-festival-2016-qualb.contest.atcoder.jp

解法を2つ紹介する。

遅い解法

まず、与えられた文字列たちに対してtrieを構築する。

f:id:hama_DU:20161018233842p:plain

↑{abra, abram, abroad, arrow}で trieを構築した図。各文字列の終端を示す頂点にマークを付けておき、各頂点には、「それ以下にある終端の数」を覚えさせておく。

クエリが来るたびに、対象の文字列を使って木を辿る。各分岐で、「今見ている文字よりも小さい」枝の先以下にある数値を合計する。これが、自分よりも辞書順で小さい文字列の数となる。

f:id:hama_DU:20161020211204p:plain

↑trie上で次辿る文字が b だとする。この場合、辞書順で b よりも a c e が若いので A+C+E を答えに足す。

この解法だと、最も長い文字列に対してクエリがたくさん来た場合が最悪のパターンで、その長さを ${ S_{max} }$ とおくと計算量が ${ O(QS_{max})}$ となり、制限時間内には処理が終わらない。

解法1 : パトリシア木

trieには子が1つだけで、かつ文字列の終端ではない頂点ができることがある。この頂点はあってもなくても答えに影響しないので、取り除くことができる。一見、定数倍の節約に思えるが、実はこれをするだけで深さが高々ルートの文字列長合計となる。

f:id:hama_DU:20161018233131p:plain

↑分岐が2つ以上または終端の頂点に色を付け、それ以外の頂点を省いた図。

理由は、木の深さが ${L}$ なら、その地点までの分岐が ${L}$ 個存在し、そのためには長さ 1〜L までの文字列が少なくとも 1 つずつ必要だから。すると文字列の合計長は ${ O(L^2)}$ のオーダーになる。逆に合計長を ${S}$ とすると、高さは ${O(\sqrt{S})}$ となるわけだ。また、分岐がなくて文字列が a, aa, aaa, ... , aa...aa となっても、合計長を ${S}$ とすると、高さは ${O(\sqrt{S})}$ となる。

f:id:hama_DU:20161018235100p:plain

木の高さが多くとも ${ \sqrt{S} }$ になったので、この状態ならば各クエリに対して木を辿っても答えが出せる。計算量は文字の種類数を ${ \sigma = 26 }$ として ${ O(\sigma^{2}Q\sqrt{S}) }$ となり、ギリギリだが間に合う。

解法2: 想定解

想定解法は、各文字列に対して一度だけ trie をたどる、というもの。これまでの解法において、答えを決めている部分は、trie上の頂点における分岐での処理であった。それは、「文字Xと文字Yを比較して、Xが若かったから答えに (文字Xを辿った頂点に書かれている数) を足した」という処理。この部分は対象の文字列が同じ場合、比較する箇所は同じなので前計算できる。

各文字列に対して、26x26の表を考える。table[X][Y] := 文字の辞書順が X < Y のとき、この文字列よりも若い文字列の数 とする。この表を trie を辿って構築する。具体例を示そう。S = {abra, abram, abroad, arrow} として、文字列 abroad に着目したとする。