한 게임에는 다양한 캐릭터가 등장하는 가챠 시스템이 존재한다.
플레이어는 총 K번의 뽑기를 수행할 수 있으며, 각 캐릭터는 최초로 획득했을 때만 컬렉션 점수에 기여한다.
가챠 배너에는 N종류의 캐릭터가 존재하며, 각 캐릭터는
- 컬렉션 점수
Vi - 등장 확률
Pi
를 가진다.
각 뽑기는 서로 독립적으로 이루어진다.
플레이어는 K번의 뽑기 후 얻을 수 있는 기대 컬렉션 점수를 계산하고자 한다.
기대 컬렉션 점수는 모든 캐릭터에 대해
(해당 캐릭터를 최소 1번 이상 획득할 확률) × (캐릭터 점수)
의 합으로 정의된다.
K번의 뽑기 후 기대 컬렉션 점수를 구하여라.
첫째 줄에 캐릭터의 수 N과 뽑기 횟수 K가 주어진다.
이후 N개의 줄에 걸쳐 각 캐릭터의 정보 Vi Pi가 주어진다.
Pi는 백분율이 아닌 실수 확률이다.
모든 확률의 합은 정확히 1이다.
기대 컬렉션 점수를 출력한다.
정답과의 절대 오차 또는 상대 오차가 10^-6 이하이면 정답으로 인정한다.
- 1 ≤ N ≤ 200,000
- 1 ≤ K ≤ 10^9
- 1 ≤ Vi ≤ 10^9
- 0 < Pi < 1
- 모든
Pi의 합 = 1
3 2
100 0.5
200 0.3
300 0.2
2 3
50 0.8
100 0.2
270.000000
98.800000
각 캐릭터를 최소 한 번 이상 획득할 확률은
100점 캐릭터 : 1 - (1 - 0.5)^2 = 0.75
200점 캐릭터 : 1 - (1 - 0.3)^2 = 0.51
300점 캐릭터 : 1 - (1 - 0.2)^2 = 0.36
따라서 기대 컬렉션 점수는
100 × 0.75
+ 200 × 0.51
+ 300 × 0.36
= 285
이다.
각 캐릭터를 최소 한 번 이상 획득할 확률은
50점 캐릭터 : 1 - (0.2)^3 = 0.992
100점 캐릭터 : 1 - (0.8)^3 = 0.488
따라서 기대 컬렉션 점수는
50 × 0.992
+ 100 × 0.488
= 98.4
이다.
어떤 캐릭터의 등장 확률이 Pi일 때,
K번의 뽑기 동안 해당 캐릭터를 한 번도 얻지 못할 확률은
(1 - Pi)^K
이다.
따라서 최소 한 번 이상 획득할 확률은
1 - (1 - Pi)^K
가 된다.
기대값의 선형성에 의해 각 캐릭터의 기대 기여도를 독립적으로 계산하여 더할 수 있다.
즉,
Expected Score
=
Σ Vi × (1 - (1 - Pi)^K)
를 계산하면 된다.
모든 캐릭터에 대해 한 번씩 계산하면 되므로 시간 복잡도는
O(N)
이다.
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
answer = 0.0
for _ in range(N):
value, prob = input().split()
value = int(value)
prob = float(prob)
answer += value * (1.0 - pow(1.0 - prob, K))
print(f"{answer:.6f}")