Educational Codeforces Round 83 G. Autocompletion

Problem - G - Codeforces

問題概要

$k$ 個の相異なる英小文字列からなる集合 $S$ がある。この集合の要素 $s$ それぞれについて以下を求めよ。

文字列を空文字列から始めて、以下の2つの操作を好きな順番で繰り返してと一致させるための最小コストを求めよ。
- 操作1： $t$ の末尾に好きな文字を1つ加える。操作コストは1。
- 操作2：文字列を「補完」する。 $S$ の要素のうち $t$ を接頭辞に持つものを辞書順に並べ、その中から好きな文字列を選んで $t$ をそれに変化させる。この文字列が辞書順で $i$ 番目（1-indexed）だった場合、操作コストは $i$ 。

入力/制約

入力は根と $n$ 個の頂点からなる trie（トライ木）の形式で与えられ、根は文字を持たず、他の $n$ 個の頂点は英小文字を1つずつ持つ。このtrie中で指定された $k$ 個の頂点に対応する文字列が $S$ の要素である。

$1 \le k \le n \le 10^{6}$

解法

実際の問題ページには入力の与えられ方がつらつらと書かれていますが、これはtrieの構造そのものです。trieと言っても今回の問題で要求される操作は普通の木とほぼ同じで、各頂点の子をアルファベット順でソートできるようにしておけば十分です。

入力例1に対応するtrieは以下のようになります。 $S$ の要素に対応する頂点を赤で示しています。

f:id:betrue12:20200310191658p:plain

この問題で可能な操作は、スタート地点を根として以下のように表現できます。

1コストをかけて1段降りる。
今いる頂点以下の部分木に属する赤頂点にワープする。このとき、部分木の中だけを見てその赤頂点が辞書順で何番目かに応じてコストがかかる。

$S$ に属するものに限らず全ての頂点 $i$ について「根からその頂点まで最小コストいくつで到達できるか」という値を考え、これを $dp\lbrack i \rbrack$ とします。根 $0$ については $dp\lbrack 0 \rbrack$ として、各頂点（文字列）を辞書順に辿るDFSで上から順に値を求めていきます。

頂点 $i$ へのたどり着き方には以下の2通りが考えられます。

直接の親からコスト1で降りてくる。直接の親を $p$ として、 $dp\lbrack i \rbrack = dp\lbrack p \rbrack + 1$ 。
頂点 $i$ が $S$ に属している場合に限り、祖先である頂点のうちどれかから補完で飛んでくる。その祖先を $a$ 、補完操作のコストを $c(a, i)$ として、 $dp\lbrack i \rbrack = \min_{a}(dp\lbrack a \rbrack + c(a, i))$ 。

この補完操作のコスト $c(a, i)$ をもう少し分解します。

頂点 $i$ が示す文字列が、 $S$ 全体の中で辞書順 $x_{i}$ 番目だとします。また、頂点 $a$ に入る前に既に「通り過ぎた」 $S$ の要素の個数を $y_{a}$ とします。このとき補完操作のコストは $c(a, i) = x_{i} - y_{a}$ となります。

f:id:betrue12:20200310192647p:plain

これを用いると補完で飛んでくる場合のDPの遷移は、

$\displaystyle dp\lbrack i \rbrack = \min_{a}(dp\lbrack a \rbrack + c(a, i)) = x_{i} - \max_{a}(y_{a} - dp\lbrack a \rbrack)$

となります。この $y_{a} - dp\lbrack a \rbrack$ は、「 $a$ までの移動コストを $dp\lbrack a \rbrack$ かける代わりに補完コストを $y_{a}$ 減らすことができた」という値であり、この値を全ての祖先について持っておいて最大値を取れば補完で飛んでくる場合の $dp\lbrack i \rbrack$ の値が計算できます。これは multiset 等で管理しておき、DFSで頂点を降りたり登ったりするたびに値を出し入れすれば良いです。