Codeforces Global Round 18 : F. LEGOndary Grandmaster

土壇場で盛り返せた回。
https://codeforces.com/contest/1615/problem/F

問題

01で構成された数列が2つある。
ただし、いずれも一部値は未確定である。

隣接する0同士または1同士を、合わせて反転させることを考える。
2つの数列のスコアは、前者を後者に一致させるための最小反転回数とする。
ただし、どうやっても一致させられない場合はスコアは0とする。

未確定の値が0,1それぞれを取る全組み合わせにおける総スコアを求めよ。

解法

初期状態で、奇数番目のindexの01を反転しておく。
そうすると、0/1を2つセットで反転させる処理は、0/1のswapとみなすことができる。

とすると、スコアはswapを繰り返して1の位置を合わせる最小回数となる。
あとは、両文字列を先頭から見て行って、どちらが1を多く先行しているか状態を持ち、組み合わせとスコアの総和をもってDPしていくとよい。

int T,N;
string A,B;
const ll mo=1000000007;

ll pat[2020][2020][2];
ll sum[2020][2020][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>N>>A>>B;
		FOR(i,N) if(i%2) {
			if(A[i]=='1'||A[i]=='0') A[i]='0'+'1'-A[i];
			if(B[i]=='1'||B[i]=='0') B[i]='0'+'1'-B[i];
		}
		
		FOR(x,N+2) FOR(y,N+2) pat[x][y][0]=pat[x][y][1]=sum[x][y][0]=sum[x][y][1]=0;
		
		pat[0][0][0]=1;
		int t;
		for(i=1;i<=N;i++) {
			FOR(t,2) {
				if(A[i-1]==t+'0'||A[i-1]=='?') {
					(pat[i-1][i][t]+=pat[i-1][i-1][0]+pat[i-1][i-1][1])%=mo;
					(sum[i-1][i][t]+=sum[i-1][i-1][0]+sum[i-1][i-1][1])%=mo;
				}
			}
			
			FOR(t,2) if(B[i-1]==t+'0'||B[i-1]=='?') {
				// same
				for(j=i;j<=N;j++) {
					(pat[i][j][t]+=pat[i-1][j][t])%=mo;
					(sum[i][j][t]+=sum[i-1][j][t])%=mo;
				}
				// diff
				ll s=0,ss=0;
				for(j=i;j<=N;j++) {
					(ss+=s)%=mo;
					if(A[j-1]==t+'0'||A[j-1]=='?') {
						(pat[i][j][t^1]+=s)%=mo;
						(sum[i][j][t^1]+=ss)%=mo;
						if(A[j-1]!='?') s=ss=0;
					}
					(ss+=sum[i-1][j][t^1]+(j-i)*pat[i-1][j][t^1])%=mo;
					(s+=pat[i-1][j][t^1])%=mo;
				}
			}
			
		}
		cout<<(sum[N][N][0]+sum[N][N][1])%mo<<endl;
		
		
	}
}

まとめ

どうにか解けてよかった。