「ルーム・アンド・ルーフ」問題解答 ( CodeIQ )
CodeIQというところでプログラミング問題「ルーム・アンド・ルーフ」に解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 標準入力$n$に対して、次の図のように、正方形に正三角形をくっつけつつ正方形を$n+1$個作っていき、$P_0=1$から始めて最後の正方形の面積を$P_n$とする時、$F_n=\lfloor P_n \rfloor$ に対して、$F_n$を$10^6$で割った余りを求め出力する。
解説
$P_n=(2+\sqrt{3})^n$ です。終わり。
…と、図形的な性質はそれでいいのですが、ここから切り捨てて整数値を求めるところが問題になります。なにせ無理数ですから。
ここでふと、$2+\sqrt{3}$の共役めいた$2-\sqrt{3}$を持ってきます。併せてこれら2数は2次方程式 $t^2-4t+1=0$ の実数解です。
そのため、数列$P_n$は、漸化式 $P_n=4P_{n -1}-P_{n -2}$ を満たすことが分かります。無理数を含まない漸化式をつくることはできるのです。
しかし、$P_n$が無理数であることには変わりません。そこで、同じ漸化式で値が整数となる数列を探します。
丁度、$Q_n=(2+\sqrt{3})^n+(2-\sqrt{3})^n\,\,( Q_0=2,\,Q_1=4 )$がそうです。そうするとこの$Q_n$の一般項の式の第一項は$P_n$そのもの、第二項は1より小さい数のべき乗であることから、実は$Q_n=F_n +1$であると分かります。
あっさり$F_n$の正体がバレてしまいました。結局$F_n$は元の漸化式をちょっと修正した $F_n=4F_{n -1}-F_{n -2}+2$ を満たします。
ということで提出版の実装Ruby(46)です。素直に漸化式を$n$回回しています。もちろん、計算量を減らすためにはバイナリ法を(以下略)。
a,b=1,3;gets.to_i.times{b=2-a+4*a=b%10**6};p a
終わりに
終わってみれば単純なコードになりましたが、整数値への切捨てをうまく処理する方法を思いつかないと厳しかったと思います。
