CSAcademy Round #51 : E. Wrong Brackets

割と定番解法。
https://csacademy.com/contest/round-51/task/wrong-brackets/

問題

開き括弧N個閉じ括弧N個で構成される計2N文字の文字列を考える。
そのような文字列のうち、Correct Bracket Sequenceではないものの辞書順K番目を求めよ。

解法

辞書順で定まる文字列を求めるので、定番解法として頭から決めていこう。
今次の文字に"("を取ると、条件を満たす(correctでない)文字列の組み合わせがK個以下なら"("、そうでないなら")"を取ればよい。

残された文字列により、correctでない文字列が何通りできるかはメモ化再帰で求められる。

int N;
ll K;
ll memo[50][50];
ll C[201][201];



ll hoge(int op,int cl) {
	if(op==0 && cl==0) return 0;
	if(cl<op) return 0;
	if(memo[op][cl]>=0) return memo[op][cl];
	ll ret=0;
	
	if(op==cl) {
		ret=C[op+cl][cl-1];
	}
	else {
		ret=hoge(op-1,cl)+hoge(op,cl-1);
		if(ret<0) ret=0x7FFFFFFFFFFFFFFFLL;
	}
	
	return memo[op][cl]=ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,190) {
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;j++) {
			C[i][j]=C[i-1][j-1]+C[i-1][j];
			if(C[i][j]<0) C[i][j]=0x7FFFFFFFFFFFFFFFLL;
		}
	}
	
	MINUS(memo);
	cin>>N>>K;
	int op=N,cl=N;
	
	string R;
	int ng=0;
	while(op || cl) {
		if(op>cl) ng=1;
		if(op==0) {
			R+=")";
			cl--;
		}
		else if(cl==0) {
			R+="(";
			op--;
		}
		else if(ng) {
			if(C[op+cl-1][op-1]>=K) {
				R+="(";
				op--;
			}
			else {
				K-=C[op+cl-1][op-1];
				R+=")";
				cl--;
			}
		}
		else {
			if(hoge(op-1,cl)>=K) {
				R+="(";
				op--;
			}
			else {
				K-=hoge(op-1,cl);
				R+=")";
				cl--;
			}
		}
	}
	cout<<R<<endl;
	
}

まとめ

Kが地味に限界ギリギリのサイズが上限なのでちょっと気を使った。