【競プロ】1日1AC : EDPC F問題【動的計画法】

今日もEducational DP Contestです。問題はこちら。

Longest Common Subsequenceを略してLCSと呼ばれる問題です。結構難しい問題なので頑張りましょう。

また、記事の作成にあたって『Educational DP Contest の F ～ J 問題の解説と類題集』を参考にさせていただきました。大変勉強になりました。ありがとうございます。

1 考え方
- 1.1 少し簡単にした問題から
- 1.2 LCSの１つを求める
2 終わりに

考え方

少し簡単にした問題から

この問題ではLCSの一つを求めることになっていますが、まずはその「長さ」だけを求めてみましょう。

文字列 \(s\) の先頭から \(i\) 文字分、文字列 \(t\) の先頭から \(j\) 文字分を、それぞれ文字列 \(SP_i,TP_j\) とします。
そして、\(dp^j_i\) を「\(SP_i,TP_j\)のLCSの長さ」とします。\(dp^{j+1}_{i+1}\) は \(dp^j_i\) を考えている状態に対して、 \(SP_i,TP_j\) の末尾に１文字ずつ追加した時のLCSの長さです。追加した文字、\(s_i,t_j\) （これらは \(s,t\) の \(i+1,j+1\) 文字目であることに注意）が等しいか、そうでないかで事情が変わります。

\(\ s_i=t_j\) （\(s\) の \(i+1\) 文字目と \(t\) の \(j+1\) 文字目が等しい）の時

これは単純で、LCSの長さが１伸びます。すなわち、\(dp^{j+1}_{i+1}=dp^j_i+1\)

\(\ s_i\neq t_j\) の時

\(i,j\) が小さい方からループを回すことを考えているので、\(dp^{j+1}_{i+1}\) を考える時点では

\[dp^0_0,dp^1_0,\cdots,dp^{|t|}_{0}\]

\[\vdots\]

\[dp^0_i,dp^1_i,\cdots,dp^{|t|}_i\]

\[dp^{0}_{i+1},dp^1_{i+1},\cdots,dp^{j}_{i+1}\]

は既知の値として扱えることを確認してください。

今の場合、「\(SP_i+s_i\)と\(TP_j\)」と「\(SP_i\)と\(TP_j+t_j\)」のLCSの長さが \(dp^{j+1}_{i+1}\) の候補になることがイメージできますか。
すなわち、

\[dp^{j+1}_{i+1}=\max \{ dp^{j+1}_i,dp^j_{i+1}\}\]

が成り立ちます。（先に言いましたが、この時 \(dp^{j+1}_i,dp^j_{i+1}\) は既知の値として扱えます。）

念のためここまでをまとめると

\[
dp^{j+1}_{i+1}=\begin{cases}
dp^j_i+1 & (s_i=t_j)\\
\max \{ dp^{j+1}_i,dp^j_{i+1}\} & (s_i\neq t_j)
\end{cases}
\]

となるわけです。これは以下のように実装できます。

#include <bits/stdc++.h>
using namespace std;

int LEN_MAX = 3000;
vector<vector<int>> dp(LEN_MAX + 1,vector<int>(LEN_MAX + 1,0));
string s,t;

int main(){
    cin >> s >> t;
    int slen = s.size(), tlen = t.size();

    for(int i = 0;i < slen;i++){
        for(int j = 0;j < tlen;j++){
            if(s[i] == t[i])
                dp[i+1][j+1] = dp[i][j] + 1;
            else
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
        }
    }
}

\(dp^{|t|}_{|s|}\) が文字列 \(s,t\) のLCSの長さになっています。

LCSの１つを求める

\(s=\) "axyb", \(t=\) "abyxb" の時のDPテーブルは以下の通りです。

これを頼りにLCSを求められないか考えましょう。

図には赤矢印がいくつかありますね。これは \(dp^{j-1}_{i-1} \rightarrow dp^{j}_{i}\) の遷移をするところで、LCSには \(s_{i}\ (=t_i)\) が含まれることになります。

一番右下のマス（この例では \( (i,j)=(4,5) \)）から遷移を逆に辿ることで答えを得られそうですね。その方法を考えます。

あるマスについて、上か下のマス（以下では隣のマスと言います）と値が等しければ、そのマスから遷移してきたと考えられます。隣のマスと値が異なるならば、それは斜めから遷移してきたものです。

\(dp^j_i\) の値をもとに遷移を逆に辿れることが分かったので実装しましょう。なお、複数の辿り方が考えられますが、それは答えが複数あるということなので１つの辿り方ができれば十分です。

#include <bits/stdc++.h>
using namespace std;

int LEN_MAX = 3000;
vector<vector<int>> dp(LEN_MAX + 1,vector<int>(LEN_MAX + 1,0));
string s,t;

int main(){
    cin >> s >> t;
    int slen = s.size(), tlen = t.size();

    for(int i = 0;i < slen;i++){
        for(int j = 0;j < tlen;j++){
            if(s[i] == t[j])
                dp[i+1][j+1] = dp[i][j] + 1;
            else
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
        }
    }

    string ans = "";
    int i = slen, j = tlen;
    while(i > 0 && j > 0){
        // 上に辿る
        if(dp[i][j] == dp[i][j-1])
            j--;
        // 左に辿る
        else if(dp[i][j] == dp[i-1][j])
            i--;
        // 斜めにたどる
        else{
            ans = s[i-1] + ans;
            i--; j--;
        }
    }
    cout << ans << endl;
}