Codeforces ECR #056 : F. Vasya and Array

これ系のDP苦手。
https://codeforces.com/contest/1093/problem/F

問題

1～Kの値を取るN要素の数列Aが与えられる。
ただし一部の要素は空である。

各空要素に1～Kの任意の値を入れるとき、同じ数字がL個以上連続しないようなAは何通りあるか。

解法

基本的には以下を組み合わせていく。
S(i) := 先頭i要素目までで条件を満たす組み合わせ
f(i,k) := 先頭i要素目までのうち、i要素目がkであるような要素の組み合わせ

まず以下を考えよう。「L個連続しない」の条件を無視すると以下のようになる。

• A[i]=kまたはA[i]が任意のとき、f(i,k) = S(i-1)
• A[i]!=kのとき、f(i,k) = 0
• S(i) = sum(f(i,*))

ここから「L個連続する」ケースを取り除こう。
仮にA[i-L]～A[i]が同じ要素kを取りえるとする。
その場合、f(i,k)のうちf(i-L,k)分はA[i-L]～A[i-1]がすでにL文字一致してることにより得られた値と言える。
よってその場合f(i,k)とS(i)からf(i-L,k)を引こう。

最終的にS(N)が解。

int N,K,L;
int A;
ll S[101010];
ll pat[101010][101];
ll sub[101010][101];
int ML[101010][101];

ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>L;
	if(L==1) return _P("0\n");
	
	S[0]=1;
	FOR(i,N) {
		cin>>A;
		
		for(x=1;x<=K;x++) if(A==x || A==-1) {
			pat[i+1][x]=S[i]+(mo-sub[i][x])%mo;
			ML[i+1][x]=min(L-1,ML[i][x]+1);
			
			if(ML[i+1][x]==L-1) sub[i+1][x]=(S[i+1-(L-1)]+mo-pat[i+1-(L-1)][x])%mo;
			(S[i+1]+=pat[i+1][x])%=mo;
		}
	}
	cout<<S[N]<<endl;
	
}

まとめ

TDPCでも似たような問題あった気がするが、身についてないな…。