ABC372振り返り

前回の振り返り

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

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

A

文字列の置換

ソースコード

main.py

print(input().replace(".",""))

B

大きいやつから引けばいいけど
aの最大値が10じゃなくて9と勘違いして1ペナ

ソースコード

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():
    M = rI()
    s = M
    N = 0
    a = 10
    A = []
    while s>0:
        b = 3**a
        if s >= b:
            s -= b
            N += 1
            A.append(a)
        else:
            a-=1
    print(N)
    print(*A)
    
if __name__ == '__main__':
    main()

C

置き換えた文字の場所からピンポイントに文字の判定をする。

文字列の置換に苦戦して時間かかったし
デバッグ用の連結が原因なの気づかずTLE2回出したorz

ソースコード

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 = "ABC"
def main():
    N, Q = rLI()
    S = rS()
    A = [list(S[i:i+3]) for i in range(N-2)]
    is_ABC = ["".join(a) == t for a in A]
    ans = sum(is_ABC)
    _s = S[:]
    
    # err(_s)
    # err(*["".join(a) for a in A])
    # err(is_ABC)
    # err(ans)
    for _ in range(Q):
        x, c = rLS()
        x = int(x)-1
        # _s = _s[:x]+c+_s[x+1:]
        for i in range(3):
            j = x-2+i
            if j >= N-2 or j < 0: continue
            A[j][2-i] = c
            a = "".join(A[j])
            chk = a == t
            if not chk and is_ABC[j]:
                ans -= 1
            elif chk and not is_ABC[j]:
                ans += 1
            is_ABC[j] = chk
        # err(_s)
        # err(*["".join(a) for a in A])
        # err(*is_ABC)
        print(ans)

if __name__ == '__main__':
    main()

D

C解いたあとF問題特攻してTLE出したあと
残り5分もなかったので何もできなかったorz

E

グラフの問題はできませんorz

F

グラフの問題は…だけどDPの匂い(?)がしたので
とりあえず実装したけどTLE
どうやら配列を使い回す工夫が必要だったみたい

ソースコード

TLEコード

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)

class ModInt:
    def __init__(self, x, mod = 998244353):
        self.mod = mod
        self.x = x.x if isinstance(x, ModInt) else x % self.mod
    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__
    __add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
    __sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
    __mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
    __pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, self.mod))
    __truediv__ = lambda self, other: ModInt(self.x * pow(ModInt(other).x, self.mod - 2, self.mod))
    __floordiv__ = lambda self, other: ModInt(self.x // ModInt(other).x)
    __lt__ = lambda self, other: self.x < ModInt(other).x
    __gt__ = lambda self, other: self.x > ModInt(other).x
    __le__ = lambda self, other: self.x <= ModInt(other).x
    __ge__ = lambda self, other: self.x >= ModInt(other).x
    __eq__ = lambda self, other: self.x == ModInt(other).x
    __ne__ = lambda self, other: self.x!= ModInt(other).x

class mint(ModInt):
    pass

def main():
    N, M, K = rLI()
    G = [[(i+1)%N] for i in range(N)]
    for _ in range(M):
        i,j = rLI()
        G[i-1].append(j-1)

    dp = [[mint(0) for j in range(N)] for i in range(K+1)]
    
    dp[0][0] = mint(1)
    nL = {0}
    for k in range(K):
        L = nL
        nL = set()
        for i in L:
            for j in G[i]:
                dp[k+1][j] += dp[k][i]
                nL.add(j)           
    ans = mint(0)
    for k in dp[K]:
        ans += k
    print(ans)
    
if __name__ == '__main__':
    main()

G

数検やってたとき似たような方程式(不定方程式?)
出てきて苦戦した記憶が蘇った。
ユークリッドの互除法使うんだっけ？

まとめ

C問題に時間をかけたのが結構痛い
もう少し文字列を扱う訓練が必要

あとDPだという直感があったとしても
残り30分くらいでF問題特攻する意義があったのかどうかは気になるところ。