ABC263 D問題

こんばんは、ぱそきいろ (@takacpu55) / Twitterです。
ABC263のD問題（Left Right Operation）解説の理解が難しかったのでメモを残しておきます。

ちなみに最近土曜日に予定が被ってABC出れない・・・

問題

atcoder.jp

解説

シンプルに解こうと思ったら問題文に沿ってコードを書けばいい気がします。
（最初の方針はこちらを思いついた）
atcoder.jp

もう一つの解説の式変形が詰まったのでメモを残します。

min[0≤x≤y≤N] (Lx+(cum[y]−cum[x])+R(N−y))

Lx：整数xで置き換えた部分の総和
cum[y]-cum[y]：残った部分の総和
R(N-y)：整数yで置き換えた部分の総和

この段階ではminを求めようと思ったらx,yの2変数で探さないといけないのでO(N^2)となります。

=RN+ min[0≤x≤N] (Lx−cum[x]+min[x≤y≤N] (cum[y]−Ry))

定数RNを外に出し、minをx,yで分けてますね。
この中で、min[x≤y≤N] (cum[y]−Ry)の部分はxによらないです。
なので0≤y≤N一度計算して配列に入れておけばO(1)で求めることができます。
よってmin[0≤x≤N]の部分を求めるだけでいいので全体でO(N)で求めることができました。

まとめ

来週はABC参加して4完したい...！

ACしたコード

N,L,R=(map(int,input().split()))
a=list(map(int,input().split()))

#累積和を求めておく
cum=[0]
for i in range(N):
    if i==0:
        cum.append(a[i])
    else:
        cum.append(a[i]+cum[-1])
N=N+1
ycum=[]
for i in range(N):
    ycum.append(cum[i]-R*(i))

#ここでmin[x≤y≤N] (cum[y]−Ry)を改めて求めておく
ycummin=[]
for i in range(N-1,-1,-1):
    if i==N-1:
        ycummin.append(ycum[i])
    else:
        ycummin.append(min(ycummin[-1],ycum[i]))

ycummin.reverse()

xcum=[]
for i in range(N):
    xcum.append(R*(N-1)+L*(i)-cum[i]+ycummin[i])

xcum.append(sum(a))

print(min(xcum))