【今日の精進】ARC123D - Inc, Dec - Decomposition

毎日格上の問題を倒すやつの76日目です。

問題リンク

atcoder.jp

問題概要

整数列 が与えられるよ。

広義単調増加列 と広義単調減少列 で、 が成り立つようなものを考えるよ。

の要素の絶対値の和の最小値を求めてね。

解法

例の如く愚直なDPを考えると、要素のスライド、累積最小値、絶対値の加算をしたくなります。

これはSlopeTrickで簡潔にできることなので、それを素直に実装すれば終わりです。

提出コード

from heapq import heappop,heappush
class SlopeTrick:
    def __init__(self):
        self.lf=[float("inf")]
        self.ri=[float("inf")]
        self.min_f=0
        self.add_L=0
        self.add_R=0
    
    def get(self,x):
        ret=self.min_f
        for i in self.lf:
            ret+=max(0,(-i+self.add_L)-x)
        for i in self.ri:
            ret+=max(0,x-(i+self.add_R))
        return ret
    
    def get_min(self):
        return self.min_f
    
    def add_a(self,a):
        self.min_f+=a
    
    def add_x_minus_a(self,a):
        self.min_f+=max(0,(-self.lf[0]+self.add_L)-a)
        heappush(self.lf,-(a-self.add_L))
        heappush(self.ri,-heappop(self.lf)+self.add_L-self.add_R)

    def add_a_minus_x(self,a):
        self.min_f+=max(0,a-(self.ri[0]+self.add_R))
        heappush(self.ri,a-self.add_R)
        heappush(self.lf,-(heappop(self.ri)+self.add_R-self.add_L))
    
    def add_abs_a(self,a):
        self.add_x_minus_a(a)
        self.add_a_minus_x(a)
    
    def cum_min(self):
        self.lf=[]
    
    def cum_min_right(self):
        self.ri=[]
    
    def move(self,v):
        self.add_L+=v
        self.add_R+=v
    
    def slide_min(self,a,b):
        self.add_L+=a
        self.add_R+=b

def add(f,num):
    f.add_abs_a(num)
    f.add_abs_a(0)

N=int(input())
A=list(map(int,input().split()))
f=SlopeTrick()
add(f,A[0])
for i in range(N-1):
    f.move(max(0,-A[i]+A[i+1]))
    f.cum_min_right()
    add(f,A[i+1])
print(f.get_min())

Submission #48201279 - AtCoder Regular Contest 123

感想

ABCかARCかだけで難易度に天地の差が…