TopCoder SRM 731 Div1 Easy TreesAndBrackets

２完+1Chalしたのに遅かったのでレート減。
https://community.topcoder.com/stat?c=problem_statement&pm=14836

問題

根付き木を成すグラフがT1,T2の２つ与えられる。
それぞれの親子関係は括弧列で表現される。

T1から(相対的な頂点の順序関係を変えずに)任意の葉頂点を取り除く、ということを任意回数繰り返したとき、T1をT2にできるか。

解法

以下の関数を考え、メモ化再帰でf(0,|T1|,0,|T2|)を判定すればよい。
f(L1,R1,L2,R2) := 2つの部分文字列T1[L1..R1)、T2[L2..R2)が問題の条件を満たすかどうかの真偽値

T1[L1]、T2[L2]はいずれも開き括弧なので、対応する閉じ括弧の位置をC1、C2とする。

• f(L1,C1+1,L2,C2+1)がtrueならば、あとは残りf(C1+1,R1,C2+1,R2)を判定する
• f(L1,C1+1,L2,C2+1)がfalseならば、T1[L1..C1)のSubTreeは取り除き、あとは残りf(C1+1,R1,L2,R2)を判定する

int N[2];
string S[2];
int P[2][101];

map<vector<int>,int> M;


class TreesAndBrackets {
	public:
	
	int ok(int L1,int R1,int L2,int R2) {
		if(R2<=L2) return 1;
		if(R1-L1<R2-L2) return 0;
		
		if(M.count({L1,R1,L2,R2})) return M[{L1,R1,L2,R2}];
		
		if(ok(L1+1,P[0][L1]-1,L2+1,P[1][L2]-1)) return M[{L1,R1,L2,R2}]=ok(P[0][L1]+1,R1,P[1][L2]+1,R2);
		return M[{L1,R1,L2,R2}]=ok(P[0][L1]+1,R1,L2,R2);
	}
	
	string check(string t1, string t2) {
		M.clear();
		S[0]=t1;
		S[1]=t2;
		int i,j;
		FOR(i,2) {
			N[i]=S[i].size();
			vector<int> V;
			FOR(j,N[i]) {
				if(S[i][j]=='(') {
					V.push_back(j);
				}
				else {
					P[i][j]=V.back();
					P[i][V.back()]=j;
					V.pop_back();
				}
			}
		}
		
		if(ok(0,N[0],0,N[1])) return "Possible";
		else return "Impossible";
		
	}
}

まとめ

コードはさほど長くないのだけど妙に考察に手間取った。