ABC194 D-Journey
回数の期待値とは ってなった(適当)
サンプル見たらなんか収束してそう
検索してみた
見たら、期待値漸化式を解けば求められるらしい
導いてみた
期待値を$ E, 1回目で成功するときの確率を$ P(A),1回目で失敗するときの確率を$ P(B)とおく
1回目で成功するときの期待値は$ 1(そりゃそう)
$ \therefore P(A)・1=P(A)
1回目で失敗,その後の試行で成功する期待値は$ E+1(既に1回投げていて，この後いつ成功するかどうかは最初と変わらない)
$ \therefore P(B)・(E+1)=(1-P(A))(E+1)
これより期待値$ Eは
$ E=P(A) + (1-P(A))(E+1) \\ E=\dfrac{1}{P(A)}
全頂点がnで、繋いでいない頂点がk個あるとき、そのどれかにつなぐ期待値は$ E_k=\dfrac{n}{k}
ゆえに$ E= \sum_{k=1}^{n}\dfrac{n}{k}
求められるのでは？ってなる→AC
感想
数学苦手すぎる
実装はかんたんだけど過程がムズカシイ...