kmjp's blog

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

Codeforces #289 Div2 F. Progress Monitoring

本番時間切れ。
http://codeforces.com/contest/509/problem/F

問題

N頂点の木をなすグラフがあるとする。
1番の頂点から始め、隣接する若い番号の順にDFSするアルゴリズムにより、全頂点を探索することを考える。

前記アルゴリズムによる初訪問の頂点番号順B[i]が与えられる。
そのような訪問順になる木は何通りあるか答えよ。

解法

以下の2値を使いDPしていく。
変数名はEditorial準拠。

  • D(L,R): B[L]から初めてB[L]~B[R]をDFSで訪問できるような木の組み合わせ数。
  • E(L,R): B[L..R]は番号順にいくつかのサブツリーに分けられ、各サブツリーB[x..y]はB[x]からDFSで訪問できる。また各サブツリーの根の番号は昇順である。というようなサブツリー群の組み合わせ。

D(L,R)及びE(L,R)は以下のように求められる。

  • E(L,R)はLを根としてB[(L+1)..R]をサブツリーに持つと考えると、E(L,R)=D(L+1,R)
  • D(L,R)は以下の和:
    • 全体が1つのサブツリーになる場合、すなわちE(L,R)。
    • B[L..(x-1)]の単一サブツリーと、B[x..R]のいくつかのサブツリーに分割できる場合、すなわち

B[L]<B[x]となるL<x≦Rに対し、D(L,x-1)*E(x,R)の和。

D(i,i)やE(i,i)は1。
ここからD(i,i+w)、E(i,i+w)をだんだんwを広げながら求めて、最終的にD(1,N)が答え。

int N,B[600];
ll mo=1000000007;
ll pat;
ll sp[502][502];
ll sub[502][502];

void solve() {
	int i,j,k,l,r,x,y,w; string s;
	
	cin>>N;
	pat=1;
	FOR(i,N) cin>>B[i], sp[i][i]=sub[i][i]=1;
	
	for(w=1;w<N;w++) {
		for(l=0;(r=l+w)<N;l++) {
			sp[l][r]=sub[l][r]=sp[l+1][r];
			for(x=l+1;x<=r;x++) if(B[l]<B[x])  sp[l][r]+=sub[l][x-1]*sp[x][r]%mo;
			sp[l][r] %= mo;
		}
	}
	
	cout<<sub[0][N-1]<<endl;
}

まとめ

終わってみるとコードはシンプル。
O(N^3)でも意外と間に合うのね。