ひらめの日常

プログラミングと読書と

ABC130-E Common Subsequence (500)

Common Subsequence

問題はこちら

atcoder.jp

この問題は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

参考

betrue12.hateblo.jp

qiita.com