ABC300Eを解いた【動的計画法,メモ化再帰】

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

ABC300のE問題を解いていく

実装コード

公式解説によると、動的計画法を再帰関数で行うようだ。

つまり、メモ化再帰の出番であり、今回もdefaultdict君に頑張ってもらおう。

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
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

mod = 998244353
inv = lambda x: pow(x, -1, mod)

from collections import defaultdict
m = defaultdict(lambda: -1)
sys.setrecursionlimit(10**7)

def main():
    N = rI()
    
    d = mint(inv(5))
    
    def dp(n):
        # err(n,len(m))
        if n > N:
            return mint(0)
        elif n == N:
            return mint(1)
        elif m[n]==-1:
            p = mint(0)
            for i in range(1,6):
                p += dp(-~i*n)
            m[n] = p*d
        return m[n]
    print(dp(1))
    
if __name__ == '__main__':
    main()

まとめ

ABC300Eを解いた、実装にはメモ化再帰と動的計画法を組み合わせた実装を行った。

最近学んだメモ化再帰と、典型アルゴリズムの定番ともいえる動的計画法の組み合わせて解くのは何かしらのエモーショナルを感じた。

また、この問題みたいに、典型アルゴリズムを2つ組み合わせて実装する必要があるというのがE問題の基本的なスタンスなのかと思えてきたのが感想。