yukicoder : No.2040 010-1 Deletion

これ系の問題、コードは簡単なんだけど気付くのに手間取るんだよな。
https://yukicoder.me/problems/no/2040

問題

01?で構成されるN文字の文字列Sが与えられる。
?に0か1を埋めたとき、ここから以下を任意に繰り返してSを空文字にできるのは何通りか。

• Sから"1"を取り除いて間を詰める。
• Sから"010"を取り除いて間を詰める。

解法

Sを空文字にできる条件は以下の通り。

• 0は偶数個である。
• 0の数が2M個とすると、0が連続する区間が(M+1)個以上ある。逆に0と0の間に1があるケースがM個未満である。

これを踏まえてDPしていく。
直前が0かどうかと、0と0の間に1があるケースとないケースの差を状態として持つとよい。

int N;
string S;
ll from[5050][2][2];
ll to[5050][2][2];

const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	from[2500][0][0]=1;
	FORR(c,S) {
		ZERO(to);
		FOR(x,5000) FOR(y,2) FOR(k,2) if(from[x][y][k]){ //dif, odd/even, prev
			if(c=='0'||c=='?') {
				(to[x+(k?0:2)-1][y^1][1]+=from[x][y][k])%=mo;
			}
			if(c=='1'||c=='?') {
				(to[x][y][0]+=from[x][y][k])%=mo;
			}
			
		}
		
		swap(from,to);
	}
	ll ret=0;
	if(count(ALL(S),'0')==0) ret++;
	for(x=2502;x<=5000;x++) ret+=from[x][0][0]+from[x][0][1];
	cout<<ret%mo<<endl;
}

まとめ

こういうのどうやると得意になるんだろうな。