kmjp's blog

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

CODE FESTIVAL 2015 決勝 : G - スタンプラリー

既出問題だったのでコピペで解いてしまいました。
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_g

問題

1~Nの番号が振られた木を成す無向グラフがある。
1番の頂点から初めて、隣接する未到達の点のうち最小値のところにDFSで移動する、という作業を繰り返し木を探索する。
N個の頂点の初訪問の順番が与えられるとき、そのような訪問順となるグラフの組み合わせ数を求めよ。

解法

完全に既出です。本番もこのコードを少し直して通しました。
Codeforces #289 Div2 F. Progress Monitoring - kmjp's blog

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; string s;
	
	cin>>N;
	FOR(i,N) cin>>B[i], B[i]--, sp[i][i]=sub[i][i]=1;
	if(B[0]!=0) return _P("0\n");
	
	for(int 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;
	
}

解法

既出でなければ多分時間内に解けなかった。
みんなよくこれ本番通すな…割とよくあるテクなのかな?

広告を非表示にする