解いた問題のソースコードと解説など。


SRM 537 Div2 Hard PrinceXToastbook

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11356&rd=14730
本を読んでそこに書かれている知識を手に入れたい。本iに書かれている知識を手に入れるにはprerequisites[i]の本を予め読んでおく必要がある。読んでいなければ知識は習得できない。prerequisites[i]が-1な本はどの予備知識も必要としない。ランダムな順番で本を読むとき得られる知識の回数の期待値を求めよ。

やりかた

Editorialを参考にしました。

ランダムな順番で本を読むことから、各本を読む順番は独立になる。そのため和の期待値は期待値の和になるので、各本を読む期待値を足しあわせればいい。
ある本iの知識を習得するにはprerequisites[i]の知識を習得している必要があり、それにはprerequisites[prerequisites[i]]の知識を習得している必要があり、というように前提知識をすべて習得している必要がある。このように考えると、本を読むべき順番というのは有向グラフで表現されることになる。このうち、循環している部分はどの順番で読んでもそこから知識は得られないので除外して考えると、このグラフは森になる。根(前提知識を必要としない本)からの距離がkのノード(本)の知識を習得するには根から順繰りに読むときのみなので、そのような確率は1/(k+1)!になる。これをすべてのノードについて計算し和を取ればいい。

以下ソース。

class PrinceXToastbook {
public:
  bool visit[55];
  double eat(vector <int> prerequisite) {
    double result = 0.0;
    int N = prerequisite.size();
    fill(visit, visit + 55, false);

    for(int i = 0; i < N; i++){
      double prob = 1.0;
      int needs = 0;
      fill(visit, visit + 55, false);
      for(int j = i; j != -1; j = prerequisite[j]){
	if(visit[j]){
	  prob = 0.0;
	  break;
	}
	visit[j] = true;
	needs++;
	prob /= needs;
      }
      result += prob;
    }
    return result;
  }
};

やりかたはわかって喜んでいたものの、実装ができずに答えを見てしまった。予めすべてのノードにたいして木の深さを測ってから確率計算する、と決め込んで考えてしまっていたため、コードが複雑になりギブアップ。すべてのノードについて逐次深さを測り、確率を計算するという事を考えなかった。ソースも非常に簡潔で良いと思う。実装力も足りないなあ(;ノД`)

Get up! 明日のSUPER ST@R!