Codeforces Global Round 26 : F. Reconstruction

こういう考察物苦手。
https://codeforces.com/contest/1984/problem/F

問題

N要素の整数列Aがあり、それぞれ-M～Mの範囲の値を取る。
しかしAは明には与えられない。

N文字の文字列Sと、N要素の整数列Bが与えられる。

• S[i]が'P'の時、B[i]はAの先頭i要素の和である
• S[i]が'S'の時、B[i]はAの末尾N-i要素の和である

Sは一部'?'になってる場合がある。
これをPやSに当てはめたとき、Bに対して、Aが条件を満たす構成になるようなものは何通りか。

解法

SとBに要素を加え、先頭にB[0]=0、S[0]='P'かつB[N+1]=0、S[N+1]=0としておく。
すると、Sのどこかで"PS"の並びが登場し、そこからAの総和がわかる。

Aの総和ごとに、条件を満たす文字の埋め方があるかを考える。
文字の並びがPP,PS,SP,SSのどれかによって、端から順に-M～Mの範囲に収められるかが確定させていける。

int T,N;
ll M,B[2020];
const ll mo=998244353;
string S;
ll dp[2020][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>S;
		S="P"+S+"S";
		FOR(i,N) cin>>B[i+1];
		B[0]=B[N+1]=0;
		N+=2;
		
		ll ret=0;
		set<ll> sum;
		FOR(i,N-1) sum.insert(B[i]+B[i+1]);
		FORR(s,sum) {
			FOR(i,N) dp[i][0]=dp[i][1]=-1;
			dp[0][0]=1;
			for(i=1;i<N;i++) {
				int CP=(S[i]!='S'),CS=(S[i]!='P');
				
				//PP,SS;
				if(abs(B[i]-B[i-1])<=M) {
					if(dp[i-1][0]!=-1&&CP) (dp[i][0]=dp[i-1][0])%=mo;
					if(dp[i-1][1]!=-1&&CS) (dp[i][1]=dp[i-1][1])%=mo;
				}
				// PS
				if(dp[i-1][0]!=-1&&CS&&B[i]+B[i-1]==s) {
					if(dp[i][1]==-1) dp[i][1]=0;
					(dp[i][1]+=dp[i-1][0])%=mo;
				}
				// SP
				if(dp[i-1][1]!=-1&&CP&&(abs(B[i]+B[i-1]-s)+1)/2<=M) {
					if(dp[i][0]==-1) dp[i][0]=0;
					(dp[i][0]+=dp[i-1][1])%=mo;
				}
			}
			if(dp[N-1][1]>=0) ret+=dp[N-1][1];
		}
		cout<<ret%mo<<endl;
	}
}

まとめ

うーん、難しい。