フィボナッチ数列と繰り返し二乗法
放課後は職員室まで部室の鍵を取りに行ってから、教室に先輩方を呼びに行くのが習慣となった。今日が初めてだけど。
というのも、ひまり先輩が鍵を取りに行って、持ち前のアグレッシブさで鍵を持ったままどこかに行ってしまうからだ。部室の前で待っていても、いつまでたってもひまり先輩が来ないので哀先輩が怒ってしまったのだ。
というわけで、今日から鍵を職員室に取りに行くのは1年生の私の仕事になったわけである。私は、結局教室に呼びに行くなら全員で鍵を取りに行ってもいいんじゃないかなと思うけど。今も部室までおしゃべりしながら並んで歩いてるもんね。
「そういえばまだ競プロがどんな感じかイメージついてないよね」
「問題を解くプログラムを作るっていうのは教えてもらいましたけど、まだよく分からないです」
「だと思ったから、今から私とひまちゃんで競プロで勝負しようと思います」
哀先輩が部室のドアのカギを開ける。ケーキ同好会の部室は一階の一番隅のところ。あまり人が通らなくてがやがやしていないので、わたし的には結構お気に入りの場所だったりする。
「30分、3問のうちから多くの問題を解いた方が勝ちで、コンテストの過去問から難易度ランダムで選ぶ」
コンテストっていうのは、前説明してもらったランクが赤とか青とかいうやつの話らしい。実力に応じて自分のレートが増減するから、実力を証明する一つの指標になってるんだって。
「問題が分からないから、ゆいちゃん何してるか分からないんじゃない？」
ひまり先輩が哀先輩に問いかける。私もそう思います。
「ひまちゃんが解説するから心配いらない」
「哀ちゃんはしないの？」
「ひまちゃんの方が強いから、私が解説すると確実に負ける」
「ハンデってことね、いいよ！」
「じゃあ、5時から30分ね、それまでなんか作ろうか」
「哀ちゃん作のホットケーキを希望します！」
「ゆいちゃんがタイマーのボタンを押してね」
「分かりました」
「3...2...1...始め」
緊張した。噛んだら絶対笑われるし。
「ゆいちゃんが分かりやすそうな順から解こうかなー」
哀先輩は一番最初の問題から順に解いていくようだ。それに対して、ひまり先輩はけっこう余裕そう。問題のページをさっと見て、私に解説する問題を選んでいるようだ。
「難易度ランダムだから、全部理解できるように解説はできないよ」
ひまり先輩って、パソコンを見るときは眼鏡かけるんだね。あれ、でも前print文を教えてもらったときは、眼鏡してなかったような。集中するときだけかけるのかな？
「これが良さげかな？」
<<問題文>>
あなたは階段を上るのに、一歩で一段か二段上ることにしました。
n段目まで上る方法の数は何通りありますか？
答えは非常に大きくなる可能性があるので、10^9+7で割った余りを出力してください。
<制約>
1 ≦ n ≦ 10^12
「これは有名な問題だね、もしかしたら見たことあるかも？」
「初めて見ました」
「ちょっと考えてみて、その間にコードを書いとくから」
一歩で一段昇る方法だけだったら、1通りだよね。「一歩で二段昇る」方法が入ってるから面倒になってるんだね。
とりあえず、階段が三段あるときはどうなるか考えてみようかな。
最初に一段昇って、そのあと二段昇る方法で1通り。それと、最初に二段昇って、そのあと一段昇る方法で合わせて2通り。あと、毎回一段づつ登る方法もあるから全部で3通りかな。数え忘れてなければ。
よし、階段が三段のときは3通りであることが分かった。じゃあ、階段がn段のときは......なんにも分かりません。
n段目までっていうのは入力で与えられるから、そのすべてに対して正しい答えを返さないといけないのが難しいよね。今やったみたいに、階段が三段のときの答えはこれ、って書いていくわけにもいかないし。
......これ来週の予選までにできるようになるんだろうか。
唸っていると、ひまり先輩がコードを書き終わったようで、パソコンから目を離して私の方を見た。
「解けた？」
「全然分かりません......」
「今いる場所は0段目で1通りだとするよ。一段目に行く方法は、1通りだよね。二段目に行く方法は何通り？」
「0段目から二段昇る方法と、一段目から一段昇る方法の2通りです。」
「そうそう。そんな感じで、三段目に行く方法は何通り？」
「あ、さっき3通りって数えてました」
「お、それじゃあ四段目は？」
「えっと、0段目から一段昇ってから、二段昇って一段昇るのと、......面倒そうです」
「じゃあヒントだよ。四段目に行くには何段目から来る方法がある？」
四段目に来るためには、二段目から2段昇る方法と、三段目から1段昇る方法がある。だから四段目まで昇る方法は2通り？
いや、二段目に上る方法が2通りだから、二段目から2段昇るときは2通り分で数えないといけないよね。三段目から1段昇るのは3通りってさっき数えたから、同じ考え方をすると四段目まで昇る方法は2 + 3 = 5通り。ちょっと分かってきたかも。
「これって、一段目から順に求めると簡単になります？」
「そう、正解！前の二つの段の通り数を足すと次の段の通り数が求まるね」
「ゆいちゃん、これ見たことあるかな？」
1 1 2 3 5 7 12 19 31 ......
「前の二つの数字を足すと、次の数字になる有名な数列があるんだけど」
「教科書のコラムで見たような......？でも名前忘れてしまいました」
「これ、フィボナッチ数が答えになるんだよ」
たしか、自然の中によく現れる数列で、例えば花びらの数はフィボナッチ数が多いそう。簡単な足し算で求めることができるのに、自然界に現れるのは不思議だなと思った記憶が微かにある。
階段の上り方の通り数がフィボナッチ数になるっていうのは意外だった。最初問題を見たときは、変な昇り方してるなーとしか思わなかったね。さすがのひまり先輩も、こんな昇り方はしなさそう。
「でもね、これはフィボナッチ数列を最初の項から求めてると実行時間制限に間に合わないんだよねー」
「え、これで正解じゃないんですか」
「もちろん正解を出力しないと誤答になるんだけど、正解を出力するまで1年かかったりすると困るよね」
競技プログラミングにおいては、ただ正解を出力するだけでなく、正解を出力するまでの速度も重要らしい。私プログラミング始めたばっかりなんだけど、来週の予選までにできるようになるんだろうか。
「ここが競技プログラミングっぽいところで、答えを求める方法を高速化する必要があるんだよね」
数列を一瞬で求める方法があればいいんだよね。あれ、なんか小学校でやったような気が。1から100までの整数の和を全部足してみなくても求められたような記憶がある。
そうだ、数列には一般項がある。1から100までの整数の和が5050って一瞬で計算できるのも、一般項が n*(n+1)/2 って求められたから。100 * 101 /2 = 101 * 50 = 5050 みたいに。フィボナッチ数列の一般項はどうなってるか知らないけど、有名な数列だから調べたら出てきそう。
「フィボナッチ数列の一般項を使うとか？」
「いい線いってるねー。でも今回は使えないかな」
「フィボナッチ数列の一般項はこんな感じになるんだけど」
「フィボナッチ数列のn項目を求めるには、√が入った数字をn回掛け算しないといけないから、面倒かも」
「結局前から足し算するのと計算する回数が同じってことですか」
「そうそう。あと小数を含む計算があるから、誤差が気になってくるね」
うーん。さすがにもう何も思いつかない。ていうか競技プログラミングをやったことがない割には、結構頑張った方じゃないだろうか。むしろ褒められるべき。
そう思っていると、ひまり先輩が答えを教えてくれた。
「数列の漸化式を行列で表して、行列累乗をするよ」
「行列で表す？」
「並ぶことじゃないよ？数学のね」
YouTubeでやってた行列のできる飲食店ってので、ランクがnっていうネタ好きだなー、とひまり先輩が呟く。
「ゆいちゃんは行列知らない？」
「今日初めて聞きました」
「行列累乗は行列を知らないと説明するのが難しいから、行列を使わずにもうちょっと簡単な例で説明しようかな」
部室のホワイトボード思っていたよりたくさん使うね。ひまり先輩がホワイトボードに数字を書いて教えてくれる。
「例えば、2の100乗を計算しようと思ったら、何回2を掛け算をする必要がある？」
「100回ですか？」
「惜しい、小さい数でチェックしてみよう。2の1乗は何回？」
「あ、0回です。だから、2の100乗は99回ですね」
「正解！」
「でも、今回求めたいのは2の〈10の12乗〉乗です」
ひまり先輩が書いた、一番右上の12がとても小さくなっている。
「この場合何回2を掛け算するんだっけ？」
「えっと、10の12乗 - 1 回です」
「パソコンで10の12乗回掛け算しようと思ったら、実はとてつもなく時間がかかるんだよね」
「そうなんですか」
「そうなんです」
「10の12乗だと、一時間くらいかな？」
あれ、時間がかかるといっても、そこまでじゃないね。授業よりは短いし。実行しておいて、その間ほかのことをしておいたらいいんじゃないかな。
「一時間くらいなら待っててもいいんじゃないですか？」
「一つ求めるのに一時間かかったら、24個求めたら1日かかっちゃうよ！コンテストは長くても2～3時間だから、全然間に合わないね」
「あ、確かに」
「例えば、地図の経路案内で、目的地までの最短距離を求めるのに1時間かかってたら困るよね」
「歩いた方が速そうですね」
「結論としては、最大128回の掛け算で計算できるよ」
「128回だとどれくらいの時間かかるんですか？」
「実行ボタンを押したら計算が終わってるくらいかな、どっちがいいかは比べるまでもないね」
「おーすごいです」
2^1 2^2 2^4 2^8 2^16
こんな感じで、2の〈2のなんとか乗〉乗を先に求めておく。
この数列は、次の数が、その前の数の2乗になってるから、次の数字は1回で計算できるよ。
前の数を繰り返し2乗していくから、繰り返し二乗法って言ったりするね。
例えば、
2^8 = (2^4)^2 = 2^4 * 2^4
みたいに、2の4乗を先に求めていたら一回の掛け算で計算できるよ。
そうすると、例えば2の15乗を計算したいとなったら、
15 = 1 + 2 + 4 + 8
って分解できるから、
2^15 = 2^(1+2+4+8) = 2^1 * 2^2 * 2^4 * 2^8
みたいに計算できるよ。
15 = 1 + 2 + 4 + 8
っていうのは2進数の考え方だね。すべての自然数が2のなんとか乗の足し算で計算できるってやつだね。
「そんなイメージで、行列っていうものに対しても同じことをすると答えが求まるよ」
微妙に最後の方が分からなかったけど、一応プログラムを見せてもらう。
ひまり先輩のプログラム、全然何をしてるのか分からないな。魔法の詠唱みたい。
その後は、この問題はグラフに落としてダイクストラだの、聞いたことのない単語のオンパレードだった。結局ひまり先輩が哀先輩より先に三問解いた。私にもっと時間をかけて解説してくれてもいいんですよ？
