ABC384振り返り

前回の振り返り
https://qiita.com/comet725/items/fa47a91b81dca6e0d15b

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

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

A

単純な置換

ソースコード

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():
    _,c1,c2 = rLS()
    S = list(rS())
    ans = [c2 if s != c1 else c1 for s in S]
    
    print("".join(ans))
    
if __name__ == '__main__':
    main()

B

上限下限以内なら加算

ソースコード

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)


rated = {1:(1600,2799),2:(1200,2399)}

def main():
    N, R = rLI()
    rate = R
    for _ in range(N):
        D, A = rLI()
        low,up=rated[D]
        if low<=rate<=up:
            rate += A
    print(rate)
    
if __name__ == '__main__':
    main()

C

bit全探索してdefaultdictに入れる
dictでは中にリストを作らせといて
追加するとき辞書順になるよう挿入

ソースコード

main.py

import sys
from itertools import product
from collections import defaultdict
from bisect import insort_right
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)

All = 'ABCDE'
d = defaultdict(list)
points = set()

def main():
    X = rLI()
    for b in product([0,1],repeat=5):
        name = ''.join(s for s,a in zip(All,b) if a==1)
        if name == '':continue
        point = sum(p for p,a in zip(X,b) if a==1)
        points.add(point)
        insort_right(d[point],name)
    for p in sorted(points,reverse=True):
        # err(p,d[p])
        for name in d[p]:
            print(name)
    
if __name__ == '__main__':
    main()

D

とりあえず総和をざっくり加算して
調整分を前後の累積和で調整したけどWA

ソースコード

WAコード

main.py

import sys
from itertools import accumulate
from bisect import bisect_left
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():
    N, X = rLI()
    A = rLI()
    
    S = list(accumulate(A))
    Sr = list(accumulate(A[::-1]))
    m = S[-1]
    M = m*(X//m+1)
    err(X,M,m,X//m)
    for s in S:
        # err(s,M-s-X)
        y = M - s - X 
        if y == 0:
            print("Yes")
            return
        else:
            zi = bisect_left(Sr,y)
            for i in range(-2,3):            
                s1 = Sr[i+zi]
                z=y-s1
                if z == 0:
                    print("Yes")
                    return
                if z < 0:
                    break
    print("No")
        
if __name__ == '__main__':
    main()

E

幅優先と優先度付きキューを使って
吸収できるスライムを探したがWA…
なんでぇ…

ソースコード

WAコード

main.py

import sys
import heapq
from collections import deque
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)


class Minheapq(object):
    q = []
    def push(self, v):
        heapq.heappush(self.q, v)

    def pop(self):
        return heapq.heappop(self.q)

    def get(self):
        return self.q[0]

    def values(self):
        for _q in self.q:
            yield _q

dy = [0, -1, 0, 1, 0]
dx = [0, 0, 1, 0, -1]

def out_of_bounds(y, x, h, w):
    return y < 0 or y >= h or x < 0 or x >= w


def main():
    H, W, X = rLI()
    P, Q = rLI1()
    A = [rLI() for _ in range(H)]
    p = 0
    q = Minheapq()
    q.push((float('inf'),-1,-1))
    visited = set()
    queue = deque([(P,Q)])
    while queue:
        cur = queue.popleft()
        y,x = cur
        cp = A[y][x]
        p += cp
        e = p/X
        # err(cur,p,e)
        visited.add(cur)
        while q.get()[0] < e:
            x,*nxt=q.pop()
            queue.append(tuple(nxt))
            # err(list(sorted(q.q)))
        for i0,j0 in zip(dy,dx):
            i=y+i0
            j=x+j0
            if out_of_bounds(i,j,H,W):continue
            if (i,j) in visited:continue
            # err((i,j), A[i][j])
            # err(i,j,cp,e)
            cp = A[i][j]
            visited.add((i,j))
            if cp < e:                    
                queue.append((i,j))
            else:
                q.push((cp,i,j))
    print(p)
    
    
if __name__ == '__main__':
    main()

F, G

ダブルシグマつらい

まとめ

C問題までは20分程度解けたが
D,Eの問題がどちらもWA抜けなかった

解法が予想付いたのに解けないのが一番つらい😢