ABC385Dを解いた【SortedSet,二分探索】

筆者はレート800前後の茶～緑コーダ

ABC385当日にACできなかったD問題を解いていく

ABCの問題を解いていく

実装コード

SortedSetで家の位置を管理したあとに、順番に巡回する
通過した家はSetから取り除く必要があるようだ

main.py

from bisect import bisect_left, bisect_right
from collections import defaultdict

from sortedcontainers import SortedSet

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
move = {c:(x,y)for c,y,x in zip("DRUL",dy,dx)}

dhx = defaultdict(SortedSet)
dhy = defaultdict(SortedSet)

visited = set()

def main():
    N, M, X, Y = rLI()
    for _ in range(N):
        x, y = rLI()
        dhx[x].add(y)
        dhy[y].add(x)
    
    cx, cy = X, Y

    for _ in range(M):
        d, c = rLS()
        c = int(c)
        nx, ny = move[d]
        mx, my = nx * c, ny * c

        if nx == 0:
            hs = dhx[cx]
            l, r = sorted([cy,cy+my])
            li = bisect_left(hs, l)
            ri = bisect_right(hs, r)-1
            if li <= ri:   
                visited.update((cx, hy) for hy in hs[li:ri+1])
                for hy in hs[li:ri+1]:
                    dhx[cx].remove(hy)
                    dhy[hy].remove(cx)
        else:
            hs = dhy[cy]
            l, r = sorted([cx,cx+mx])
            li = bisect_left(hs, l)
            ri = bisect_right(hs, r)-1 
            if li <= ri:   
                visited.update((hx, cy) for hx in hs[li:ri+1])
                for hx in hs[li:ri+1]:
                    dhx[hx].remove(cy)
                    dhy[cy].remove(hx)

        # err(d,c,l,r,hs[li:ri+1])
        cx+=mx
        cy+=my
    
    print(cx, cy, len(visited))

    
if __name__ == '__main__':
    main()

まとめ

通過した家をSetから取り除く発想がなくて撃沈。

そして何よりも恥ずるべきなのは単純な誤字に全く気づかないところ

            l, r = sorted([cx,cx+my]) # 誤
            l, r = sorted([cx,cx+mx]) # 正

こういう誤字があるのでコピペはしたくないのに
コピペしないようにすると
余計処理を考えるのに苦労するのが非常に困る。