Codeforces #1082 : Div1 C. Rigged Bracket Sequence

問題

括弧列Sが与えられる。
このうちいくつかの位置を選択し、それらを右rotateすることを考える。

その場合も、Sが正しい括弧列となる選択は何通りか。

解法

状態を３つ持って、先頭からDPしよう。
状態は以下の３つ。

• 選択したうちの最後の位置が、閉じ括弧か開き括弧か
• 先頭から見て、ここまでのうち最後に選択された位置は、閉じ括弧か開き括弧か
• rotateにより、開き括弧が先行する数がrotate前に比べて+1/0/-1のどれだけ変化したか。

int T,N;
string S;
const ll mo=998244353;
int P[303030];
ll p2[303030];

ll from[3][2][2];
ll to[3][2][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,301010) p2[i+1]=p2[i]*2%mo;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		ll ret=N;
		
		ZERO(from);
		ZERO(to);
		FOR(i,N) {
			P[i+1]=P[i];
			if(S[i]=='(') P[i+1]++;
			else P[i+1]--;
			
			// same
			ZERO(to);
			//新規
			if(S[i]=='(') {
				// ')'
				if(P[i+1]>1) (to[0][1][0]+=1)%=mo;
				// '('
				(to[1][0][0]+=1)%=mo;
			}
			if(S[i]==')') {
				// ')'
				(to[1][1][1]+=1)%=mo;
				// '('
				(to[2][0][1]+=1)%=mo;
			}
			FOR(j,3) FOR(x,2) FOR(y,2) if(from[j][x][y]) {
				//same
				if(P[i+1]+(j*2-2)>=0) (to[j][x][y]+=from[j][x][y])%=mo;
				int nj=j;
				if(y==0&&S[i]==')') nj++;
				else if(y==1&&S[i]=='(') nj--;
				assert(nj>=0&&nj<=2);
				//取れるか
				if(P[i+1]+(nj*2-2)>=0) {
					(to[nj][x][S[i]==')']+=from[j][x][y])%=mo;
					if(x==(S[i]==')')) (ret+=from[j][x][y])%=mo;
				}
			}
			
			swap(from,to);
			
		}
		cout<<ret<<endl;
		
	}
}

まとめ

愚直に状態を分ければいいので、C問題の難易度としては低めかも…と思いつつ、これ1750ptなんだな。