Last time If you have a recommended problem, please leave a comment or twitter. Today is 30 days.
#30 ABC154-D
** Thoughts ** When I calculated the expected value of $ K $ dice that are straightforwardly continuous, I got TLE. Even if I submitted it with PyPy, it was TLE, so I read the explanation. If you use the cumulative sum, you can reduce the amount of calculation. The expected value can be calculated with $ \ frac {1} {2} (p [i] + 1) $. Cumulative sum is implemented using numpy. I love numpy
import numpy as np
n, k = map(int,input().split())
p = list(map(int,input().split()))
e = [(i+1)/2 for i in p]
e = np.cumsum(e)
e = np.append(0,e)
ans = 0
for i in range(n-k+1):
ans = max(e[i+k]-e[i],ans)
print(ans)
Detailed explanation of cumulative sum
** Thoughts ** The for statement calculates the expected value for each die roll. If the dice roll is K or less, toss the coin. Calculate the number of coin tosses with while and count $ \ frac {1} {2} $.
n, k = map(int,input().split())
ans = 0
for i in range(1,n+1):
count = 0
if i < k:
while i < k:
i *= 2
count += 1
ans += 1/n * (1/2)**count
print(ans)
I am not good at problems of probability and expected value, so I have to review the number A. See you again, good night.
Recommended Posts