yukicoder No.1029 JJOOII 3

お題箱より。

解法

計算量などの表記のため、 $L = \max |S_{i}|$ と置きます。この問題の制約では $L \le 80$ です。

作りたいレベル $K$ のJOI文字列を $T$ と表記します。文字列のインデックスは0-indexedで表記します。

$T$ を前から順に作っていく、以下のようなDPを考えます。

$dp\lbrack i \rbrack =$ 文字列 $T$ のうち先頭の $i$ 文字（つまり $0, 1, ..., i-1$ 文字目）を作るのに必要な最小コスト

$T$ の文字数が $3K$ なので、 $dp\lbrack 3K\rbrack$ が答えです。

$dp\lbrack i \rbrack$ からの遷移として、次に購入する文字列 $S_{i}$ を全て試すことにします。このときの遷移先、すなわち $S_{i}$ を購入することで $T$ をどこまで進められるかを計算したいです。そのためには $S_{i}$ の文字を順に見ていきながら、 $T$ の続きの文字と一致すればその文字を採用して $T$ を1文字進める、ということを繰り返せば良いです。

1つの $dp\lbrack i \rbrack$ からの遷移で各 $S_{i}$ の全ての文字を見ることになるので、このDPを回すと全体計算量 $O(KNL)$ で答えを求められます。ちょっと心もとないですね。もう少し高速化しましょう。

実際には文字列 $T$ は、ほとんどの箇所で同じ文字が続きます。 $dp\lbrack i \rbrack$ からの遷移を考える時、例えば $T$ の $i$ 文字目から $i+L$ 文字目まで全部 J であったとします。このとき $S_{i}$ を1回購入することで J ゾーンから脱出することはできないので、単に「各 $S_{i}$ に含まれる J の個数」ぶんだけ進むことになり、 $S_{i}$ を1文字ずつ見なくても一発で遷移先が計算できます。O や I についても同様です。

ほとんどのインデックスではこのような遷移計算が可能であり、1つの $dp\lbrack i \rbrack$ からの遷移が $O(N)$ で計算できます。そしてこのような遷移計算ができないところ、つまり $T$ のインデックスのうち $L$ 文字先までの間に異なる文字が存在するところは高々 $O(L)$ 箇所です。これら2つの遷移を使い分けることで全体計算量は $O(KN + L^{2}N)$ となり、間に合います。