Codeforces #1073 : Div1. B2. Sub-RBS (Hard Version)

微妙にややこしい問題設定。
https://codeforces.com/contest/2190/problem/B2

問題

ある括弧列に対し、良い括弧列の定義はB1と同じとする。
Codeforces #1073 : Div1. B1. Sub-RBS (Easy Version) - kmjp's blog

括弧列Tのスコアを、Tに対する良い括弧列の長さの最大値とする。
括弧列Sが与えられる。Sの各部分文字列に対するスコアの総和を求めよ。

解法

Sを後ろから１文字ずつ見て、以下の状態を管理しながらTに組み込むかどうか見ていこう。

• 組み込む場合、開き括弧が２個以上登場した後、閉じ括弧が１個以上ある状態を経たかどうか
• 開き括弧と閉じ括弧の数の差
• Tの長さ

開き括弧と閉じ括弧の数の差が0になったタイミングで、１つ目の条件を満たしているなら|T|-2がスコアに計上される。

int T,N;
string S;
const ll mo=998244353;
ll dp[101][101][4]; // len, cur, status


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		ZERO(dp);
		dp[0][0][0]=1;
		ll ret=0;
		for(i=N-1;i>=0;i--) {
			for(l=N-1;l>=0;l--) {
				FOR(x,l+1) {
					if(S[i]==')') {
						(dp[l+1][x+1][0]+=dp[l][x][0])%=mo;
						(dp[l+1][x+1][1]+=dp[l][x][1])%=mo;
						(dp[l+1][x+1][3]+=dp[l][x][2])%=mo;
						(dp[l+1][x+1][3]+=dp[l][x][3])%=mo;
					}
					else if(x) {
						(dp[l+1][x-1][1]+=dp[l][x][0])%=mo;
						(dp[l+1][x-1][2]+=dp[l][x][1])%=mo;
						(dp[l+1][x-1][2]+=dp[l][x][2])%=mo;
						(dp[l+1][x-1][3]+=dp[l][x][3])%=mo;
						if(x-1==0) (ret+=dp[l][x][3]*(l-1))%=mo;
					}
				}
			}
		}
		cout<<ret%mo<<endl;
	}
}

まとめ

Hardの方がかかった時間短いな。