ABC385振り返り

前回の振り返り

今日はABC385開催日だったので参加結果を振り返る

今週はA,Bの2完(0ペナ)

A

脳筋if文

ソースコード

main.py

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)

def main():
    A, B, C = rLI()
    ans = A==B==C or A+B==C or A==B+C or A+C==B
    print('Yes' if ans else 'No')
    
if __name__ == '__main__':
    main()

B

大分gridは慣れてきたがやはり実装に時間かかる…

ソースコード

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from itertools import product, accumulate, groupby
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:(y,x)for c,y,x in zip("URDL",dy,dx)}

def main():
    H, W, X, Y = rLI()
    grid = [list(rS()) for _ in range(H)]
    T = rS()
    visited = [[False]*W for _ in range(H)]
    vcnt = 0
    
    cx = X - 1
    cy = Y - 1
    if grid[cx][cy] == "@" and not visited[cx][cy]:
        visited[cx][cy] = True
        vcnt += 1
    for t in T:
        nx, ny = move[t]
        # err((cx+1,cy+1),t,(nx,ny),grid[cx][cy],grid[cx+nx][cy+ny])
        if grid[cx+nx][cy+ny] == "#":
            continue
        cx += nx
        cy += ny
        # err((cx+1,cy+1),grid[cx][cy])
        if grid[cx][cy] == "@" and not visited[cx][cy]:
            visited[cx][cy] = True
            vcnt += 1
        
    print(cx+1,cy+1,vcnt)
    
if __name__ == '__main__':
    main()

C

高さごとにビルの位置を取って最大の等差数列をどうやって作るのみたいな
複雑に考えすぎてわけわかんなくなりパス。

N<=3000なんだからO(N^2)でもいけるのに…

D

Bの応用で通った家をSetで管理するみたいな手法を試したが
無事にWA,TLEを貰い玉砕

ソースコード

WA,TLEコード

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from itertools import product, accumulate, groupby

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) 
            visited.update((cx, hy) for hy in hs[li:ri+1])
            for _ in range(ri-li):
                dhx[cx].pop(li)
        else:
            hs = dhy[cy]
            l, r = sorted([cx,cx+my])
            li = bisect_left(hs, l)
            ri = bisect_right(hs, r) 
            visited.update((hx, cy) for hx in hs[li:ri+1])
            for _ in range(ri-li):
                dhx[cy].pop(li)
        # err(d,c,l,r,hs[li:ri+1])
        cx+=mx
        cy+=my
    
    print(cx, cy, len(visited))

    
if __name__ == '__main__':
    main()

E

ユ木とかいうネーミングセンスは面白いが
グラフはまだBFSぐらいしかできませんorz

F

ここの数学頑張ればもしやがあった…？

G

数え上げでかつmodintとか言う時点で高度すぎる話

まとめ

入緑以来の屈辱の2完、
クリスマス前で散々な結果になってしまい本当に辛いです…

とりあえずCはN<=3000とかいうO(N^2)のアルゴリズムでもACできそうな成約なのに
適当に作ってトライしなかったのが大きな判断ミスだと思う