Codeforces #288 Div2 E. Arthur and Brackets

こちらは何とか解けた。
http://codeforces.com/contest/508/problem/E

問題

correct bracket sequencesとは、同数の開き括弧と閉じ括弧から構成され、両者の対応がとれた状態の文字列を指す。
N組の括弧の対2N文字からなるbracket sequencesを考える。
先頭から順に、N個の開きかっこに対し、そこから閉じ括弧までの文字数の下限L[i]と上限R[i]が与えられる。

閉じ括弧までの文字数がL[i]～R[i]となるようなcorrect bracket sequencesが存在するか答えよ。

解法

O(N^3)解法とO(N)解法がある。自分は前者で解いた。

l個目からr個目までの開きかっこ(と対応する閉じ括弧)からなるcorrect bracket sequencesをメモ化再帰で求めていく。
(もちろん、l=1、r=Nとしたときの解が答えである)

l個目の開き括弧と閉じ括弧の間に、何個開き括弧・閉じ括弧の対が入るか総当たりする。
i個入る場合、以下の３つを満たせば条件を満たすcorrect bracket sequencesが作成可能である。

• L[l]≦2*i+1≦R[i]を満たす。
• (l+1)～(l+i)個目の開きかっこ(と対応する閉じ括弧)からなるcorrect bracket sequencesが作成可能である。
• (l+i+1)～r個目の開きかっこ(と対応する閉じ括弧)からなるcorrect bracket sequencesが作成可能である。

今回メモリ制限が厳しいので、メモ化再帰の過程でcorrect bracket sequencesを作ることはできない。
よって、１回メモ化再帰で上記(l,r)に対応したiを求め、再度探索してbracket sequencesを作ると良い。

なお、O(N)解法は「これ以上開きかっこを加えると破綻する場所で閉じ括弧を加える」という解法のようだ。

int N;
int LL[606],RR[606];
int memo[606][606];

int dodo(int L,int R) {
	if(R<=L) return 0;
	int& ret=memo[L][R];
	if(ret>=0) return ret;
	ret=5000;
	
	int i;
	for(i=0;i<R-L;i++) {
		if(LL[L]<=i*2+1 && i*2+1<=RR[L]) {
			if(dodo(L+1,L+i+1)<=1000 && dodo(L+i+1,R)<=1000) return ret=i;
		}
	}
	return ret;
}

void dodo2(int L,int R) {
	if(R<=L) return;
	_P("(");
	dodo2(L+1,L+memo[L][R]+1);
	_P(")");
	dodo2(L+memo[L][R]+1,R);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>LL[i]>>RR[i];
	MINUS(memo);
	
	if(dodo(0,N)>=1000) return _P("IMPOSSIBLE\n");
	dodo2(0,N);
	_P("\n");
	
	
}

まとめ

O(N^3)が想定解で助かった…。