Pythonで毎日AtCoder #30

はじめに

前回
おすすめの問題があったらコメントやtwitterでリプ飛して欲しいです。
今日で30日です。

#30

ABC154-D

考えたこと
素直に連続する$K$個のサイコロの期待値を計算するとTLEしてしまいました。PyPyで提出してもTLEしたので解説を読みました。
累積和を使えば計算量を減らせるのTLEしません。期待値は$\frac{1}{2}(p[i]+1)$で計算することができます。累積和はnumpyを用いて実装します。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)

累積和の詳しい解説

ABC126-C

考えたこと
for文でサイコロの目ごとに期待値を計算します。もしサイコロの目がK以下ならコイントスします。コイントスする回数をwhileで計算して、$\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)

まとめ

確率とか期待値の問題は苦手なので、数Aの復習しないといけない。ではまた、おやすみなさい。