競技プログラミング用 知識集積所
ABC402E - Payment Required
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
状況を
- 1問目は正解済かどうか（2択）
- 2問目は正解済かどうか（2択）
- 3問目は正解済かどうか（2択）
（中略）
- n問目は正解済かどうか（2択）
- 所持金はいくらか（0円からx円までx+1択）
の組み合わせと考えると、全部で2^n*(x+1)通りの状況が考えられる。
データサイズが最大の場合でも、この個数は130万通りくらいしかない。
よって、各状況での期待値を150回以内くらいの計算で求められるなら、動的計画法（未作成）で解答できる。
問題の解答状況はビット全探索（未作成）と似たような考え方で管理してやればよい。
データサイズが最大の場合でも、この個数は130万通りくらいしかない。
よって、各状況での期待値を150回以内くらいの計算で求められるなら、動的計画法（未作成）で解答できる。
問題の解答状況はビット全探索（未作成）と似たような考え方で管理してやればよい。
期待値は、挑戦可能な（つまり、まだ正解していなくて、所持金が足りる）各問題k番に対し、
k番不正解率*残金減って同じ解答状況での期待値 + k番正解率*（残金減ってkが正解済になった状況での期待値+k番の得点）
を計算し、最大値（挑める問題がなければ0）を考えればよい。
この計算は、式の見た目こそ煩雑だが、問題数が8問なので150回以内の計算で終わることは明らかであり、これで解ける。
この計算は、式の見た目こそ煩雑だが、問題数が8問なので150回以内の計算で終わることは明らかであり、これで解ける。
