AtCoder: ABC130-E Common Subsequence (500)

Common Subsequence

問題はこちら

この問題はLCS(Longest common subsequence)と関わりが深いのでまずはそれから書いてみる。

LCS

最長の共通部分列の長さを求めてくださいというのが典型的な問題。次のような例を考えてみる。

s: abcd
t: acfed

$s_i = t_j (= x)$ の時、これまでの共通部分列の末尾にそれぞれ $x$ を加えることで長さが+1された共通部分列を新しく作ることができる。例でみると、 $s_i = d, t_j = d$ の時、今までのLCSは "ac" なので、"acd" を作ることでより長いものを作ることができる。

よって、常にLCSを持ちながら遷移するdpを実装することで答えを求めることができる。遷移は次の通り。

$dp[i + 1][j + 1]$ : $s_i$ までと $t_j$ までの中のLCS
$s_i = t_j$ の時: $dp[i + 1][j + 1] = dp[i][j] + 1$
それ以外: $dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])$

今回の問題

それぞれちょうど $s_i$ と $t_j$ で終わるものの共通部分列の数を数えてみる。

$s_i = t_j (= x)$ の時、これまでに存在していた全ての共通部分列に対して、末尾にそれぞれ $x$ を加えることで、新しい共通部分列を作ることができる。つまり、これまでに存在していた全ての共通部分列（= $s _ {i-1}$ までと $t _ {j - 1}$ までに存在する全ての共通部分列）の数だけ増える。さらに、 $x$ 一文字のみのものも増えるので、これに+1されることになる。

遷移テーブルのイメージは次のようになる。水色の部分を例とすると、"abc" までと "abcfe" までの共通部分列の数は水色で囲われた部分の和になっている。なので、 "abcd" までと "abcfed" までの共通部分列の数は水色で囲われた部分 + d自身のみの場合である。

f:id:thescript1210:20190618181932j:plain:w300 — 遷移テーブル

$sum[i + 1][j + 1]$ : $s_i$ までと $t_j$ までの共通部分列の個数の二次元累積和。
$dp[i + 1][j + 1]$ : $s_i$ までで ちょうど $s_i$ で終わるもの と、 $t_j$ までで ちょうど $t_j$ で終わるもの の共通部分列の数。
$s_i = t_j$ の時: $dp[i + 1][j + 1] = sum[i][j] + 1$
それ以外: $dp[i + 1][j + 1] = 0$
累積和の更新: $sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + dp[i + 1][j + 1]$

解答

抜粋部分

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
const ll mod = 1e9 + 7;

int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll> s(n), t(m);
    rep(i, n) cin >> s[i];
    rep(i, m) cin >> t[i];

    vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, 0));
    vector<vector<ll>> sum(n + 1, vector<ll>(m + 1, 0));
    rep(i, n) {
        rep(j, m) {
            if (s[i] == t[j]) {
                dp[i + 1][j + 1] = sum[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = 0;
            }
            dp[i + 1][j + 1] %= mod;
            sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] + dp[i + 1][j + 1];
            sum[i + 1][j + 1] %= mod;
            sum[i + 1][j + 1] = (sum[i + 1][j + 1] + mod - sum[i][j]) % mod;
        }
    }

    ll ans = 1;
    rep(i, n + 1) rep(j, m + 1) ans += dp[i][j], ans %= mod;
    cout << ans << endl;
    return 0;
}

Submission #6008512 - AtCoder Beginner Contest 130

参考

僕は、dp[i][j]をs[i]とt[j]を同時に採用すると増える場合の数とおき if (s[i] != t[j]) dp[i][j] = 0 else (s[i-1]までとt[j-1]までで作れる数列は後ろにs[i](=t[j])をつけて新たな共通数列に出来るため)dp[i][j] = dp[i-1][j-1]までの総和として総和の部分を二次元累積和を使い高速化しました
— harady (@harady_a_human) 2019年6月17日

betrue12.hateblo.jp

qiita.com

ひらめの日常

日常のメモをつらつらと

AtCoder: ABC130-E Common Subsequence (500)

Common Subsequence

LCS

今回の問題

解答

参考