【Ruby基礎】AtCoder Beginner Contest 006 B – トリボナッチ数列

INDEX

■はじめに

Rubyの基礎的な問題をたくさん解くことで基本的な考え方やメソッドの使い方を定着させたい。
基本的にはAtCoderというプログラミングコンテスト（競技プログラミング）の過去問を使う。（AtCoderは難易度が分かれており、難易度の低いA問題かB問題を解いていく）

（5/23時点の方針）
メソッドの切り分け方や値の受け渡しを練習するために、コード長の短さについては気にせずに書くことにする。

（2022/10/17時点の方針）
しばらくはB問題を小さい番号の方からやっていく。たまにA問題もやるかも。

■問題

●出典

AtCoder Beginner Contest 006のB問題
https://atcoder.jp/contests/abc006/tasks/abc006_2

●問題文

※表記がややこしいので画像で貼り付け

●入力

入力は以下の形式で標準入力から与えられる。

整数 n(1≦n≦10^6) が 1 行で与えられる。

●出力

トリボナッチ数列の第 n 項、an を 10007 で割った余りを 1 行で出力してください。
また、出力の末尾には改行を入れること。

■回答

●愚直に書く

ぱっと見、全然わからない笑。こういう系をちゃんと解けるようになりたいのである。

愚直に進めていく。
まずトリボナッチ数列というのを数式で書きたい。

…だめだ、全然できない涙。
まだ回答は見たくないので、似たようなものとしてフィボナッチ数列をRubyで書いた時のコードというのをちょっと調べてみる。

参考：Ruby で再帰を用いてフィボナッチ数を求めるコードを書いてみた
https://qiita.com/zooootech/items/d8ca1e9d8cfde5646591

なるほど、再帰というのを使うのか。
何度か見たはずだし書いたこともあるはずだけど全然身に付いていなかった…。

n = gets.to_i

def tribonacci(num)
  if num == 1 || num == 2
    return 0
  elsif num == 3
    return 1
  else
    tribonacci(num - 1) + tribonacci(num - 2) + tribonacci(num - 3)
  end
end

puts tribonacci(n) % 10007

上記のコードでトリボナッチ数列は求められそう！
ただ、nの数字が大きくなるとメチャクチャ計算に時間がかかっているようだ…。初めてのTLE エラーを観測した。
どうすりゃいいのか…涙。

AtCoder社長の解説スライドを拝見。
https://www.slideshare.net/chokudai/abc006

まさに再帰関数でやると計算量が膨大になりますって書いてある。動的計画法みたいにやりましょうとも。「動的計画法」ってなんだ…？

う〜〜〜んここまでか、他の方の回答を見させていただこう…。

●他の方の回答を確認

結論から言うと、色々と答えを見てもちゃんと理解ができていない。
いくつかの回答をもとに自分なりに書き直したのが下記。

a = Array.new(1000000)

a[0] = 0
a[1] = 0
a[2] = 1

n = gets.to_i
(3..n).each{|i|
  a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 10007
}

p a[n - 1]

まず今回の標準入力の最大値である1,000,000の配列を作ってしまう
1〜3番目は決まっているので先に入れる
ここで標準入力を変数nに格納
nが0というのはなくて、1〜２の時は計算不要なので、3〜1,000,000の際にeachで回す
トリボナッチ数列を求めるa[i] = (a[i - 1] + a[i - 2] + a[i - 3])をする
上記の時点で% 10007をしているのがポイント。もし最後にp a[n - 1] % 10007をしようとすると、途中式の段階で桁が爆発して時間切れになる。

…という感じなのだけど、途中で% 10007しても結果が同じというのがイマイチピンと来ないのと、自分の１つ目の解法の再帰関数との違いがイマイチわからない…。

■振り返りなど

今回は不完全燃焼。自分の実力不足を痛感した。
しばらくしてからまた見てみよう。