TopCoder SRM 731 Div2 Hard JustBrackets

割と手こずった。
https://community.topcoder.com/stat?c=problem_statement&pm=14855

問題

Div1 Easy同様、木構造を括弧列であらわすことを考える。
TopCoder SRM 731 Div1 Easy TreesAndBrackets - kmjp's blog

葉頂点をいくつか取り除いて生成できる空でない括弧列のうち、辞書順最小のもの(以下最小括弧列と呼ぶ)を求めよ。

解法

まず入力の文字列に対して、複数の括弧列に分解できる場合、個々に対応する最小括弧列を求めてその最小値を答えればよい。

f(S) := これ以上細かく分解できない括弧列Sにおける最小括弧列
とする。
Sが"( A B C ... )"と分解できる場合、f(S)の候補として再帰的に"( f(A) f(B) f(C) ... )"とすることが一つ考えられる。
ただし例えばf(A)≧f(B)ならf(A)をあえて置く理由は無いのでf(A)は消せる。
このように、f(A),f(B),f(C)...について後ろにより小さいものがあるなら前の物は消す、という処理を繰り返せばf(S)をより小さくできる。

class JustBrackets {
	public:
	string hoge(string S) {
		vector<string> V;
		V.push_back(")");
		S=S.substr(1,S.size()-1);
		int dep=0;
		string T;
		FORR(c,S) {
			T+=c;
			if(c=='(') dep++;
			else dep--;
			if(dep==0) {
				string R=hoge(T)+")";
				while(V.size() && R<V.back()) V.pop_back();
				V.push_back(R);
				T="";
			}
		}
		
		string ret="(";
		FORR(v,V) ret+=v.substr(0,v.size()-1);
		ret+=")";
		
		return ret;
	}
	
	string getSmallest(string s) {
		string ret=")";
		int dep=0;
		string T;
		FORR(c,s) {
			T+=c;
			if(c=='(') dep++;
			else dep--;
			if(dep==0) {
				ret=min(ret,hoge(T));
				T="";
			}
		}
		return ret;