反省．ABC3完．レート-51．

解法

問題文の，箇条書きの一行で表されるまとまった動作を，ここではステップと呼ぶ．

2回累積和を取った配列から，各ステップの開始時（終了時）の座標がわかる．あとは，各ステップ内で移動できる最大値を計算しておく．これは累積和の累積MAX．（各ステップの開始時の座標）+（各ステップで移動できる最大値）の最大値が答え．

これを理解するために（発想するために），考えたいことはすべての動作後のロボットの座標は，（各ステップの開始時の座標） + （各動作の移動距離の累積和）で表されるということ．例えば，サンプル2において各ステップの開始時の座標は， $0, -2, -3, -1, 0$ である（手元で書くととてもよい）．ステップ1において， $A_1$ だけ動かすときは， $0 + -2 = -2$ にロボットがいる．ステップ4において， $A_1, A_2, A_3$ だけ動かすときは， $-1 + (-2 + 1 + 3) = -1 + 2 = 1$ である．

今知りたいのは，ロボットの座標の最大値なので，（各ステップの開始時の座標） + （各動作の移動距離の累積和の最大値）を各ステップで計算し，そのうちの最大値を求めればよい．

計算量は $O(N)$ である．

コード

def main():
    from itertools import accumulate
    N = int(input())
    A = [int(i) for i in input().split()]
    S = list(accumulate(A))
    T = list(accumulate([0] + S))

    M = list(accumulate(S, func=max))

    ans = 0
    for i in range(N):
        ans = max(ans, T[i] + M[i])
    print(ans)


if __name__ == '__main__':
    main()

提出コードへのリンク

ACを取ってからだれさんのツイートについて考えてみると，より問題への見通しがすっきりとした，だれさんありがとうございます…！

Q.25Lの容積をもつからっぽの井戸に水を汲みます。
1日につき6Lの水を運べますが、夜は2Lぶん蒸発してしまいます。
井戸から水が溢れるのは何日目でしょう？
↑昔の本で見たこの問題が頭をよぎりました https://t.co/yur7dPIzPn
— だれ (@pro_anyone) 2020年11月8日