Codeforces Round #556 B. Three Religions

お題箱より。

Problem - B - Codeforces

問題概要

英小文字からなる長さ $n$ の文字列 $S$ が与えられる。また文字列 $T_{1}, T_{2}, T_{3}$ があり、これらは最初は空である。

以下のクエリが合計で $q$ 個与えられる。

1 i c 文字列 $T_{i}$ の末尾に文字 $c$ を足す。
2 i 文字列 $T_{i}$ の末尾の文字を取り去る。

各クエリに対して、そのクエリを処理した後の $T_{1}, T_{2}, T_{3}$ に対する以下の問いに答えよ。

$S$ の文字を色1、色2、色3、無色に塗り分け、色 $i$ に塗られた文字を順に読むと $T_{i}$ に一致するようにできるか？

制約

$1 \le n \le 100000$
$1 \le q \le 1000$
文字列 $S$ および1クエリで与えられる文字は全て英小文字である
空文字列に対して2クエリが与えられることはない
全ての時点で $T_{1}, T_{2}, T_{3}$ はいずれも250文字を超えない

解法

問題1回の解き方を考える

まずはクエリのことを忘れて、1回問題を解くことを考えましょう。

文字列を左から見ていくことで、例えばこんなDPが考えられます。

$dp\lbrack i \rbrack\lbrack a \rbrack\lbrack b \rbrack\lbrack c \rbrack =$ 文字列 $S$ の最初の $i$ 文字目まで見たときに、 $T_{1}, T_{2}, T_{3}$ のそれぞれ $a, b, c$ 文字目までが塗られているようにできるか？（true/false）

これでは状態数が多いですね。ここで「できる/できない」などのブール値を値とするDPは、その添字のうちの1つを値にしてしまうことで状態数を削減できる可能性があります。例えば、

$dp\lbrack a \rbrack\lbrack b \rbrack\lbrack c \rbrack =$ $T_{1}, T_{2}, T_{3}$ のそれぞれ $a, b, c$ 文字目までが塗られているようにするためには、最小で文字列 $S$ の最初の $i$ 文字目までを見ればよいか？（ただし、不可能な場合はINFとする）
$dp\lbrack i \rbrack\lbrack a \rbrack\lbrack b \rbrack =$ 文字列 $S$ の最初の $i$ 文字目まで見て、 $T_{1}, T_{2}$ はそれぞれ $a, b$ 文字目まで塗られているときに、 $T_{3}$ は最大で何文字まで塗られているようにできるか？

のような変形が考えられます。このように添字の1つを「最小の○○」「最大の○○」のように値のほうに持ってくることで状態数を削減できます。今回の場合は $a, b, c$ の値がそれぞれ250以下であることから、上のほうを採用したいです。

あとはちゃんと遷移を計算できるようにします。例えば $dp\lbrack a \rbrack\lbrack b \rbrack\lbrack c \rbrack = x$ のとき、 $dp\lbrack a+1 \rbrack\lbrack b \rbrack\lbrack c \rbrack$ は何になるでしょうか？それは「 $T_{1}$ の $a+1$ 文字目と同じ文字が、 $S$ の $x$ 文字目より後ろで一番近くにあるところ」となります。

これは事前に「 $S$ の $i$ 文字目より後ろで、文字 $k$ が一番近くにあるのはどこか？」という情報を全ての $(i, k)$ に対して計算しておけばすぐに求められます。これは後ろから見ていくことで全て求められて、文字は26種類なので十分間に合います。

$T_{1}, T_{2}, T_{3}$ の長さをそれぞれ $A, B, C$ として、 $dp\lbrack A \rbrack\lbrack B \rbrack\lbrack C \rbrack$ がINFでなければ答えはYesです。ということで、判定を1回するだけなら解けそうです。

クエリへの対応を考える

クエリのたびにさっきのDPをやり直していては間に合いません。クエリでは $T_{1}, T_{2}, T_{3}$ どれかの末尾が1文字増減するだけなので、ほとんどの結果は使い回せるはずです。

クエリが来る前の $T_{1}, T_{2}, T_{3}$ の長さをそれぞれ $A, B, C$ としましょう。そして、この時点で $dp\lbrack a \rbrack\lbrack b \rbrack\lbrack c \rbrack$ の値が $0 \le a \le A, 0 \le b \le B, 0 \le c \le C$ に対して既に求まっているとしましょう。ここにクエリが来た時の処理を考えます。

クエリ2の場合

文字を削除するクエリの場合は簡単です。例えば 2 1 というクエリが来ると $T_{1}$ の長さは $A-1$ になります。このとき $dp\lbrack A-1 \rbrack\lbrack B \rbrack\lbrack C \rbrack$ の結果はそのまま使うことができます。この値がINFでなければYesです。