kmjp's blog

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

TopCoder SRM 537 Div2 Hard PrinceXToastbook

これも気づいてしまえば実装は簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=11356

問題

0~(N-1)の魔法がある。
初期状態ではいずれも未習得である。

それぞれの魔法が書かれた魔法の書を見ることでその魔法を習得できるが、一部の魔法は前提として他の魔法を習得済みでないと(魔法の書を読んでも)習得できない。

0~(N-1)のpermutationを均等な確率で1つ選択して、その順で魔法の書を読む場合、習得できる魔法の期待値を答えよ。

解法

ある魔法Aを覚えるために、A->B->C->Dといくつかの依存関係チェーンがあったとする。
この場合、Aを習得できる確率は、permutation中でD->B->C->Aの順となることであり、その確率はチェーンの深さの階乗の逆数である。

ここまでわかれば後は簡単で、依存関係をDFSでたどり、チェーンの深さの階乗の逆数を足しこんでいけばよい。
似たような問題、Codeforcesで前に見たなぁ。

class PrinceXToastbook {
	public:
	vector<int> P;
	double dfs(int cur,int dep,double div) {
		double ret = 1/div;
		int i;
		FOR(i,P.size()) if(P[i]==cur) ret += dfs(i,dep+1,div*(dep+1));
		return ret;
	}
	
	double eat(vector <int> pre) {
		P=pre;
		int N=pre.size();
		int x;
		vector<int> V;
		double ret=0;
		
		FOR(x,N) if(pre[x]==-1) ret += dfs(x,1,1);
		return ret;
	}
};

まとめ

最初気づくまでちょっとかかった。
Codeforcesで似た問題を見た成果が出たね。