Hatena::Grouptopcoder

hotpepsiの練習帳

2012-03-21

SRM 537 Div2

20:17

練習

Hard (1000) PrinceXToastbook

問題

  • N冊の本がある。
  • そのうちの何冊かは、別の本を読んでからでないと理解できない。
  • ランダムにN冊読むとき、理解できる冊数の期待値を求める。

方針

  • わからん
  • uwiさんに教わる
  • 事前知識を親として自分が子というグラフとして考える
  • 木とか森になっている
  • 木が成立せず、閉路があると失敗する(閉路の部分がゼロになる)
  • 木の場合、理解できる場合の数÷とりうる全ての場合の数を考えればよい
  • 深さをdepthとすると、得られる知識は1.0÷depth!
  • https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_537/PrinceXToastbook.cpp

感想

赤い人に教わるという贅沢。

まず制約条件から、どういうものなのか(グラフで表せるのかとか)を描くべき。

閉路検出は最初、自分に戻ってくるかどうかを判定したら無限ループした。すばらしいテストケース! 深さがノード数を超えたら閉路、でよい。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20120321