競技プログラミング用 知識集積所
I - Coins
最終更新：
sport_programming
-
view
問題
必要知識
ABCのB以下レベルの内容は省略
考え方
「表が半分より多い確率」だけを継承してもしょうがないので、「表がj枚出る確率」を全部継承していく。
コインが0枚のときは「0枚の確率は1、それ以外は0」で初期化する。
その後はi枚目まででj枚表が出るには
その後はi枚目まででj枚表が出るには
- i-1枚目まででj-1枚表が出て、i枚目も表が出る
- i-1枚目まででj枚表が出て、i枚目は裏が出る
のどちらか、と計算していけばいい。
最終的にn枚での確率を全部出したら、半分より多く表が出る範囲を合計すればいい。
