Crystalでメモ化再帰を行う
- In Ruby, to perform memoized recursion, we usually declare
$memo={}
. - Crystal also accepted this method (actually type config is required, so like
$memo={} of Int32 => Int64
). - However, this stopped working in 0.19.0.
@memo
and@@memo
are also invalid at top-level. - The best way for memoized recursion is now to use class.
- https://yukicoder.me/submissions/144799
yukicoder287_class.cr
class Solve
@memo={} of Tuple(Int32,Int32) => Int64
def perform(n,d,u)
if d==1
0<=n&&n<=u ? 1 : 0
else
@memo[{n,d}]||=(0..u).reduce(0_i64){|s,i|s+perform(n-i,d-1,u)}
end
end
def run
n=gets.not_nil!.to_i
p perform(6*n,8,n)
end
end
Solve.new.run
- However, this is a little bit over-work for competitive programming.
- With checking the issue, the most problematic point is initializing. Now we can utilize the fact that in (Ruby and) Crystal, contants are just un-reassignable and destructive updating is possible. In short, we use
Memo
. - Now we are able to build the program.
- https://yukicoder.me/submissions/144800
yukicoder287_const.cr
Memo={} of Tuple(Int32,Int32) => Int64
def perform(n,d,u)
if d==1
0<=n&&n<=u ? 1 : 0
else
Memo[{n,d}]||=(0..u).reduce(0_i64){|s,i|s+perform(n-i,d-1,u)}
end
end
n=gets.not_nil!.to_i
p perform(6*n,8,n)
- Rubyでメモ化再帰を行うには、先頭で
$memo={}
とするのが一般的である。 - Crystalでもこの方法は以前は有効であった(実際には型指定が必要なので、
$memo={} of Int32 => Int64
などとする)。 - しかし、この方法は0.19.0で使えなくなった。
@memo
や@@memo
も効かない。 - 現在メモ化再帰を行うのに最も良い方法はクラスで囲うことであろう。
- しかし、競技プログラミングでは、これは多少オーバーワークである。
- このissueを見ると、初期化に問題があることがわかる。そこで、(Rubyや)Crystalでは、定数とは再代入不可なものであり破壊的変更は可能であることを利用する。つまり、
Memo
を宣言する。 - これでコンパイルを通すことができた。