競プロ典型 90 問：050 - Stair Jump（★3）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/17
• 結果：解けた
• 時間：10分

考えたこと

• いかにもDP
• DP[n]をn段目にたどり着く方法とおいて、DP[n] から DP[n+1]とDP[n+L]に配ればOK。
  • 最初、1段～L段上にすすめると勘違いしていたけど、そうではなくて1段orL段だった。

公式解説

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

解説を読んだふりかえり

• 特に問題はないけど、解説はもらうDPっぽい考え方になってると思った。どっちでも良いんだろうけど。

ソース

N,L = [int(x) for x in input().split()]
DP = [0] * 1000000
DP[0] = 1
MOD = 10**9 + 7

for i in range(N+1):
    DP[i+1] += DP[i]
    DP[i+1] %= MOD
    DP[i+L] += DP[i]
    DP[i+L] %= MOD
print(DP[N])

再帰でもやってみた

• 解けた
• 自分の環境(Win, Python3.9)では、大きいサイズの問題のときに無言で終了する症状が再発。
  • 下記のときと全く同じ
  • ebinafactory.hatenablog.com
• AtCoder上では問題ないようで無事にAC。速度面は下記。
  • Python3：163ms
  • PyPy3：772ms
  • PyPy3(DP版)：69ms
• Python環境でのDP or メモ化再帰については、
  • PyPyは再帰が遅い。(関数呼び出しが遅いらしい)
    • おそらく、再帰以外は全面的にPyPyが早い。
  • メモ化再帰よりDPを使いつつ、PyPyだけ使っていけば良い
  • 自分の場合は、DPのトレーニングが必要そう。

from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

N,L = [int(x) for x in input().split()]
MOD = 10**9 + 7

@lru_cache(maxsize=1000000)
def f(n):
    if n==0:
        return 1
    elif n<0:
        return 0
    return (f(n-1) + f(n-L))%MOD

print(f(N))