ARC201C - Prefix Covering

問題

リンク

解法

与えられた文字列をTrie木に載せていくことを考える。$X$が良い集合であることは、Trie木上で以下が成り立っていることと同値である。

• $X$に含まれる文字列の終点を黒色で塗ったとき、Trie木上で黒色でない頂点のみを辿って葉にたどり着くようなパスが存在しない。

このような塗り方をすべて求めれば良い。そのような塗り方を「いい塗り方」と呼ぶことにする。

---

$K$が固定の場合を考える。$\text{dp}_i :=i$を根とする部分木が良い塗り方であるような塗り方の総数、とする¹。また、簡単のためすべての頂点は子を持たないか、ちょうど2つの子を持つかのいずれかであるとする²。

まず葉は、その頂点で終了するような文字列が存在するならば$1$で、そうでないならば$0$となる。ある部分木について、

• $\text{dp}_A$をA側の部分木
• $\text{dp}_B$をB側の部分木
• 終点ノードの集合を$T$
• $C_i$を自身を除いた部分木に含まれる終点ノードの数 として

$$\text{dp}_i = \text{dp}_A \times \text{dp}_B + \begin{cases} {2}^{C_i} & \text{if } i \in T \\ 0 & \text{otherwise} \end{cases}$$

で計算できる。気持ちとしては、+の左側が「頂点$i$を塗らなかった場合にその部分木が良い集合となる」場合の数、右側は(頂点$i$を塗った場合にはその部分木は良い部分木となるので)他の頂点を塗る塗り方の場合の数を計算している。

---

ここで、$K$が動的に変わる場合を考える。ある文字列をTrie木に追加したとき、変化しうる値はA側の部分木とB側の部分木のどちらか一方と、追加した文字列のパス上に存在する$C_i$の値である。これは各頂点に$\text{dp}_A, \text{dp}_B, C_i$をメモしておくことで差分計算が可能となる。

以上から、この値を載せておくことで全体で$O(\sum |S|)$となる。

Footnotes

1. これを思いつくにはどうする的な話題に関しては「こういう問題がこういう解き方ができるよね」という積み重ねなのかなぁという気持ちになります。 ↩

2. こうしておくと実装が楽 ↩