【今日の精進】ARC076F - Exhausted?

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

問題リンク

atcoder.jp

問題概要

ゲームのやりすぎで腰を痛めた*1 人の高橋くんたちを、数直線上の の位置にある 個の椅子に座らせようとしてるよ。

ただ、 人目の高橋くんには座標 より左か、座標 より右の椅子に座りたいというこだわりがあるよ。

必要なら任意の実数座標に椅子を追加できるとき、全員の要望を満たすための追加すべき椅子の個数の最小値を求めてね。

解法

椅子は必ず座標 に追加するとして良いです。この位置には、誰でも座ることができるためです。

また、椅子をあらかじめ 個追加して、 が成立するようにします。

若干唐突ですが、Hallの定理を活用しましょう。

これは、今回の問題で言うと「任意の高橋くんの部分集合において、誰か一人でも座れる椅子の個数が、高橋くんの人数以上である」ことが条件です。

ただまあ、当然ながらすべての部分集合について調べ上げるのは不可能です。そのため、別の方法で確かめられないか考えましょう。

例えば、「左を固定する」方法が考えられます。こうすると、右の候補は狭いものから順に試していけば良いです。そして、足りなくなったらその分だけ椅子を追加してやりましょう。

まあこれでも なので間に合いはしないのですが、例えばこれを区間加算区間minの遅延セグメント木によって高速化すると、 なので、これは間に合います、

提出コード

INF=pow(2,61)-1

class LazySegmentTree():
    def __init__(self,default,operator,e,mapping,composition,delay):
        if type(default)==int:
            self.size=default
        else:
            self.size=len(default)
        self.ope=operator
        self.E=e
        self.mapp=mapping
        self.comp=composition
        self.DEL=delay
        self.bit=1
        while self.size>self.bit:
            self.bit=self.bit<<1
        self.seg=[self.E for i in range(self.bit*2)]
        self.delay=[self.DEL for i in range(self.bit*2)]
        if type(default)!=int:
            for i,j in enumerate(default,self.bit):
                self.seg[i]=j
        for i in range(self.bit-1,0,-1):
            self.seg[i]=self.ope(self.seg[i<<1],self.seg[(i<<1)+1])
    
    def __setitem__(self,pos,val):
        if type(pos)==int:
            pos+=self.bit
            self._prop(pos)
            self.seg[pos]=self.mapp(val,self.seg[pos])
            self.delay[pos]=self.comp(val,self.delay[pos])
            self._up(pos)
            return
        left=pos.start
        if left==None:
            left=0
        right=pos.stop
        if right==None:
            right=self.size
        left+=self.bit
        right+=self.bit
        l0=left//(left&-left)
        r0=right//(right&-right)
        self._prop(l0)
        self._prop(r0)
        while left<right:
            if left%2==1:
                self.seg[left]=self.mapp(val,self.seg[left])
                self.delay[left]=self.comp(val,self.delay[left])
                left+=1
            if right%2==1:
                right-=1
                self.seg[right]=self.mapp(val,self.seg[right])
                self.delay[right]=self.comp(val,self.delay[right])
            left=left>>1
            right=right>>1
        self._up(l0)
        self._up(r0)
    
    def _prop(self,pos):
        use=[]
        while pos>1:
            pos>>=1
            use.append(pos)
        for i in range(len(use)-1,-1,-1):
            pos=use[i]
            self.seg[pos<<1]=self.mapp(self.delay[pos],self.seg[pos<<1])
            self.delay[pos<<1]=self.comp(self.delay[pos],self.delay[pos<<1])
            self.seg[(pos<<1)+1]=self.mapp(self.delay[pos],self.seg[(pos<<1)+1])
            self.delay[(pos<<1)+1]=self.comp(self.delay[pos],self.delay[(pos<<1)+1])
            self.delay[pos]=self.DEL
    
    def _up(self,pos):
        while pos>1:
            pos=pos>>1
            self.seg[pos]=self.ope(self.seg[pos<<1],self.seg[(pos<<1)+1])
    
    def __getitem__(self,pos):
        if type(pos)==int:
            self._prop(pos+self.bit)
            return self.seg[pos+self.bit]
        left=pos.start
        if left==None:
            left=0
        right=pos.stop
        if right==None:
            right=self.size
        left+=self.bit
        right+=self.bit
        ret_left=self.E
        ret_right=self.E
        l0=left//(left&-left)
        r0=right//(right&-right)
        self._prop(l0)
        self._prop(r0)
        while left<right:
            if left%2==1:
                ret_left=self.ope(ret_left,self.seg[left])
                left+=1
            if right%2==1:
                right-=1
                ret_right=self.ope(self.seg[right],ret_right)
            left=left>>1
            right=right>>1
        return self.ope(ret_left,ret_right)

def mapp(f,x):
    return f+x

def comp(f,g):
    return f+g

N,M=map(int,input().split())
ans=max(0,N-M)
M=max(N,M)
tak=[]
for i in range(N):
    L,R=map(int,input().split())
    tak.append((L,M-R+1))
tak.sort()
seg=LazySegmentTree(range(M),min,INF,mapp,comp,0)
for l,r in tak:
    seg[r:]=-1
    if l<-seg[:]:
        ans+=-seg[:]-l
        seg[:]=-seg[:]-l
print(ans)

Submission #47584743 - AtCoder Regular Contest 076

感想

赤Diff自力AC、流石に気持ちいい…*2

*1:まじでなにこれ!?

*2:Hallの定理使うのは知ってたんだけどそれは許して…