Codeforces Round #5 C.Longest Regular Bracket Sequence

Codeforces 動的計画法

積み残し。

問題概要

括弧からなる文字列を、+と1を挿入して正しい数式にできるとき、その文字列を"regular"であるという。
例えば"(())()", "()","(()(()))"はregularであり、")(", "(()", "(()))("はregularではない。


長さ10^6以下の括弧からなる文字列が与えられる時、この文字列の連続する部分列で、regularな文字列のうち長さが最大のものについて、その長さと出現回数を求めよ。

解法

自力で解けなかったのでlaycurse先生のブログを参考に……


括弧の深さが0以下になってしまう（例：())など）とその時点でregularでなくなってしまうのはすぐにわかる。
なので、

  • それぞれの括弧の深さごとに、開始括弧の位置を覚えておき
  • 深さがdになったときにd+1の開始位置をリセットする

ような操作を繰り返していけば最大長のregularな文字列を得ることができる。

ソースコード

int idx[10000001];

void run()
{
	string str; cin>>str;
	fill_n(idx,10000001,inf);
	
	int ans=0,times=1,d=5000000;
	
	rp(i,str)
	{
		if(str[i]=='(')
		{
			d++;
			if(idx[d]==inf)idx[d]=i;
		}
		else
		{
			int tmp=i-idx[d]+1;
			if(tmp==ans)times++;
			if(tmp>ans)ans=tmp,times=1;
			idx[d+1]=inf; d--;
		}
	}
	cout<<ans<<" "<<times<<endl;
}