yukicoder : No.2031 Colored Brackets

これは典型か。
https://yukicoder.me/problems/no/2031

問題

N文字の括弧列が与えられる。
各文字を赤青に塗り分け、同色の文字を集めた2つの括弧列を作る方法は2^N通りある。
この両方が正しい括弧列となるような塗り分け方は何通りか。

解法

以下をDPで埋めて行けばよい。
f(n,r) := n文字目までの塗り分けを決めたとき、赤青いずれもprefixにおいて閉じ括弧が開き括弧よりも多くなるケースがなく、かつ赤い括弧列では開き括弧がr個多いような組み合わせ

nとrが定まれば、青い括弧列で開き括弧が何個多いかわかるので、それぞれ次に閉じ括弧を連結可能かがわかる。

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	from[0]=1;
	int sum=0;
	FORR(c,S) {
		ZERO(to);
		if(c=='(') {
			for(i=0;i<=sum;i++) {
				(to[i]+=from[i])%=mo;
				(to[i+1]+=from[i])%=mo;
			}
			sum++;
		}
		else {
			for(i=0;i<=sum;i++) {
				if(i) (to[i-1]+=from[i])%=mo;
				if(i!=sum) (to[i]+=from[i])%=mo;
			}
			
			sum--;
		}
		swap(from,to);
	}
	
	cout<<from[0]<<endl;
	
}

まとめ

こちらはすんなり。