TopCoder SRM 660 Div1 Medium Privateparty

落ち着いてみれば簡単なのに…。
http://community.topcoder.com/stat?c=problem_statement&pm=13804

問題

問題設定はDiv2 Mediumと同じ。
TopCoder SRM 660 Div2 Medium PrivateD2party - kmjp's blog

ただしこちらは、パーティーの最大参加者数を求めるのではなく、参加順が均等にランダムな場合の参加者数の期待値を求める。

解法

各人が参加するかどうかは、嫌いな人が先に来ているかどうかに依存する。
この考えを再帰的に考えると、Div2 Medium同様に嫌っている関係を有効グラフで表したとき、各人から到達可能な頂点の影響を受けることになる。

i番の人が影響を受ける人数を(自分も含め)M[i]人とする。
このM[i]人のうち、自分と自分が直接嫌う人が何番目に来るかによって再帰的に自分が参加する確率を求めることができる。

例えば、自分が参加する順番がこのM[i]人の中で1～M[i]番になる確率はそれぞれ1/M[i]である。
仮に自分が参加する順番をx番、自分が嫌いな人が参加する順番をy番とする。
M[i]人の影響を受ける人がx番に来るとき、パーティーに参加する確率をDP[M[i]][x]とする。
yは1～M[i]のうちxではないものを1/(M[i]-1)の確率で選ぶことになる。

y＞xの場合、自分の嫌いな人は自分の後に来るので、嫌いな人の来る確率は関係なく自分は参加する。
y＜xの場合、嫌いな人がその場にいる確率はDP[M[i]-1][y]なので、自分が参加する確率はその反対のDP[M[i]-1][y]である。

上記の要領でDP[M[i]][x]をDPで求めれば、その和がM[i]の影響を受ける人の参加確率となる。
ループがあるときにこれで問題がないか気になるが、「自分の嫌いな人は自分の後に来るので、嫌いな人の来る確率は関係なく自分は参加する。」の条件より、自分の参加がループして自分にかかることはないので、無視してよい。

class Privateparty {
	public:
	int N;
	double dp[51][51],dpsum[51];
	vector<int> A;
	int vis[51];
	
	int dfs(int c) {
		vis[c]=1;
		if(vis[A[c]]) return 1;
		return dfs(A[c])+1;
	}
	
	double getexp(vector <int> a) {
		A=a;
		N=a.size();
		int i,j,x,y;
		
		ZERO(dp);
		dpsum[1]=dp[1][1]=1;
		for(i=2;i<=N;i++) {
			dpsum[i]=0;
			for(j=1;j<=i;j++) {
				for(x=1;x<=i;x++) {
					if(x<j) dp[i][j]+=(1-dp[i-1][x]);
					if(x>j) dp[i][j]+=1;
				}
				dp[i][j] /= (i-1);
				dpsum[i]+=dp[i][j]/i;
			}
		}
		
		double ret=0;
		FOR(i,N) {
			ZERO(vis);
			ret += dpsum[dfs(i)];
		}
		
		return ret;
	}
}

まとめ

強連結成分分解は不要だったか。