公式

C - Catastrophic Roulette 解説 by evima

Hints

Hint 1 Consider solving it using dynamic programming (DP).
For example, if you use “how many times the roulette has been spun so far” as the index for DP, you will have to manage an infinite number of states.
Consider solving it by keeping the number of states to manage as few as possible. What should you manage and how?

Hint 2 Let \(q\) be the number of distinct integers that have appeared, and consider managing the following quantities for each value of \(q\):

  • The probability that it is the first/second player's turn right after the number of distinct integers has become $q$
  • The expected amount of the fine paid by the first/second player at the moment right after the number of distinct integers has become $q$

This problem can be solved by updating these quantities for \(q=1,2,\dots,N-1\) in order.
Formulate these carefully to implement it.


Hint 3 For \(0 < p < 1\), it holds that \(\displaystyle 1 + p^2 + p^4 + p^6 + \dots = \sum_{i=0}^{\infty} p^{2i} = \frac{1}{1-p^2}\) .
This hint might be useful if you are having trouble with handling infinite sums.

投稿日時:
最終更新: