LoginSignup
0

More than 5 years have passed since last update.

Memoized recursion in Crystal

Posted at

Crystalでメモ化再帰を行う

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を宣言する。
  • これでコンパイルを通すことができた。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0