ABC370振り返り

前回の振り返り

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

今週も無事A,B,Cの3完(0ペナ)

A

l,rが同じならInvalid
それ以外は指示に従う

ソースコード

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():
    l, r = rLI()
    if l == r:
        print("Invalid")
    elif l:
        print("Yes")
    else:
        print("No")
        
    
    
if __name__ == '__main__':
    main()

B

N点のグラフとして見立てるイメージで実装
流石にこのレベルのグラフは解ける

ソースコード

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()
    A = {i+1:{j:a for j,a in enumerate(rLI(),start=1)} for i in range(N)}
    ans = 1
    for i in range(1,N+1):
        if ans >= i:
            ans = A[ans][i]
        else:
            ans = A[i][ans]
    print(ans)
if __name__ == '__main__':
    main()

C

1文字ずつ置き換えたものを用意して
辞書順に一番若いものを配列に加える

ソースコード

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)

def main():
    S = rS()
    t = rS()
    X = []
    N = len(S)
    s = S
    for _ in range(N):
        if s == t: break
        y = "z"*N
        e = []
        for j in range(N):
            if s[j] == t[j]:continue
            s_list = list(s)
            s_list[j] = t[j]
            w = ''.join(s_list)
            e.append(w)
            if w == t:
                q = t
                break
            if w not in X:
                y=min(y,w)
        else:
            q = y
        s = q
        X.append(q)
        del y
    
    print(len(X))
    for x in X:
        print(x)
    
if __name__ == '__main__':
    main()

D

座標系の問題つらい、時間かけたけど無理だった

E

E問題の動的計画法はまだ難しい…

F

これもダブリングなんだね

G

面白そうだったけど正解者数極端に少ないのでパス

まとめ

D問題が座標系で撃沈していたが
E問題の動的計画法をチャレンジすべきだったか
判断は難しいところ