PCK2020K (予選) - パスポート

問題文

Aizu Online Judge

解法

次のように定めます。求める答えは$${f(1)}$$です。

• $${f(v) := }$$(国$${v}$$から国$${N}$$まで最適に向かったとき、パスポートに書かれている文字列)

各国について、次に行くべき国が分かればよいです。これを末尾から決めていきます。

次に行くべき国の候補が$${x_1, \cdots, x_k}$$であるとします。このうち$${f(x_1), \cdots, f(x_k)}$$が最小になる国に行くのが最適です。以下では文字列を効率的に比較する方法を考えます。

比較したい文字列を$${f(y_1), f(y_2)}$$とおきます。「$${f(y_1)}$$と$${f(y_2)}$$の先頭$${t}$$文字が等しく、$${t + 1}$$文字目が異なる」ような整数$${t}$$を求めたいです。これは「$${f(y_1)}$$と$${f(y_2)}$$の先頭$${m}$$文字が等しい」ような最大の$${m}$$を求めることと同じです。$${m}$$で二分探索できるとして、判定問題を高速に解きたいです。

そこで、次に行くべき国を決めていく過程で、次の 2 つの値も計算しておくことにします。これらはダブリングの要領で計算できます。

• $${dest_{k, v} :=}$$(国$${v}$$から最適に進んだとき、$${2 ^ k}$$回進んだところにある国)

• $${hash_{k, v} :=}$$($${f(v)}$$の先頭$${2 ^ k}$$文字のハッシュ)

なお、文字列$${S = s_1 \cdots s_{|S|}}$$に対しそのハッシュは$${(\sum_{1\le i\le |S|} s_i \times \mathrm{base} ^ {|S| - i})\% \mathrm{mod}}$$で定めます。

これらを使うと、$${f(y_1), f(y_2)}$$の先頭$${m}$$文字のハッシュを$${O(\log m)}$$時間で求められます。よって、$${t}$$を$${O((\log N) ^ 2)}$$時間で求めることができます。

文字列の比較が$${O(N + M)}$$回あるため、$${O((N + M)(\log N) ^ 2)}$$時間で解くことができます。

提出コード

Aizu Online Judge