ABC130 E - Common Subsequence (500)

概要

長さNの整数列Sと長さTの整数列Mが与えられる。Sの部分列とTの部分列のなかで共通するものはいくつあるか。(mod 10^9+7 して出力)

制約

1 ≦ N, M ≦ 2 * 10^3

方針

DP。

S = {1, 3, 2}, T = {1, 2, 3, 3, 2, 3}のケースを考える。このとき該当する部分列は16個。

引き算したあとはMODを足すのを忘れない。（これで結構WAがでる）

考え方①

次のようなDPを構成することを考える。
dp[i][j] = Sのi文字目、Tのj文字目まで使った時の共通部分列の個数　とする。このとき、求めるDP配列は下記のようになる。

	1	2	3	3	2	3
1	1	1	1	1	1	1
3	1	1	3	5	5	7
2	1	3	5	7	13	15

下記の点が重要。

• S[i] = T[j]のとき、これまで作った部分列(dp[i-1][j-1])についてそれら全ての後ろにS[i]を追加したものと、S[i]自身が新たに共通部分列となる。
• S[i] != T[j] であっても、1つ上の文字のdp[i-1][j-1]とdp[i-1][j]に差分があれば、それはdp[i][j]にも反映させたい。

解答①

Submission #6004402 - AtCoder Beginner Contest 130

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll MOD = 1e9+7;
 
	ll N, M;
	cin >> N >> M;
 
	vector<ll> S(N);
	rep(i, N) cin >> S[i];
 
	vector<ll> T(M);
	rep(i, M) cin >> T[i];
 
	vector<vector<ll>> dp(N+1, vector<ll>(M+1, 0));
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			dp[i+1][j+1] += dp[i+1][j];
			dp[i+1][j+1] %= MOD;
			dp[i+1][j+1] += dp[i][j+1] - dp[i][j] + MOD;
			dp[i+1][j+1] %= MOD;
			if(S[i] == T[j]){
				dp[i+1][j+1] += dp[i][j] + 1;
				dp[i+1][j+1] %= MOD;
			}
 
		}
	}
 
	cout << dp[N][M] + 1 << endl;
}

考え方②

①と近しいが、下記のDPを考えてもよい。
dp[i][j] = Sのi文字目、Tのj文字目を使ったときに新たに発生する共通部分列の個数
このときdp[i][j]のすべての和+1が解答になる。
方針のサンプルだとDP配列は下記の通り。

	1	2	3	3	2	3
1	1	0	0	0	0	0
3	0	0	2	2	0	2
2	0	2	0	0	6	0

dpの2次元累積和配列をsmとし、dpとsmを同時に更新してゆく。
dp[i][j]はS[i] = T[j]のとき sm[i-1][j-1] + 1、そうでないとき0
sm[i][j]は2次元累積和の足し方より、
sm[i][j] = sm[i-1][j] + sm[i][j-1] - sm[i-1][j-1] + dp[i][j]

解答

Submission #6004397 - AtCoder Beginner Contest 130

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll MOD = 1e9+7;
 
	ll N, M;
	cin >> N >> M;
 
	vector<ll> S(N);
	rep(i, N) cin >> S[i];
 
	vector<ll> T(M);
	rep(i, M) cin >> T[i];
 
	vector<vector<ll>> dp(N+1, vector<ll>(M+1, 0));
	vector<vector<ll>> sm(N+1, vector<ll>(M+1, 0));
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(S[i] == T[j]){
				dp[i+1][j+1] += sm[i][j]+1;
				dp[i+1][j+1] %= MOD;
			}
 
			sm[i+1][j+1] = sm[i][j+1] + sm[i+1][j] - sm[i][j] + dp[i+1][j+1] + MOD;
			sm[i+1][j+1] %= MOD;
		}
	}
 
	cout << (sm[N][M] + 1) % MOD << endl;
}