ABBYY Cup 3.0 : B. EKG

Bまではまだ割と簡単。
http://codeforces.com/contest/316/problem/B2

問題

1～N番の番号をふられたN匹のビーバーが、なんらかの順番で1列に並んでいる。
一部のビーバーは自分の前のビーバーの番号を知っており、他のビーバーは自分の前のビーバーの番号を知らない。
X番のビーバーは列の何番目である可能性があるか、すべて答えよ。

解法

自分の前がだれかわからないビーバーを先頭として、多数のビーバー列ができると考える。
Xの含まれた列の前に、Xの含まれないビーバー列が任意の個数入ることができる。

よって、Xの含まれないビーバー列内のビーバー数をDPして、Xの含まれた列の前に並びうるビーバー数を求める。
そしてXの含まれる列中でXのいる位置を加算すればよい。

int N,X;
int A[1001],B[1001],vis[1001],bit[1001];

void solve() {
	int f,r,i,j,k,l, x,y;
	int q=0;
	
	cin>>N>>X;
	FOR(i,N) {
		cin>>A[i+1];
		B[A[i+1]]=i+1;
	}
	
	x=1;y=X;
	vis[y]++;
	while(A[y]!=0) {
		x++;
		y=A[y];
		vis[y]++;
	}
	
	bit[x]=1;
	FOR(i,N) {
		if(A[i+1]!=0 || vis[i+1]) continue;
		x=1;y=i+1;
		while(B[y]!=0) x++,y=B[y];
		for(y=N-x;y>=0;y--) if(bit[y]) bit[y+x]++;
	}
	
	FOR(i,N+1) if(bit[i]) _P("%d\n",i);
	return;
}

まとめ

問題そのものはともかく、問題設定が面白いな。