Codeforces Round #358 (Div. 2) D. Alyona and Strings

お題箱より。

Problem - D - Codeforces

問題概要

文字列 $s, t$ が与えられ、それぞれの長さは $n, m$ である。また整数 $K$ が与えられる。

以下の条件を満たすような $K$ 個の文字列の組 $(p_{1}, ..., p_{K})$ の、長さの総和の最大値を求めよ。

$p_{1}, ..., p_{K}$ のどの文字列も空でない。
$s, t$ のどちらにも、 $p_{1}, ..., p_{K}$ がこの順番に重なることなく連続部分文字列として出現する。

制約

$1 \le n, m \le 1000$
$1 \le K \le 10$
$s, t$ は英小文字からなる
問題の条件を満たす $(p_{1}, ..., p_{K})$ が存在することが保証されている

※添字に $k$ を使いたいので入力の $K$ を大文字にしました。

解法

※文字列のインデックスは先頭を0文字目とする0-indexedで扱います。

この問題は最長共通部分列（LCS）の応用です。LCSとは2つの文字列 $s, t$ に対して、「 $s, t$ のどちらの（連続とは限らない）部分列にもなっているような文字列のうち、最長のもの（の長さ）」を求めたものです。

これはそれぞれの文字列の長さを $n, m$ として $O(nm)$ のDPで求めることができます。具体的には、

$dp\lbrack i \rbrack\lbrack j\rbrack =$ 文字列 $s$ の $i-1$ 文字目までと文字列 $t$ の $j-1$ 文字目までを見終わったときの、そこまでの共通部分列の長さの最大値

と定義して、以下の3パターンの遷移を考えます。

の文字目を採用せずに無視する
- $dp\lbrack i+1 \rbrack\lbrack j\rbrack \leftarrow dp\lbrack i \rbrack\lbrack j\rbrack$
の文字目を採用せずに無視する
- $dp\lbrack i \rbrack\lbrack j+1\rbrack \leftarrow dp\lbrack i \rbrack\lbrack j\rbrack$
の文字目との文字目が等しい場合、これを共通部分列に採用する
- $dp\lbrack i+1 \rbrack\lbrack j+1\rbrack \leftarrow dp\lbrack i \rbrack\lbrack j\rbrack + 1$

今回の問題の条件は部分列に求められる条件が少し厳しくなっていて、 $K$ 個の連続部分文字列として抜き出す必要があります。

$K$ の値が小さいことに注目して、DPの添字として「これまで連続部分列を何個使ったか」の添字 $k$ を加えましょう。この $k$ は新しい連続部分列を始める時に1増やすことにします（終わるときでも良いです）。

DPの中での $k$ の増え方は以下のように考えられます。

文字を1つも採用していない時、あるいはいったん「採用せずに無視する」遷移によって途切れた後に新しい連続部分列を始めると、必ず $k$ が1増える。
文字を採用した直後の遷移でまた文字を採用する場合は、前の連続部分列にくっつける（ $k$ が増えない）か、新しい連続部分列を始める（ $k$ が1増える）かを選ぶことができる。

これらを区別するためには、「最後に見たところの文字を採用したか」のフラグがあれば良いです。

つまり、最終的にDPの状態は以下のように定義すると上手くいきます。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack\lbrack l \rbrack$ ：文字列 $s$ の $i-1$ 文字目までと $t$ の $j-1$ 文字目までを見て、これまでに連続部分列を $k$ 個使っていて、最後に見たところの文字を採用した $(l=1)$ /採用していない $(l=0)$ 時の、長さ合計の最大値

遷移も通常のLCSのDPを以下のように応用すれば良いです。

遷移後の $l$ の値を、文字を採用せずに無視する遷移では $l=0$ 、文字を採用する遷移では $l=1$ とする。
$l=0$ の状態から $l=1$ の状態に遷移する時には $k$ を1増やす。
$l=1$ の状態から $l=1$ の状態に遷移する時には、 $k$ を1増やす場合と増やさない場合の2つの遷移を行う。

最終的には $dp\lbrack n\rbrack\lbrack m\rbrack\lbrack K\rbrack\lbrack 0\rbrack$ と $dp\lbrack n\rbrack\lbrack m\rbrack\lbrack K\rbrack\lbrack 1\rbrack$ のうち大きいほうが答えになります。