AtCoder Beginner Contest 344, D : String Bags

問題文

　https://atcoder.jp/contests/abc344/tasks/abc344_d

問題概要

　文字列の列が $n$ 個与えられる．$i$ ($1 \leq i \leq n$) 番目の列は $S_i = \langle S_{ i, 1 }, S_{ i, 2 }, \dots, S_{ i, A_i } \rangle$ である．
　ここで，次の処理を行う．

1. 変数 $S$ を用意し，$S \leftarrow \epsilon$ とする*1．
2. $i = 1, 2, \dots, n$ について，順に次の処理を行う．
   1. 次の 2 つの内，いずれかを行う．
      1. 次の処理を行う．
         1. 整数 $j$ ($1 \leq j \leq A_i$) を選ぶ．
         2. $S \leftarrow S + S_{ i, j }$ とする．
      2. 何もしない．

　操作終了後の $S$ を与えられる文字列 $T$ に一致させるとき，$S$ に代入する操作の回数の最小値はいくらか？　不可能な場合はそのことを報告せよ．

制約

• $1 \leq n, |T| \leq 100$
• $1 \leq A_i, | S_{ i, j } | \leq 10$

解法

　$S$ に連結する文字列の選び方の総数は，最悪ケースで $\Theta( ( \max A )^n )$ 通りもあるため，全探索を行うことはできません．より高速な方法を考える必要があります．
　よりよい手法を目指すためにまず重要なこととして，目標を達成するためには操作の過程（終了時を含む）で $S$ は常に $T$ の接頭辞になっていなければならないということがあります．このことを踏まえて操作の過程を見てみます．
　今，$i$ 番目までの文字列列まで扱い方（どれを連結するか or 何もしないか）を決め終わっていて，$|S| = j$ になっているとします．ここで，もし $i, j$ が等しくなる状態が複数あったとしても，その後で起こることが全く同じなので，どれかひとつのみを試せばよいことになります．$i, j$ が等しい状態を「まとめる」気持ちになると，次のように状態をとる動的計画法を考えることができます：
\begin{align*}
\mathit{ dp }[i][j] :=& \, \text{$i$ 番目の文字列列まで見て，} \\
& \, \text{$T$ の先頭 $j$ 文字まで一致させるために連結する文字列の最小個数}
\end{align*}
初期化は以下のようになります：
\begin{equation*}
\mathit{ dp }[i][j] = \begin{cases}
0 & \text{($i = 0 \land j = 0$)} \\
\infty & \text{(otherwise)}
\end{cases}
\end{equation*}
いわゆる「配る DP」で状態遷移を書くと，各状態からの遷移は次のようになります：
\begin{align*}
\mathit{ dp }[ i + 1 ][ j + |S_{ i, k }| ] &\overset{ \mathrm{ chmin } }{ \leftarrow } \mathit{ dp }[i][j] + 1 & \text{(for $k$ s.t. $T[ j, j + |S_{ i, k }| ) | = S_{ i, k }$)} \\
\mathit{ dp }[ i + 1 ][j] &\overset{ \mathrm{ chmin } }{ \leftarrow } \mathit{ dp }[i][j]
\end{align*}
更新が終わったあと，$\mathit{ dp }[n][ |T| ]$ に答えが求まっています．
　計算量についてですが，上記の DP は状態数が $\Theta( n |T| )$ 個あります．それぞれの状態について，$O( \max A )$ 個の文字列についてのループが回り，各文字列については $O( \max | S_{ i, k } | )$ 時間かけて部分文字列の一致判定を行っています．文字列を連結しない方の遷移は $O( 1 )$ 時間です．まとめると，この DP は $O( n |T| ( \max A ) ( \max | S_{ i, k } | )$ 時間で走ります．

コード

constexpr auto INF = LIM<>::max() / 2;

int main()
{
	IN( string, T );
	IN( int, N );
	auto SS = make_vector< string >( N, 0, "" );
	REP( i, N )
	{
		IN( int, A );
		SS[i].resize( A );
		cin >> SS[i];
	}

	const int L = SZ( T );

	static int dp[ 128 ][ 128 ];
	// dp[ # of cosidered elems ][ # of matched characters ] := min cost
	fill( AALL( dp ), INF );
	dp[0][0] = 0;

	REP( i, N )
	{
		REP( j, L + 1 )
		{
			FOR( s, SS[i] )
			{
				if ( T.substr( j, SZ( s ) ) == s )
				{
					chmin( dp[ i + 1 ][ j + SZ( s ) ], dp[i][j] + 1 );
				}
				chmin( dp[ i + 1 ][j], dp[i][j] );
			}
		}
	}

	const int res = dp[N][L];
	cout << ( res == INF ? -1 : res ) << endl;

	return 0;
}

*1:ここで，$\epsilon$ は空文字列を表す．