TCO 15 1B Med The Tips

問題

n個の宝を探す宝探しゲームをする。
ノーヒントで宝iを探せる確率はp[i]
G[i][j]=Yならばi番目の宝が見つかればi番目の宝にj番目の宝の場所も記されているのでj番目の宝も見つけられる。

見つけられる宝の個数の期待値を求める問題。

解法

i番目の宝が見つかる確率をp[i]とおく。

G'[i][j]を「iからjまで連結しているならば1」として隣接行列を作る。

この時p[i]は「1- (iに到達できるnodeがどれも見つからない)」なので余事象で簡単に計算できる。