東京海上日動2020 C - Lamps

問題原文

atcoder.jp

解法

１回分の操作はいもす法を使うことで でできる。 これを 回行うので、 、さてどう高速化するか。。。となるけど、実は愚直にやっても 回程度の操作で に収束する。
ので、実際には で答えを求められる。

のケースを手計算してたら気がついた。
一番操作回数が多くなるのは で、両端が一番 になるまで時間がかかる、という事実をもとにちゃんと観察すればまだはやく気づけたかも。（だいたい倍々になっていく）

実装

from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))


def calc_imos(arr):
    imos = [0] * (N + 1)
    for i, a in enumerate(arr):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        imos[l] += 1
        imos[r + 1] -= 1
    imos = list(accumulate(imos))
    return imos[:-1]


for k in range(min(50, K)):
    A = calc_imos(A)
print(*A, sep=' ')

感想

えーん、もう少し早く解きたかった。