ABC275Dを解いた【メモ化再帰】

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

ABC275のD問題を解いていく

実装コード

メモ化再帰というテクニックがあれば一発で解ける問題らしい。

一度計算した値を連想配列に入れればいいということで個人的に頼れる味方であるdefaultdict君に頑張っていただこう。¹

初期値が入っていれば計算、それ以外だったら計算済なのでその値を返すようにする。

main.py

from collections import defaultdict
df=defaultdict(lambda:0)
df[0]=1
def f(x):
    if df[x]==0:df[x]=f(x//2)+f(x//3)
    return df[x]
print(f(int(input())))

メモ化再帰について調べてみたが、それ専用(?)のデコレーターとしてfunctools.lru_cacheがあるようだ。

main.py

from functools import lru_cache
@lru_cache
def f(x):
    if x==0:return 1
    else: return f(x//2)+f(x//3)
print(f(int(input())))

まとめ

ABC275のD問題を解いた。

メモ化再帰をdefaultdictで実装して解いたが、メモ化再帰用のデコレーターとしてfunctools.lru_cacheが存在していることも知った。

再帰関数を使った実装はまだまだ慣れていないところがあり、勉強になった。

1. 普通のdictでもnot inで判定すればできるようだが、初期値が入っていれば計算のほうが個人的にわかりやすいのでこちらを使うことにした。 ↩