AtCoder Beginner Contest 261 G問題メモ

AtCoder Beginner Contest 261

G - Replace

• 英小文字からなる2つの文字列 $S,T$ と、$K$ 個の変換ルール（文字 $C_i$→文字列 $A_i$）が与えられる
  • $|C_i|=1$
• 変換を繰り返して $S$ を $T$ にできるか判定し、可能なら最小変換回数を求めよ
• $1 \le |S| \le |T| \le 50$
• $1 \le K \le 50$
• $1 \le |A_i| \le 50$

発想としては素直な、だが考察量と実装の重い多重DP。
さらに $|A_i|=1$ の時は実装を分けなければならないのが難しさに拍車を掛ける。

変換元が必ず1文字なので、 「$S$ の $h$ 文字目が、$T$ の中での $i$ 文字目から $j$ 文字目に変化した」という境界がはっきりしている。
（変換元が2文字以上だったら、境界をハッキリ分けられない）

S: ab
T: cbcabc

変換ルール  a→cc
            b→ac
            c→bc
↓
S |a   |b  |   Tのうち cbc は Sの a から、
  |cc  |ac |           abc は     b から変換された
T |cbc |abc|                      という境界が明確にある

よってDPで「$S$ の先頭何文字が、$T$ の先頭何文字に変換されたか」を順次求めていけそう。

• $DP_{Main}[h,j]=S$ の先頭 $h$ 文字目までを $T$ の先頭 $j$ 文字目までに変換するコスト

ただし、これを求めるには、たとえば以下の情報が必要となる。

• $DP_1[i,j,c]=$ 文字 $c$ から、$T$ の $i～j$ 文字目に変換するためのコスト（無理ならINF）

$DP_1$ が存在する前提で、$DP_{Main}[h,j]$ の求め方は、

       h   j
S:  abcd..
T:  efghijkl..

$S$ で着目中の最後の文字 $S_h$（上例で'd'）が、$T$ のどの部分に変換されたか？
「$m～j$ 文字目に変換された」という $m$ を全て調べ、コスト最小のものを取れば求まる。

• $DP_{Main}[h,j] = \min_{m}(DP_{Main}[h-1, m-1] + DP_1[m,j,S_h])$

m=6 とした場合の例
S:  abc   | d        DP_Main[h-1, m-1] ... 'abc' を 'efghi' に変換するするコスト
T:  efghi | jkl      DP1[m,j,Sh]       ... 'd' を 'jkl' に変換するコスト

これでDPを埋めていき、$DP_{Main}[|S|,|T|]$ が答えとなる。

だが、$DP_1$ は直接求めるのが難しい。
変換ルールの各 $C_k$ から変換できる部分を変換していく、ということを繰り返すと、 可能な文字列が爆発的に増え、しかもどれが最終的に $T$ の部分文字列になるかの判別が難しい。

そこで、補助として「変換先 $A_k$ のそれぞれに対しても、$DP_{Main}$ と同じようなDPを作り、変換コストを求める」という方針をとる。
こうすれば、$T$ の部分文字列だけを考慮すれば良くなる。

$A_k$ を $T[i:j]$ に変換するコストが分かれば、$C_k→T[i:j]$ の変換コストは それ+1 である。
（本当は $|A_k|=1$ の変換があるせいでそうとも限らないのがややこしいのだが、ひとまず大まかな方針としては）

以下のDPを定義する。

• $DP_1[i,j,c]=$ 文字 $c$ から $T[i:j]$ に変換するためのコスト（無理ならINF）
• $DP_2[i,j,k,l]=A_k$ の先頭 $l$ 文字までから $T[i:j]$ に変換するコスト（無理ならINF）

$T[i:j]$ は $T$ の $[i,j)$ の範囲を指すものとする。

長さ1の区間に関しては先に埋めてしまえる。

• $DP_1[i,i+1,T_i]=0$
  • $T[i:i+1]=T_i$ であり、$T_i$ を $T_i$ に変換するコストは当然0なので

また、$T_i$ 以外の文字からの変換に関しては、長さが1（$|A_k|=1$）の変換を繰り返してできる可能性がある。

アルファベットの各文字を頂点として、 $|A_k|=1$ であるような $k$ に限定して、$A_k→C_k$ と、本来の変換とは逆向きに辺（コスト1）を張ったグラフを考えることで、 $T_i$ を始点としたDijkstraにより、各文字から $T_i$ にする最小コストが分かる。
（目的地が決まっていて、各出発地からそこに到達するコストを求めるイメージなので、逆辺になる）

• $DP_1[i,i+1,c]=$(Dijkstraの結果における $c$ から出発したときのコスト)

$DP_2$ は、$A_k$ の最初の1文字と、先ほど求めた $DP_1$ からわかる。
変換によって文字が減ることはないので、$T[i:j]$ が1文字ならば変換元も1文字しかあり得ないため、 $l \ge 2$ を考える必要は無い。（不可能でありINF確定）

• $DP_2[i,i+1,k,1]=DP_1[i,i+1,A_k[0]]$

いま、$DP_1[i,j,c]$ と $DP_2[i,j,k,l]$ を求めるとする。
この時、$j-i$ より短い区間の $DP_1,DP_2$ は全て求まっているとする。
また、長さ1の区間は既に埋めたので、$j-i \ge 2$ とする。

$DP_2$ に関しては、「DPの発想」の項で述べた $DP_{Main}$ の考え方と同様、 最後の1文字がどの範囲までに変換されるかを全探索することで、求められる。

• $DP_2[i,j,k,l] \xleftarrow{\min} \min_{m} DP_2[i,m,k,l-1]+DP_1[m,j,A_k[l]]$
  • ※$l \ge 2$

ただしこれが可能なのは $l \ge 2$ までであって、 $l=1$ の時は、$DP_1[m,j,A_k[l]]$ がまさに今から求めようとしている $DP_1[i,j,c]$ の $c=A_k[l]$ のときに相当するので、 まだ求まっておらず、別の方法をとらなければならない。

• ここまでで求まっている情報を整理
  • $DP_1[i,j,c]$ はまだ何も求まっていない
  • $DP_2[i,j,k,l]$ は、$l \ge 2$ のみ、求まっている
    • つまり $|A_k| \ge 2$ なら、文字 $C_k$ から $A_k$ を経由して $T[i:j]$ にするコストはほぼ求まりかけている

1つの文字 $c$ を $T[i:j]$（※長さは2以上）に変換するには、主に2つのルートがある。

• ①$c$ から直接2文字以上に変換する
  • $C_x=c,|A_x| \ge 2$ である変換ルールがあれば可能
  • コストは「$A_x$ を $T[i:j]$ にするコスト $+ 1 = DP_2[i,j,x,|A_x|]+1$」
  • 条件を満たす $x$ が複数あれば、それぞれを調べた上でのmin

• ②$c$ から1文字の変換を経由して2文字以上に変換する
  • 1文字変換で適当な文字（$d$ とする）にして、そこから上記と同様、$C_x=d$ である変換ルールを利用
  • どこかで1文字から2文字以上にする変換（つまり①の方法）を行わねばならない
  • ($c→d$ にするために1文字変換を繰り返した回数) + ($d$ からの①の方法によるコスト) がコストとなる

• どちらもできないなら $c$ から $T[i:j]$ へは不可能

注意すべきは、①が可能であっても、②の方が安くなることがあること。

Dijkstraで実装する。
まずは①によって $T[i:j]$ への変換が可能な (文字 $c$, ①の方法によるコスト $v$) を列挙する。
そこから、区間の長さが1の時にも行った、逆辺を張ったグラフでのDijkstraにより、各文字からの最短コストが求まる。
多始点Dijkstraとは少し違うが、似たような感じで、初期のキューに列挙した $(c,v)$ を入れた状態から開始すればよい。

Dijkstraの結果に従って $DP_1[i,j,c]$ と $DP_2[i,j,k,1]$ を埋めれば、$DP_1,DP_2$ とも、$(i,j)$ における全てが埋まった。

後はこれを繰り返して $DP_1$ を完成させ、それを元に $DP_{Main}$ を実行すれば、答えとなる。

Python3