Codeforces #850 : Div1 E. Infinite Game

E問題の割には難易度ひかえめ？
https://codeforces.com/contest/1785/problem/E

問題

2人で対戦ゲームを行う。
互いにラウンドを戦い、2ラウンド先に勝った方がゲーム全体の価値となる。

文字列Sが与えられる。
この文字列は各ラウンドで先手後手どちらが勝ったかを与えられるが、一部のラウンドの勝者は未確定である。
未確定の勝者をそれぞれ確定させた場合、Sを無限回繰り返したラウンドの構成を考えたとき、先手のゲームの勝率の期待値が0.5未満・0.5ちょうど・0.5以上となる組み合わせはそれぞれ何通りか。

解法

Sを1回回す前の状態で、両者何ラウンド勝利した状態で、Sを1周回すと両者の勝利回数がどうなるか、また遷移後の両者のラウンドの勝利回数に対し、DPで状態遷移数を求められる。
Sを繰り返したとき、ラウンド勝利回数がループ状態に入ったとき、勝利回数の差がプラスマイナス0のどうなるかをそれぞれ数え上げよう。

string S;
int N;
const ll mo=998244353;

ll ret[3];
int from[16][4][4][4][4][802];
int to[16][4][4][4][4][802];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	int a,b,c,d,mask;
	FOR(i,16) {
		from[i][0][1][2][3][400]=1;
	}
	FOR(i,N) {
		ZERO(to);
		FOR(mask,16) FOR(a,4) FOR(b,4) FOR(c,4) FOR(d,4) {
			FOR(x,802) if(from[mask][a][b][c][d][x]) {
				if(S[i]=='a'||S[i]=='?') {
					int y=x;
					if((a&1)&&((mask>>0)&1)) y++;
					if((b&1)&&((mask>>1)&1)) y++;
					if((c&1)&&((mask>>2)&1)) y++;
					if((d&1)&&((mask>>3)&1)) y++;
					int a2=(a&1)?0:(a|1);
					int b2=(b&1)?0:(b|1);
					int c2=(c&1)?0:(c|1);
					int d2=(d&1)?0:(d|1);
					(to[mask][a2][b2][c2][d2][y]+=from[mask][a][b][c][d][x])%=mo;
				}
				if(S[i]=='b'||S[i]=='?') {
					int y=x;
					if((a&2)&&((mask>>0)&1)) y--;
					if((b&2)&&((mask>>1)&1)) y--;
					if((c&2)&&((mask>>2)&1)) y--;
					if((d&2)&&((mask>>3)&1)) y--;
					int a2=(a&2)?0:(a|2);
					int b2=(b&2)?0:(b|2);
					int c2=(c&2)?0:(c|2);
					int d2=(d&2)?0:(d|2);
					(to[mask][a2][b2][c2][d2][y]+=from[mask][a][b][c][d][x])%=mo;
				}
			}
		}
		swap(from,to);
	}
	
	FOR(a,4) FOR(b,4) FOR(c,4) FOR(d,4) {
		int T[4]={a,b,c,d};
		vector<int> R={0};
		FOR(i,7) R.push_back(T[R.back()]);
		reverse(ALL(R));
		mask=1<<R[0];
		for(i=1;i<5;i++) {
			if(R[i]==R[0]) break;
			mask|=1<<R[i];
		}
		FOR(i,801) {
			if(i>400) (ret[0]+=from[mask][a][b][c][d][i])%=mo;
			if(i==400) (ret[1]+=from[mask][a][b][c][d][i])%=mo;
			if(i<400) (ret[2]+=from[mask][a][b][c][d][i])%=mo;
		}
	}
	
	FOR(i,3) cout<<ret[i]%mo<<endl;
		
	
}

まとめ

とはいえ本番でさっと思いつかない。