ABC154Dを解いた【確率,累積和】

筆者はレート800前後の茶～緑コーダ

ABC154のD問題を解いていく

実装コード

p面サイコロの期待値は
(p+1)/2で出せる

あとはK区間の総和なので累積和して最大値を記憶すればOK

main.py

from itertools import accumulate
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)


def main():
    N, K = rLI()
    P = rLI()
    S = [0]+list(accumulate(map(lambda p:(p+1)/2,P)))
    m = 0
    for i in range(K,N+1):
        x = S[i] - S[i-K]
        if x > m:
            m = x
    print(m)
    
if __name__ == '__main__':
    main()

まとめ

確率や期待値の問題が得意ではないが
こういうシンプルな解法ならできるようになってきた