CodeIQ：極めよプログラミング道！【実力判定：Aランク】その２

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「極めよプログラミング道！【実力判定：Aランク】その２」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

【問題】
1階は1部屋、2階は1部屋、3階は2部屋、4階は3部屋、5階は5部屋、6階は8部屋、7階は13部屋と、増えていく塔があります。
3階以降は、下の2つの階にある部屋数の合計となります。ただし、部屋数が16以上になった場合は、合計を16で割った余りとなります。
ある階数が示された場合、その階に何部屋あるのか答えてください。
提示される階数は、1から1000000000の範囲とします。

【入力】
標準入力から、複数行のデータが与えられます。1行のデータが、1セットの数字になります。
1セットの数字は、1つの階数の数字です。

【出力】
1行ずつ計算して、答えとなる数字を1行ごと標準出力に出力します。

4
5
6
8

3
5
8
5

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

ModFibs = [0, 1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0, 9, 9, 2, 11, 13, 8, 5, 13, 2, 15, 1]

def solve(n)
	return ModFibs[n%ModFibs.size]
end

# main
while line = gets
	line.strip!
	next if line.empty?

	p solve(line.to_i)
end

解説

コードは短いですが、前回のAランクの問題より難しいです。
というか数学が要求されます。

考え方

上限が非常に大きいので素朴にフィボナッチ数列を求めるのはもちろん、漸化式を使っても時間的に無理に思えます。Rubyの整数は自動的に任意精度になりますが、あまりに数が大きいので単純な計算ですら時間がかかりすぎます。

ポイントは16で割った余りの数列は一定のパターンの繰り返しになることに気づくか（知っているか）だけです。私は「フィボナッチ数列剰余」で検索し、そのことを知りました。

繰り返しになるなら、その部分をあらかじめ計算しておけばO(1)で答えを求められます。

main

定数ModFibsが繰り返しのパターンです。私はn=100まで実際に計算するプログラムを作り、その結果からパターンを作成しました。
入力値を取得し数値に変換してsolve()に渡して結果を印字します。

solve(n)

入力値nをModFibsのサイズで割った余りを要素番号としたModFibsの要素を返すだけです。

雑感

最初、漸化式を調べて見たりしたのですが、「桁数が大きすぎて計算するだけでもアウトだ。剰余を求めながらやらないとできない」と気づき、「フィボナッチ数列剰余」で検索したら繰り返しになることを発見しました。
この問題は回答したらヒントが出るのですが、私のやり方が想定解のようです。