Codeforces ECR #106 : E. Chaotic Merge

最終問以外は割とすんなり解いてるな。
https://codeforces.com/contest/1499/problem/E

問題

文字列x,yから、以下の手順で文字列zを作ることを考える。

• xとyのいずれか空でない方を選び、先頭の文字を取り除いてzの末尾につける、ということをx,yがともに空になるまで繰り返す。

こうして作るzがchaoticであるとは、隣接する文字が互いに異なることを示す。

文字列S,Tが与えられる。
Sの部分文字列全パターンと、Tの部分文字列全パターンの対に対し、その2つから作る文字列がchaoticとなるような文字列の選び順の総和を求めよ。

解法

f(a,b,x,y,t) := 以下の条件を満たす文字列の選び方

• Sのprefix a文字目、Tのprefix b文字目まで考えた
• x,yは、それぞれzにS,Tから1文字以上抽出済みかの真偽値を示す
• tは、zの末尾はSから来たかTから来たかの2値を示す

上記値を丁寧に足しこんでいこう。
S,Tは部分文字列も考えるので、適宜f(a,b,false,false,*)をインクリメントしたり、f(a,b,true,true,*)を解に計上していこう。

int A,B;
string S,T;
ll dp[1010][1010][2][2][2];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	A=S.size();
	B=T.size();
	ll ret=0;
	FOR(x,A+1) FOR(y,B+1) {
		dp[x][y][0][0][0]++;
		FOR(i,2) FOR(j,2) FOR(k,2) {
			ll v=dp[x][y][i][j][k];
			if(v==0) continue;
			if(i==0&&j==0) {
				if(x<A) (dp[x+1][y][1][0][0]+=v)%=mo;
				if(y<B) (dp[x][y+1][0][1][1]+=v)%=mo;
			}
			else if(k==0) {
				if(x<A&&S[x-1]!=S[x]) (dp[x+1][y][i|1][j][0]+=v)%=mo;
				if(y<B&&S[x-1]!=T[y]) (dp[x][y+1][i][j|1][1]+=v)%=mo;
			}
			else {
				if(x<A&&T[y-1]!=S[x]) (dp[x+1][y][i|1][j][0]+=v)%=mo;
				if(y<B&&T[y-1]!=T[y]) (dp[x][y+1][i][j|1][1]+=v)%=mo;
			}
		}
		ret+=dp[x][y][1][1][0]+dp[x][y][1][1][1];
	}
	cout<<ret%mo<<endl;
}

まとめ

思いついてしまえば実装は軽め。