플래티넘 III
문제
풀이
시행 횟수의 기댓값
각 종류의 피어난 꽃의 개수를 변수로 하는 DP로 해결할 수 있습니다.
각 경우의 기댓값을 구하는 경우만 알아보겠습니다.
아직 $M_i$개 만큼 피어나지 않은 꽃 중 하나가 피어날 확률을 $p$라 합시다.
이때 해당 꽃 중 하나가 피어날 때 까지 시행 횟수의 기댓값은 $1/p$입니다.
증명
확률 $p$인 경우가 일어날 때 까지의 시행 횟수의 기댓값을 구해봅시다.
한 번에 일어나는 경우 $p$, 두 번에 일어나는 경우 $(1 - p)p$, 세 번에 일어나는 경우 $(1 - p)^2p$, $\cdots$
위를 모두 합하면 $\sum_{k = 0}^\infty (k + 1)(1 - p)^kp$로 나타낼 수 있습니다.
확률 앞의 횟수 ($k + 1$)이 $1$이 되도록 전부 분할하면
$\sum_{k = 0}^\infty (1 - p)^kp + \sum_{k = 1}^\infty (1 - p)^kp + \sum_{k = 2}^\infty (1 - p)^kp + \cdots$로 나타낼 수 있습니다.
각 항을 등비수열의 합 공식을 이용해 다시 쓰면 $1 - p + (1 - p)^2 + (1 - p)^3 + \cdots$입니다.
다시 등비수열의 합 공식을 이용해 다시 쓰면 $1/p$입니다. $\blacksquare$
기댓값
아직 $M_i$만큼 피어나지 않은 꽃들의 $a_i$를 모두 합한 값을 $A$이라 합시다.
$i$번째 꽃이 하나 더 피고 나서, 모든 꽃이 $M_i$만큼 피어나게 하기 위한 기댓값을 $E_i$라 합시다.
그렇다면 현재 상태에서의 기댓값은 $1/p + \sum (E_i \times a_i / A’)$이 됩니다.
코드
파이썬에서 튜플과 딕셔너리를 사용하면 시간 초과를 받으므로 6자리 11진수를 이용해서 DP를 계산하면 됩니다.
1 | |