【ABC】 182 D - Wandering

解説読むとめっちゃ簡単ですよね...。なぜ解けなかったのか...。こちらの動画のコードを丸パクリさせて頂きました。他の人のコードを読むのも勉強になります。

N = int(input())
N += 1
A = [0] + list(map(int, input().split()))

Aの要素iまでの増加分を足し合わせた累積和をaccum_sumとしています。ステップiを行った時に増減する幅が格納されています。

accum_sum = A[:]
for i in range(1, N):
    accum_sum[i] += accum_sum[i-1]

入力例1の場合は

print(accumulation_sum) 
[0, 2, 1, -1]

ステップiを行った後の実際の座標は初期位置をnow=0としてaccumulation_sumの要素をそれぞれ足せば求まります。

now = 0
for i in range(1, N):
    now += accum_sum[i]
    print(i, now)

出力

1 2
2 3
3 2

次にステップiで移動できる最大幅を計算します。これはステップiまでのaccum_sumの最大値を計算すれば良いです。全体に対してmax(accumulation_sum)ではない点に注意して下さい。

accum_max = accum_sum[:]
for i in range(1, N):
    accum_max[i] =max(accum_max[i], accum_max[i-1])
print(accum_max) # [0, 2, 2, 2]

後はこれらを元に全ステップで到達できる座標の最大値を計算して行きます。

ans = 0
now = 0
for i in range(1, N):
    ans = max(ans, now+accum_max[i])
    now += accum_sum[i]
print(ans) # 5

コード全体は以下のUpしました。

butch’s blog