不参加だったけど、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); } }
まとめ
一件ややこしいけど、解法はさほど難しくもない。