【今日の精進】ARC070E - NarrowRectangles

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

問題リンク

atcoder.jp

問題概要

個の長方形が縦一列に並んでいるよ。

それぞれの長方形をスライドして連結にするとき、スライドする距離の最小値を求めてね。

解法

普通のDPは当然間に合いません。

しかし、そのDPを観察すると、やってることは「区間minをとる」ことと「ある地点からの距離を足す」ことです。

これは、どちらも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

N=int(input())
func=SlopeTrick()
wide=0
for i in range(N):
    l,r=map(int,input().split())
    func.slide_min(l-r,wide)
    func.add_abs_a(l)
    wide=r-l
print(func.get_min())

Submission #47999071 - AtCoder Regular Contest 070

感想

銅Diffさん…？