ABC 261 G — Replace

考察

一文字を置き換えて生じた文字は、その後も順序を保ち、目標文字列の連続した一部分になる。そこで、途中の文字列全体を追う代わりに「一文字から目標のどの区間を作るか」を考える。短い区間を組み合わせて長い区間を作り、一文字同士の置換による循環だけを最短路で処理する。

操作列から導出木へ

文字列そのものを状態として幅優先探索すると、長さを目標以下に制限しても、途中に現れる文字列の種類が多すぎる。一方、各文字がどの文字から生じたかを追うと、置換を木として表せる。根は元の一文字で、規則を一回使うたびに、その文字の子として右辺の文字を左から並べる。この木を導出木と呼び、最終的な文字列は葉を左から読んだものになる。

右辺は空でないので、どの子も少なくとも一文字の葉を持つ。従って、一つの節点から生じる葉は目標の非空な連続区間を占め、兄弟の区間は交わらず左から並ぶ。別々の子への操作は干渉せず、必要な費用を足せる。

以降、N=∣T∣N=|T|、M=∣S∣M=|S| とし、文字列の添字は1始まり、T[l..r]T[l..r] は両端を含む区間とする。状態を

D[l][r][c]=文字 c から T[l..r] を作る最小費用D[l][r][c] =\text{文字 }c\text{ から }T[l..r]\text{ を作る最小費用}

と定める。到達不能は ∞\infty とする。ここで固定するのは、根の文字 cc に最初に適用する規則である。

  • 何もしないなら、l=rl=r かつ Tl=cT_l=c のときだけ費用0。
  • 最初の規則の右辺が二文字以上なら、各文字に非空区間を割り当てるため、子が担当する区間はすべて元の区間より短い。
  • 最初の規則が一文字への置換 c→dc\to d なら、候補は 1+D[l][r][d]1+D[l][r][d]。区間長が変わらず、c→d→cc\to d\to c のような循環もあり得る。

つまり、区間長の昇順だけでは最後の種類を処理できない。同長の依存だけを分離し、短区間から得た候補を出発点として解く。

多文字右辺を分割する補助DP

規則 Ck→AkC_k\to A_k の右辺の長さを ak=∣Ak∣a_k=|A_k| とする。右辺が長いとき、全分割を直接列挙するのは高価なので、先頭から一文字ずつ連結する補助状態

Fk[h][l][r]=右辺の先頭 h 文字から T[l..r] を作る最小費用F_k[h][l][r] =\text{右辺の先頭 }h\text{ 文字から }T[l..r]\text{ を作る最小費用}

を持つ。これは右辺の文字からの費用であり、規則 Ck→AkC_k\to A_k 自体の費用1は含めない。

h≥2h\geq 2 では、右辺の hh 文字目が担当する末尾区間の直前を mm として、

Fk[h][l][r]=min⁡l≤m<r(Fk[h−1][l][m]+D[m+1][r][Ak,h])F_k[h][l][r] =\min_{l\leq m<r} \left(F_k[h-1][l][m]+D[m+1][r][A_{k,h}]\right)

と計算する。左右はともに真に短い区間なので、区間長の昇順なら既に確定している。h>r−l+1h>r-l+1 なら、各文字に一文字以上を割り当てられず値は ∞\infty である。h=1h=1 の値は D[l][r][Ak,1]D[l][r][A_{k,1}] そのものだが、同じ区間の DD が確定するまで設定を待つ。

各区間で候補・単項閉包・補助基底の順に確定する

一文字への規則を単項規則と呼ぶ。区間 [l,r][l,r] ごとに、次の三段階を行う。

  1. 一致基底と多文字右辺の候補を作る。 上式で h≥2h\geq 2 の FkF_k を計算する。各文字 cc の暫定費用 bcb_c は、すべて ∞\infty から始め、一致する一文字区間なら0、Ck=cC_k=c かつ ak≥2a_k\geq 2 の規則があれば 1+Fk[ak][l][r]1+F_k[a_k][l][r] で最小化する。
  2. 単項規則の閉包を取る。 26文字を頂点とし、規則 c→dc\to d に対して逆向きの辺 d→cd\to c を費用1で張る。有限な bcb_c を持つ全頂点を、その値を初期距離として Dijkstra 法に入れる。最短距離を D[l][r][c]D[l][r][c] とする。
  3. 一文字分の補助状態を確定する。 すべての規則について Fk[1][l][r]=D[l][r][Ak,1]F_k[1][l][r]=D[l][r][A_{k,1}] と置く。これが、より長い区間で補助DPを使うための基底になる。

逆向きに張る理由は、dd から区間を作る費用が分かれば、その前に c→dc\to d を一回付け足し、cc からの費用を更新できるからである。初期距離 bcb_c は文字ごとに異なるため、単位辺でも通常の多点始点BFSではなく Dijkstra 法で小さい費用から確定する。全初期距離が ∞\infty なら、その区間はどの文字からも作れない。

独自の小例として、S=aS=\texttt{a}、T=bcT=\texttt{bc}、規則を a→d\texttt{a}\to\texttt{d}、d→bc\texttt{d}\to\texttt{bc} とする。一文字区間の一致基底から、[1,2][1,2] では

Fk[2][1][2]=D[1][1][b]+D[2][2][c]=0F_k[2][1][2] =D[1][1][\texttt{b}]+D[2][2][\texttt{c}]=0

となる(kk は後者の規則)。まず bd=1b_{\texttt{d}}=1 が得られ、逆向き辺 d→a\texttt{d}\to\texttt{a} に沿って D[1][2][a]=2D[1][2][\texttt{a}]=2 が確定する。実際の操作順は a→d→bc\texttt{a}\to\texttt{d}\to\texttt{bc} であり、費用を伝える順序とは逆になる。

開始文字列の各文字を連結する

最後に、SS の各文字が担当する区間を左から決める。G[i][r]G[i][r] を「SS の先頭 ii 文字から TT の先頭 rr 文字を作る最小費用」とし、G[0][0]=0G[0][0]=0、それ以外は ∞\infty で初期化する。i=1,…,Mi=1,\ldots,M の順に、r≥ir\geq i について

G[i][r]=min⁡i−1≤m<r(G[i−1][m]+D[m+1][r][Si])G[i][r] =\min_{i-1\leq m<r} \left(G[i-1][m]+D[m+1][r][S_i]\right)

と計算する。ここでは元からある SS の文字を連結するだけなので、規則を使う費用1は加えない。答えは G[M][N]G[M][N] であり、∞\infty なら −1-1 を出力する。

典型の発動条件

文字列導出の区間 DP(CYK型)

発動条件: 元の各記号が目標文字列の連続区間を生成し、生成列の連結順序が保存されるとき。

記号と目標区間を状態にし、規則右辺の各記号へ区間を非空分割して費用を合成する。区間の分割に文法規則を当てはめる、CYK型の構文解析DPである。

一文字規則の最短路閉包

発動条件: 同じサイズの DP 状態間を単項規則が循環させる一方、他の規則候補は既に計算済みのとき。

単項規則の逆向きに費用1の辺を張り、一致基底・多文字規則の既知候補を初期距離として、多点始点Dijkstraを行う。

問題固有の要素

右辺が空でないことが、各子への非空分割と、二文字以上の右辺による依存区間の短縮を保証する。削除規則を許す別問題では、子が空文字列を作れるため、この計算順をそのまま使えない。

別の問題へ持ち帰る視点: 再帰規則を「状態サイズを厳密に減らすもの」と「同サイズの依存を作るもの」に分ける。後者だけを別のアルゴリズムで解けば、DP全体の計算順を組み立てられる。

正当性

任意の導出木で、根の文字に最初に適用する規則を固定する。多文字規則なら、各子の葉は目標区間の左からの非空分割をなし、すべて真に短い区間となる。短区間の最小費用が確定していれば、補助DPは全分割を調べ、その規則から始まる最小費用を求める。逆に、分割した各区間の導出を根の規則につなげれば、その費用の導出を実現できる。

導出木の根から単項規則をたどると、有限な導出では、無操作で一致する葉か、最初の多文字規則に行き着く。この到達先の費用が第一段階の候補であり、その前の単項規則列を逆向きにたどった費用が第二段階の経路長に対応する。従って、一致基底・多文字候補の作成後に逆向きグラフを多点始点Dijkstraで閉じれば、その区間の全導出の最小費用が求まる。単項循環があっても費用は正なので、循環を繰り返して最小費用を下げることはない。

第三段階で一文字分の補助値を確定することで、次の長さの区間に必要な短区間の値がそろう。以上より、区間長の帰納法で全状態が正しい。開始文字列の各文字の葉も左からの非空分割をなすため、最後の連結DPはすべての導出を覆い、各部分の導出を実際に結合できる。有限な候補がない場合に限って到達不能となる。

実装上の注意

  • 一致基底は無操作なので費用0。公式解説の本文にはここを1とする箇所があるが、掲載コードは0で初期化しており、問題条件とも0が整合する。S=TS=T なら、すべての元文字を無操作のまま使って答えは0になる。
  • 区間長の短い順に、h≥2h\geq 2 の補助DPと一致基底・多文字候補、単項閉包、h=1h=1 の補助値の順で処理する。単項規則を多文字規則と同じ一回の走査だけで処理すると、規則の入力順に依存して伝播を取りこぼす。
  • 26頂点だけなので、Dijkstraは未確定頂点の最小距離を毎回全走査で選んでもよい。最小値が ∞\infty になったら終了する。
  • ∞\infty を表す番兵値を使うなら、到達不能な項を加算候補から外す。FF には規則自体の費用を含めず、bcb_c を作るときだけ1を足す。最後の GG には足さない。

復習の核

  • 文字列全体の状態数が多いとき、各元文字の子孫が占める区間と、子孫同士の順序保存に注目する。
  • 導出木で根に最初に使う規則を固定すると、独立な子の問題へ分けられる。DPの計算順は、実際の操作順と一致するとは限らない。
  • 同サイズの依存を分離したら、何を既知の初期費用にし、どちら向きに最適値を伝えるかを式から決める。

計算量と制約

時間

B=max⁡k∣Ak∣B=\max_k|A_k| とする。補助DPは O(KBN2)O(KBN^2) 状態で各状態の分割点を O(N)O(N) 個調べるため、O(KBN3)O(KBN^3) 時間。単項規則グラフの構築は一度だけで O(K+26)O(K+26) 時間かかる。

各区間のDijkstraを頂点の全走査で実装すると、最小頂点の選択に O(262)O(26^2)、辺の緩和に O(K)O(K) 時間を使う。最後の連結DPは O(MN2)O(MN^2) 時間なので、全体は

O ⁣(KBN3+(262+K)N2+MN2)O\!\left(KBN^3+(26^2+K)N^2+MN^2\right)

となる。単項規則は相異なる文字対に限られ、高々 26⋅2526\cdot25 本である。従って、単項閉包をさらに粗く O(263)O(26^3) と押さえた

O(KBN3+263N2+MN2)O(KBN^3+26^3N^2+MN^2)

も上界として正しい。26326^3 はここでは余裕を持たせた評価であり、各区間で三重ループの全点対最短路を実行するという意味ではない。

空間

DD が O(26N2)O(26N^2)、全規則の補助DPが O(KBN2)O(KBN^2)、最後の GG が O(MN)O(MN)。入力と単項グラフも含め、全体は O((26+KB)N2)O((26+KB)N^2)。

制約との対応

公式制約は 1≤M≤N≤501\leq M\leq N\leq50、1≤K≤501\leq K\leq50、1≤∣Ak∣≤501\leq |A_k|\leq50。すべて英小文字で、右辺は空でなく、Ck≠AkC_k\neq A_k、規則の組は相異なる。時間制限は2秒、メモリ制限は1024 MiBである。

支配的な補助DPの粗い上界は 505=312,500,00050^5=312{,}500{,}000。実際には非空区間だけを扱い、2≤h≤min⁡(ak,r−l+1)2\leq h\leq\min(a_k,r-l+1)、l+h−2≤m<rl+h-2\leq m<r に絞れば、前半の h−1h-1 文字に足りない区間を調べずに済む。右辺が目標より長い規則も候補にならない。こうした範囲に絞ったループで、公式解説と同じ規模の計算に収める。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Replace の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間合成・領域分割DP

主題
  • 区間合成・領域分割DP: 区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。
追加で学ぶ技能
    なし
    既習技能
    • 最短路モデル: 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。

    主タグ: 区間合成・領域分割DP

    補助タグ: 最短路モデル

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 区間合成・領域分割DP

    • 区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。

    先に読む単元:

    • 最小十分状態からDPを設計する — 初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。
    • 最短路モデル — 基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題