Edit

【pythonでABC154を解説】D - Dice in Line

問題概要

問題ページ

D - Dice in Line
D - Dice in Line

問題ページへ移動する

問題文

\(N\) 個のサイコロが左から右に一列に並べてあります。左から \(i\) 番目のサイコロは \(1\) から \(p_i\) までの \(p_i\) 種類の目がそれぞれ等確率で出ます。

隣接する \(K\) 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。

制約

  • \(1 ≤ K ≤ N ≤ 200000\)
  • \(1 ≤ p_i ≤ 1000\)
  • 入力で与えられる値は全て整数

問題の考察

ACコード

import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    ls = [0] * (n + 1)
    tm = 0
    for i, v in enumerate(a):
        ls[i + 1] = (((1 + v) * v) // 2) / v
    ls = list(itertools.accumulate(ls))
    for i in range(k, n + 1):
        tm = max(tm, ls[i] - ls[i-k])
    print(tm)


if __name__ == '__main__':
    solve()

-Edit