hotpepsiの練習帳

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

感想

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

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

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