TopCoder SRM 715 Div2 Hard InPrePost

まぁこれはすんなり。
https://community.topcoder.com/stat?c=problem_statement&pm=14610

問題

ラベル付き根付き二分木木を深さ優先探索するとき、pre/in/postの3通りの辿り方について以下のように訪問順のラベルを並べる。
sはpre/in/postのいずれかを含む配列である。

• dfs(v,order):
  • left,rightは対応する左右の子頂点
  • orderがpre : v + dfs(left,s[0]) + dfs(right,s[1])
  • orderがin : dfs(left,s[3]) + v + dfs(right,s[4])
  • orderがpost : dfs(left,s[4]) + dfs(right,s[5]) + v

根頂点rootに対するdfs(root,pre),dfs(root,in),dfs(root,in)が与えられたとき、そのような訪問順を満たす木は存在するか判定せよ。

解法

dfs(v,pre),dfs(v,in),dfs(v,post)の3つのラベルの並び順が与えられたとき、条件を満たす木が存在するかを再帰的に判定していこう。
まず、3種が同じラベル群の並べ替えでない場合は明らかに条件を満たさない。
以下3種が並べ替えると同じになる場合を考える。

dfs(v,pre)の先頭は当然vでなければならない。
また、vがわかるとdfs(v,in)の結果からleftとrightのサイズがわかる。
よってdfs(v,pre),dfs(v,in),dfs(v,post)からdfs(left,*)とdfs(right,*)がわかるので再帰的に判定していけばよい。

class InPrePost {
	public:
	vector<int> S;
	
	int ok(string a1, string a2, string a3) {
		string v1=a1,v2=a2,v3=a3;
		sort(ALL(v1));
		sort(ALL(v2));
		sort(ALL(v3));
		if(v1!=v2 || v1!=v3) return 0;
		if(v1.size()<=1) return 1;
		int label = a1[0];
		int a,b,i;
		FOR(i,a2.size()) if(a2[i]==label) {
			a=i;
			b=a2.size()-(i+1);
		}
		string L[3],R[3];
		L[S[0]]=a1.substr(1,a);
		R[S[1]]=a1.substr(1+a);
		L[S[2]]=a2.substr(0,a);
		R[S[3]]=a2.substr(1+a);
		L[S[4]]=a3.substr(0,a);
		R[S[5]]=a3.substr(a,b);
		return ok(L[0],L[1],L[2]) && ok(R[0],R[1],R[2]);
	}
	
	string isPossible(vector <string> s, vector <int> a1, vector <int> a2, vector <int> a3) {
		S.clear();
		string s1,s2,s3;
		FORR(c,s) {
			if(c=="pre") S.push_back(0);
			if(c=="in") S.push_back(1);
			if(c=="post") S.push_back(2);
		}
		FORR(a,a1) s1.push_back(a);
		FORR(a,a2) s2.push_back(a);
		FORR(a,a3) s3.push_back(a);
		
		if(ok(s1,s2,s3)) return "Possible";
		return "Impossible";
	}
}

まとめ

これは割とすぐ思いつくかな。