ABC372Fを解いた【inline DP】

筆者はレート800前後の茶～緑コーダ

ABC372のF問題を解いていく

実装コード

普通にDPをした場合はTLEしてしまうので計算量を減らす必要があるらしい。

必ず+1の頂点には辺が付いているので
値を使い回すようにDPを組めばいいみたい。

そうした場合イレギュラーのM個の辺と
N番目の値を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 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 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 = []
    for _ in range(M):
        G.append(rLI1())

    dp = [mint(0) for _ in range(N+K)]
    
    dp[K] = mint(1)
    for k in range(K,0,-1):
        add = []
        for i,j in G:
            add.append((j,dp[i+k]))
        dp[k-1]=dp[k+N-1]
        for j,v in add:
            dp[j+k-1] += v
    ans = mint(0)
    for i in range(N):
        ans += dp[i]
    print(ans)
    # err(*(int(dp[i])for i in range(N)))
    
if __name__ == '__main__':
    main()

まとめ

ABC372Fを解いた。inlineDPを実装した。

成約数やグラフの構造を鑑みて計算を減らす工夫が必要なのは流石F問題といったところ。

このような問題を時間内で解ける日はいつ来るのだろうか。