kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2022 Round4 : Easy PreInPostOrder

不参加だったけど、Easyは普通に解けたので出てたらレート上がってたな。
https://community.topcoder.com/stat?c=problem_statement&pm=17755

問題

1~Nのラベルがついた二分木を探索することを考える。
現在いる頂点の深さに応じ、pre-order/in-order/post-orderを切り替えながら訪問した木のラベルを出力する手順を考える。
初手pre-orderを取った場合と、初手in-orderを取った場合のラベル出力順A,Bが与えられる。
このようなラベル出力順を満たす木は何通りあるか。

解法

以下の通り、両ラベル列の部分列に対し、メモ化再帰を行おう。
dp(X,Y,L,depth) := 両ラベル列のうち、片方はA[X...(X+L-1)]に対応する部分列、もう片方はB[Y...(Y+L-1)]に対応する部分列を出力するような木の個数のうち、ルートの深さがdepthであるもの

depthに応じて、以下の通り処理を分岐できる。

  • 片方がpre-order,片方がin-orderの場合、前者の先頭ラベルを見ればルートが確定できるし、そのラベルの後者の部分列での位置を見れば、左と右の部分木の頂点数個数がわかる。あとは再帰。
  • 片方がpost-order,片方がin-orderの場合、前者の末尾のラベルを見ればルートが確定できるし、以後同様。
  • 片方がpre-order,片方がpost-orderの場合、前者の先頭ラベルと後者の末尾のラベルを見ればルートが確定できる。左右の部分木のサイズが確定できないが、そこは総当たりしてしまおう。
ll memo[3][71][71][71];
const ll mo=1000000007;
vector<int> X,Y;

class PreInPostOrder {
	public:
	
	ll hoge(int L1,int L2,int len,int turn) {
		if(len==0) return 1;
		if(len==1) return X[L1]==Y[L2];
		if(memo[turn][L1][L2][len]>=0) return memo[turn][L1][L2][len];
		ll ret=0;
		
		int i;
		if(turn==0) {
			FOR(i,len) if(X[L1]==Y[L2+i]) ret+=hoge(L1+1,L2,i,1)*hoge(L1+1+i,L2+i+1,len-(i+1),1)%mo;
		}
		else if(turn==1) {
			FOR(i,len) if(X[L1+i]==Y[L2+len-1]) ret+=hoge(L1,L2,i,2)*hoge(L1+1+i,L2+i,len-(i+1),2)%mo;
		}
		else {
			if(X[L1+len-1]==Y[L2]) {
				FOR(i,len) ret+=hoge(L1,L2+1,i,0)*hoge(L1+i,L2+i+1,len-(i+1),0)%mo;
			}
		}
		
		
		return memo[turn][L1][L2][len]=ret%mo;
	}
	
	int reconstruct(vector <int> PIP, vector <int> IPP) {
		X=PIP;
		Y=IPP;
		MINUS(memo);
		return hoge(0,0,X.size(),0);
		
	}
}

まとめ

一件ややこしいけど、解法はさほど難しくもない。