yukicoder : No.2106 Wild Cacco

わかってしまえばすぐ。
https://yukicoder.me/problems/no/2106

問題

"("")"".""?"で構成される文字列Sが与えられる。
S中の"."を"("")""?"いずれかに置き換えたとき、以下を満たすものは何通りか。

• "?"を開き括弧か閉じ括弧にすると、Sが正しい括弧列になる

解法

"?"は、途中まで開き括弧、それ以降閉じ括弧にするのが良い。
括弧列に関する典型的なDPとして、開き括弧が何個余分にあるかを保持しながらDPするケースがあるが、そこに1つ状態を加え、"?"を開き括弧にするか閉じ括弧にするかを持つようにしてDPしていこう。
"?"を開き括弧にすることから閉じ括弧に遷移することはできるが、逆はできない。

const ll mo=998244353;
ll from[2020][2];
ll to[2020][2];
int N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	from[0][0]=1;
	FORR(c,S) {
		ZERO(to);
		if(c=='('||c=='.') {
			FOR(i,2001) {
				to[i+1][0]+=from[i][0];
				to[i+1][1]+=from[i][1];
			}
		}
		if(c==')'||c=='.') {
			FOR(i,2001) {
				to[i][0]+=from[i+1][0];
				to[i][1]+=from[i+1][1];
			}
		}
		if(c=='?'||c=='.') {
			FOR(i,2001) {
				to[i+1][0]+=from[i][0];
				to[i][1]+=(from[i+1][0]+from[i+1][1]);
			}
		}
		FOR(i,2001) FOR(j,2) from[i][j]=to[i][j]%mo;
	}
	cout<<(from[0][0]+from[0][1])%mo<<endl;
}

まとめ

ワイルドカードを2段階置換する問題は珍しいかも。