ABC371振り返り

前回の振り返り

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

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

T = (0,1),(0,2),(1,2)
def main():
    S=rLS()
    old = [0]*3
    for t,s in zip(T,S):
        if s == ">":
            old[t[0]] += 1
        else:
            old[t[1]] += 1
    for i,a in enumerate("ABC"):
        if old[i] == 1:
            print(a)
    
if __name__ == '__main__':
    main()

B

フラグをデフォルトで立てといて
生まれたのが男子かつフラグが立っているときのみYesと出力する
男子が生まれたらフラグを折る

ソースコード

main.py

import sys
from collections import defaultdict
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():
    _, M = rLI()
    d = defaultdict(lambda: True)
    for _ in range(M):  
        A, B = rLS()
        if B=="M" and d[A]:
            d[A] = False
            print("Yes")
        else:
            print("No")
    
if __name__ == '__main__':
    main()

C

グラフの拒絶反応がでてとけなかった😅
そっちよりD解いてる人多かったし許して

D

累積和と二分探索の合わせ技

ソースコード

main.py

import sys
from bisect import bisect_left,bisect_right
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()
    X = rLI()
    P = rLI()
    S = [0]+P[:]
    for i in range(N):
        S[i+1] = S[i+1]+S[i]
    
    Q = rI()
    
    for _ in range(Q):
        L,R = rLI()
        i=bisect_left(X,L)
        j=bisect_right(X,R)
        print(S[j]-S[i])
                
    
if __name__ == '__main__':
    main()

E

動的計画法とか累積和の応用かなとおもって
色々試したけどできなかったorz

余事象を考えるのかYO！

F

動的計画法かと思ったけど遅延セグ木とかの方なのね

G

解説チラ見したら$2^{2367}$とかいう巨大数がでて戦慄

まとめ

今回はD問題が解けたから良いが
グラフの問題の拒絶反応をなんとかしないといけないですね