yukicoder : No.2378 Cards and Subsequences

典型テクの詰め合わせといえば詰め合わせ。
https://yukicoder.me/problems/no/2378

問題

M種類のカードが計N枚並んでおり、入力でその順が与えられる。
各種類のカードは、表裏に整数が書かれている。

カード列の部分列を全パターン考える。
ただし、部分列を抽出した場所が異なっても、得られるカード列が同じものは同じ列とみなす。
各パターンについて、各カード両面のどちらを表にするか選択できるとする。

部分列全パターン及びカードの表裏の選択全パターンのうち、表を向いたカードの整数値の総和がKとなるのは何通りか。

解法

先頭から順にカードを部分列に入れるか入れないか判断していくことを考える。
i番目のカードが選ばれるのは、直前の同じ種類のカードがj番目にある場合、直前に選んだカードxはj≦x＜iを満たしていればよい。

よって
d(x,s) := 最後に選んだカードがx番目で、そこまでの表面の整数の総和がsとなる組み合わせ
とすると、i番目のカードの表面にA[i]、裏面にB[i]が書かれているとして

と状態遷移すればよい。

int N,M,K;
int S[2020],A[2020],B[2020];
const ll mo=998244353;

ll dp[2020][2020];
ll dpS[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) {
		cin>>S[i];
		S[i]--;
	}
	FOR(i,M) cin>>A[i];
	FOR(i,M) cin>>B[i];
	
	dp[0][0]=1;
	dpS[0][0]=1;
	int pre[2020]={};
	for(i=1;i<=N;i++) {
		x=pre[S[i-1]];
		pre[S[i-1]]=i;
		
		FOR(j,K) {
			ll a=dpS[i-1][j];
			if(x) a+=mo-dpS[x-1][j];
			if(j+A[S[i-1]]<=K) (dp[i][j+A[S[i-1]]]+=a)%=mo;
			if(j+B[S[i-1]]<=K) (dp[i][j+B[S[i-1]]]+=a)%=mo;
		}
		
		FOR(j,K+1) dpS[i][j]=(dpS[i-1][j]+dp[i][j])%mo;
	}
	cout<<dpS[N][K]<<endl;
}	

まとめ

本番参加が遅れたため時間内に間に合わず…。