More than 3 years have passed since last update.

競技プログラミングでTLEのときに高速化できるアルゴリズム

Last updated at 2020-04-13Posted at 2020-04-07

暇があるときに更新する、競プロをやっているときに気づいたことの備忘録

Level1

配列の部分和を求め比較する必要がある際、一回づつ部分和を求めるのではなく、前項(i項まで)の和にi+1の項を加えてそこから部分和の範囲を考慮したほうが早い。例上記が正解、下記だとTLEになる。

ABC_D_Dice_in_Line.py

for i in range(k, len(p)):
    saveSum = saveSum + p[i] - p[i - k]
    if saveSum > M:
        M = saveSum

ABC_D_Dice_in_Line.py

for i in range(len(p) - k + 1):
    # 一回づつlistの和を求めているから計算量が多い
    savesum = sum(p[i:i + k])
    if savesum > M:
        M = savesum

あとで書く