AtCoder Beginner Contest 261 G問題メモ

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$ の時は実装を分けなければならないのが難しさに拍車を掛ける。

DPの発想

変換元が必ず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を定義する。

$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

深い多次元配列が必要になるDPは、PythonはもちろんPyPyもちょっと速度的に不安で、 Numpy形式で表現できてなお速いNumbaを使いたくなる。

Numbaで実装したとき、DPの各値はそこまで大きくならないことが分かっているので、 64bitは不要で、32bit型などで実装したかったが、（その方が計算時間改善になるし） int64とint32の混在によるコンパイルエラーになってしまった。

DPの値を配列の添え字に使うと強制的に64bitとして扱われる？
よくわからないが、まぁ、とりあえず型は全て64bit型にしていた方が無難そう。。。

import os
import sys
from heapq import heapify, heappop, heappush

import numpy as np


def solve(s, t, KK, ccc, lll, aaa):
    n = t.size

    CHAR_TYPES = 26
    MAX_CONV_LEN = lll.max()

    INF = 1 << 29
    dp1 = np.full((n, n + 1, CHAR_TYPES), INF, np.int64)
    dp2 = np.full((n, n + 1, KK, MAX_CONV_LEN + 1), INF, np.int64)

    # 長さが変わらない変換のリンクを作っておく
    int_list = [KK]
    int_list.clear()
    one_char_links = [int_list.copy() for _ in range(CHAR_TYPES)]
    for i in range(KK):
        if lll[i] > 1:
            continue
        one_char_links[aaa[i, 0]].append(ccc[i])

    def dijkstra(q):
        heapify(q)
        distances = np.full(CHAR_TYPES, INF, np.int64)
        for cost, u in q:
            distances[u] = cost
        while q:
            cost, u = heappop(q)
            if distances[u] < cost:
                continue
            for v in one_char_links[u]:
                new_cost = cost + 1
                if distances[v] > new_cost:
                    distances[v] = new_cost
                    heappush(q, (new_cost, v))
        return distances

    # 長さが1の区間はややこしいので個別に作成
    for i in range(n):
        dist = dijkstra([(0, t[i])])
        for c in range(CHAR_TYPES):
            dp1[i, i + 1, c] = dist[c]
        for k in range(KK):
            dp2[i, i + 1, k, 1] = dist[aaa[k, 0]]

    for w in range(2, n + 1):
        for i in range(n - w + 1):
            j = i + w
            more_than_2_distances = np.full(CHAR_TYPES, INF, np.int64)
            for k in range(KK):
                for l in range(2, lll[k] + 1):
                    tmp = INF
                    for m in range(i + 1, j):
                        tmp = min(tmp, dp2[i, m, k, l - 1] + dp1[m, j, aaa[k, l - 1]])
                    dp2[i, j, k, l] = tmp
                if lll[k] > 1:
                    more_than_2_distances[ccc[k]] = min(more_than_2_distances[ccc[k]], dp2[i, j, k, lll[k]] + 1)

            q = []
            for c in range(CHAR_TYPES):
                if more_than_2_distances[c] < INF:
                    q.append((more_than_2_distances[c], c))
            if q:
                dist = dijkstra(q)
                for c in range(CHAR_TYPES):
                    dp1[i, j, c] = dist[c]
                for k in range(KK):
                    dp2[i, j, k, 1] = dist[aaa[k, 0]]

    dp = np.full((s.size, n + 1), INF, np.int64)
    for j in range(1, n + 1):
        dp[0, j] = dp1[0, j, s[0]]
    for p in range(1, s.size):
        c = s[p]
        for j in range(p + 1, n + 1):
            tmp = INF
            for i in range(p, j):
                tmp = min(tmp, dp[p - 1, i] + dp1[i, j, c])
            dp[p, j] = tmp

    if dp[-1, -1] == INF:
        return -1
    else:
        return dp[-1, -1]


SIGNATURE = '(i8[:],i8[:],i8,i8[:],i8[:],i8[:,:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

s = input()
t = input()
k = int(input())
INF = 1 << 60
ord_a = ord('a')

ccc = np.zeros(k, np.int64)
lll = np.zeros(k, np.int64)
aaa = np.full((k, 51), -1, np.int64)
for i in range(k):
    c, a = input().split()
    ccc[i] = ord(c) - ord_a
    lll[i] = len(a)
    for j, b in enumerate(a):
        aaa[i, j] = ord(b) - ord_a

s = np.fromiter(map(ord, s), dtype=np.int64) - ord_a
t = np.fromiter(map(ord, t), dtype=np.int64) - ord_a
ans = solve(s, t, k, ccc, lll, aaa)
print(ans)

目次

AtCoder Beginner Contest 261 G問題メモ

G - Replace

問題

解法

DPの発想

具体的なDP

初期値

遷移