読者です 読者をやめる 読者になる 読者になる

問題解決の宝石箱

競技プログラミング/数学ネタ置き場

CODE FESTIVAL 2016 予選B E. Lexicographical disorder

☆6 2016年 AtCoder

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

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 に着目したとする。

  • 2番目の文字の分岐で、r < b ならば arrow が自分より若くなるので、table[r][b] += 1 とする。
  • 4番目の文字の分岐で、a < o ならば abra, abram が自分より若くなるので、table[a][o] += 2 とする。

そして各クエリでは、与えられたアルファベット順の組み合わせに従い、表を調べれば良い。 計算量は文字の種類数を  { \sigma = 26 } として  { O(\sigma^{2}Q + \sigma N) } となる。こちらのほうが解法1より速い。

解答コード

パトリシア木 : E.java

想定解法 : E2.java

gist8b7a66f8155e1efa4832e3259d6f82df