競プロ典型 90 問：042 - Multiple of 9（★4）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/15
• 結果：解けなかった
• 時間：30分

考えたこと

• DPっぽい
• 一文字足して行く感じ

公式解説

https://twitter.com/e869120/status/1394423616805097477

解説を読んだふりかえり

メモ化再帰で書いてみた

• 個人的にDPよりも再帰のほうがわかりやすいので、再帰で書いてみた
• スルッとかけたけど、sys.setrecursionlimit(10**6) をつけ忘れて REが取れなかった。
• Windows環境で実行すると、99999 とか5桁規模を入力すると、原因不明だけど無言で終了する。何も出力してくれないし、エラーにもならない。
• AtCoder環境だと問題ないようで、AC。

ソース

import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)
K = int(input())
MOD = 10**9 + 7

# メモ化再帰
@lru_cache(maxsize=1000000)
def f(n):
    # 終了条件
    if n==0:
        return 1
    ret = 0
    # f(n-1), ... f(n-9)の合計
    for i in range(max(n-9,0), n):
        ret += f(i)
        ret %= MOD
    return ret

ans = f(K) if K%9==0 else 0
print(ans)

追記＠20211017

DP版も書いてみた。

個人的には再帰のほうが理解しやすいな。。。 でも、DPのほうが速度が早いし、Pythonの再帰数設定だとか無言で終了するような挙動もあるし、競プロでは重要スキルな気がしてる。DP力をつけねば。

K = int(input())
DP = [0] * (K+1)
DP[0] = 1
MOD = 10**9 + 7
for i in range(1,K+1):
    st = max(0, i-9)
    DP[i] = sum(DP[st:i])
    DP[i] %= MOD
print(DP[K] if K%9==0 else 0)