🐢

[鉄則B28] Fibonacci Easy

2024/05/18に公開

Ruby

フィボナッチ数列で大きな値を求める際の注意点が学べる問題。

問題を要約する

フィボナッチ数例の N 番目を 1000000007 で割った余りで求めよ

要点

N 番目を求めてから余りに変換するのでは手遅れ
面倒だが足し算するたびに変換するのが正しい

最後に余りを求める (TLE)

N = gets.to_i
MOD = 1000000007
@memo = []
def f(n)
  n <= 1 and return 1
  @memo[n] ||= f(n - 2) + f(n - 1)
end
p f(N.pred).modulo(MOD)  # => 8

普通のコードに見えるが予想以上の計算時間になってしまう。

毎回余りに変換する (AC)

725 ms

N = gets.to_i
MOD = 1000000007
@memo = Array.new(N)
def f(n)
  n <= 1 and return 1
  @memo[n] ||= (f(n - 2) + f(n - 1)).modulo(MOD)
end
p f(N.pred)  # => 8

メモ化変数の型に注意する

メモ化変数を、

@memo = {}

で定義してしまうと TLE になる。なんでもハッシュの癖がついてしまい当初 TLE になる理由がわからなかった。気をつけたい。あと、

@memo = []

と、

@memo = Array.new(N)

の違いは 11 ms 程度の差だったので、あらかじめ確保しておくのが面倒なら空配列でいいかもしれない。