ABC364振り返り

前回の振り返り

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

今回はA,B,Cの3完、前回、前々回とA,B,Dの3完だったの今度こそ4完したかったけど残念でした

こんかいは、甘い、しょっぱい、のパラメータをもった量に関する問題が複数あった。(A,C,E)

• 今回のABCのメインテーマ(?)

A

甘いの食べたらフラグを立てて、また甘いのを食べたとき、それが最後じゃなければNo

ソースコード

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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 = rI()
    swt = False
    for i in range(N):
        S = rS()
        if S == "sweet":
            if swt and i < N-1:
                print("No")
                break
            swt = True
        else:
            swt = False
    else:
        print("Yes")

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 rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

d = {
    "L": ( 0,-1),
    "R": ( 0, 1),
    "U": (-1, 0),
    "D": ( 1, 0),
}

def main():
    H, W = rLI()
    si, sj = rLI()
    si -= 1
    sj -= 1 
    
    L = [[False] * W for _ in range(H)]
    for i in range(H):
        S = rS()
        for j, s in enumerate(S):
            if s == "#":
                L[i][j] = True 
    X = rS()
    for i,move in enumerate(X,start=1):
        di, dj = d[move]
        if si+di < 0 or si+di >= W or sj+dj < 0 or sj+dj >= W:
            continue
        elif L[si+di][sj+dj]:
            continue
        else:
            si+=di
            sj+=dj
    print(f"{si+1} {sj+1}")
if __name__ == '__main__':
    main()

C

一番甘いものから食べる高橋くんと一番しょっぱいものから食べる高橋くんのどっちがダウンするかデスゲームするだけ。

一番の甘い、しょっぱいはheapqを最大値系にしたやつを使う。

ソースコード

main.py

import sys
import heapq
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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 Maxheapq:
    def __init__(self):
        self.q = []

    def push(self, v):
        heapq.heappush(self.q, v * -1)

    def pop(self):
        return heapq.heappop(self.q) * -1

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

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

def main():
    N, x, y = rLI()
    A = rLI()
    B = rLI()
    
    qA = Maxheapq()
    qB = Maxheapq()
    for a,b in zip(A,B):
        qA.push(a)
        qB.push(b)
    
    swt = 0
    sal = 0
    
    for i in range(N):
        swt += qA.pop()
        sal += qB.pop()
        if swt>x or sal>y:
            print(i+1)
            break
    else:
        print(N)
if __name__ == '__main__':
    main()

D

E問題がCの応用で行けそうなきがしたのでスルーしちゃった。

E

C問題の逆かな？とかおもいこっちから実装。とりあえずDPで行けるだろうとか思ったけど普通に撃沈…こんなんだったらD問題悩んでたほうがよかったかもしれない。

F

グラフの問題はまだできません定期

G

グラフの問題は(ry

まとめ

E問題がDPで解けそうなやつだったがうまく実装できなかった。
できなそうな問題よりできそうな問題を先にやるのは良いが、問題の難易度をもう少し見積もってから取り掛かるべきだったのが今回の振り返りポイントだと思った。