ケーキ同好会でも、プログラミングは必須スキルです！

ケーキ同好会3

放課後は職員室まで部室の鍵を取りに行って、そのあと教室に先輩方を呼びに行くのが習慣となった。

今日が初めてだけどね。

というのも、ひまり先輩が鍵を取りに行って、持ち前のアグレッシブさで鍵を持ったままどこかに行ってしまうからだ。

部室の前で待っていても、いつまでたってもひまり先輩が来ないので哀先輩が怒ってしまったのだ。

というわけで、今日から鍵を職員室に取りに行くのは1年生の私の仕事になったわけである。

私は、結局教室に呼びに行くなら全員で鍵を取りに行ってもいいんじゃないかなと思うけど。

今も部室までおしゃべりしながら並んで歩いてるもんね。

「そういえばまだ競プロがどんな感じかイメージついてないよね」

「問題を解くプログラムを作るっていうのは教えてもらいましたけど、まだよく分からないです」

「だと思ったから、今から私とひまちゃんで競プロで勝負しようと思います」

哀先輩が部室のドアのカギを開ける。ケーキ同好会の部室は一階の一番隅のところ。

あまり人が通らなくてがやがやしていないので、わたし的には結構お気に入りの場所だったりする。

「30分、3問のうちから多くの問題を解いた方が勝ちで、コンテストの過去問から難易度ランダムで選ぶ」

「問題が分からないから、ゆいちゃん何してるのか分からないんじゃない？」

ひまり先輩が哀先輩に問いかける。私もそう思います。

「ひまちゃんが解説するから心配いらない」

「哀ちゃんはしないの？」

「ひまちゃんの方が強いから、私が解説すると確実に負ける」

「ハンデってことね、いいよ！」

「じゃあ、17時から30分ね、それまでなんか作ろうか」

「哀ちゃん作のホットケーキを希望します！」

●

「ゆいちゃんがタイマーのボタンを押してね」

「分かりました」

「3、2、1、始め」

緊張した。噛んだら絶対笑われるし。

「ゆいちゃんが分かりやすそうな順から解こうかなー」

横から見てると、哀先輩は一番最初の問題から順に解いていくようだ。

それに対して、ひまり先輩はけっこう余裕そう。

問題のページをさっと見て、私に解説する問題を選んでいる。

「難易度ランダムだから、全部理解できるように解説はできないよ」

ひまり先輩って、パソコンを見るときは眼鏡かけるんだね。

あれ、でも前print()について教えてもらったときは眼鏡してなかったような。

集中するときだけかけるのかな？

「これが良さげかな？」

問題文

あなたは階段を上るのに、一歩で一段か二段上ることにしました。

$N$段目まで上る方法の数は何通りありますか？

答えは非常に大きくなる可能性があるので、$10^9 + 7$ で割った余りを出力してください。

制約

$1 \leq N \leq 10^{6}$

「これは有名な問題だね、もしかしたら見たことあるかも？」

「初めて見ました」

「ちょっと考えてみて、その間にコードを書いとくから」

一段昇る方法なら1通りだよね。

二段上る方法は？

えっと、一歩で一段目まで昇って、そこからまた一歩で二段目まで上る方法があるね。

あ、一歩で一気に二段上る方法もある。

だから二段上る方法は2通り。

「一歩で二段上っても」良いから面倒になってるんだね。

階段が三段あるときはどうなるか考えてみよう。

最初に一段上って、そのあと二段上る方法で1通り。

それと、最初に二段上って、そのあと一段上る方法で合わせて2通り。

あと、毎回一段づつ上る方法もあるから全部で3通りかな。数え忘れてなければ。

よし、階段が三段のときは3通りであることも分かった。

【挿絵表示】

じゃあ、階段が$N$段あるときは......なんにも分かりません。

$N$段目までっていうのは入力で与えられるから、そのすべてに対して正しい答えを返さないといけないのが難しいよね。

今やったみたいに、階段が三段のときの答えはこれ、って書いていくわけにもいかないし。

......これ6月のコンテストまでにできるようになるんだろうか。

唸っていると、ひまり先輩がコードを書き終わったようで、パソコンから目を離して私の方を見た。

「解けた？」

「全然分かりません......」

「じゃあ、いっしょに考えてみようか」

「一段目に行く方法は、1通りだよね。二段目に行く方法は何通り？」

「一番下から二段上る方法と、一段目から一段上る方法の2通りです」

「そうそう。そんな感じで、三段目に行く方法はどう？」

「あ、さっき3通りって数えてました」

「お、それじゃあ四段目は？」

「えっと、一番下から一段上ってから、二段上って一段上るのと、......面倒そうです」

「たしかに、その方法だと$N$が大きくなったときに難しくなるねー」

「さっきここまで考えてて、難しいなーって思ってました」

「じゃあヒントだよ。

四段目に行くまでの方法の通り数をいきなり考えると難しくなっちゃうから、

四段目に一歩で上れる段数を考えてみよう！」

四段目には二段目と三段目から一歩で上れるね。

二段目から2段上る方法と、三段目から1段上る方法で2通り？

いや、二段目に上る方法が2通りあるから、二段目から一歩で2段上る方法は2通り分で数えないといけないよね。

同じように考えると、三段目から1段上る方法は3通り分で数えないと。

だから、四段目まで上る方法は、二段目から来る2通りと、三段目から来る3通りを合わせて2 + 3 = 5通り。

ちょっと分かってきたかも。

【挿絵表示】

次の段には前二つの段からしか行けないから、

前二つの段に上る方法の通り数を足すと、次の段に上る方法の通り数が求まるんだね。

「これって、前二つの答えを足せば求まります？」

「そう、正解！前の二つの段までの上り方の通り数を足すと、次の段までの上り方の通り数が求まるね」

「じゃあ、十段目まで昇るのは何通りになるかな？」

「えっと、一段目から順番に求めていけばいいんですよね」

五段目まで昇るのは、3 + 5 = 8通り、

六段目まで昇るのは、5 + 8 = 13通り、

七段目まで昇るのは、8 + 13 = 21通り......

ちょっとこれめんどくさいかも。

「今めんどうだなって思ったでしょ、顔に出てたよ」

「え、本当ですか、恥ずかしい......」

ふふ、とひまり先輩が小さく笑う。

「でも、これは数学の問題じゃないから、ね」

「今考えたことを代わりにパソコンにやらせよう！」

n = int(input())

fib = [1,1]

for i in range(n - 1):

fib.append(fib[-1] + fib[-2])

print(fib)

「プログラムを書くっていうのは、言うなればゆいちゃんと同じ考え方をするミニゆいちゃんを作るってことだね」

プログラムを見てみた。知らない文法がいっぱい......

「プログラムの文法は少しづつ分かるようになるよ」

「ところでゆいちゃん、8番目までの答えを並べて見てみよう」

\[1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34 \dots\dots\]

「これ見たことあるかな？

前の二つの数字を足すと、次の数字になる有名な数列だよ」

「教科書のコラムで見たような......？でも名前は忘れてしまいました」

「これ、フィボナッチ数列になるんだよ」

名前を聞いたら少し思い出した。

たしか、自然の中によく現れる数列で、例えば花びらの数はフィボナッチ数が多いそう。

簡単な足し算で求めることができるのに、自然界に現れるのは不思議だなと思った記憶が微かにある。

でも、階段の上り方の通り数がフィボナッチ数になるっていうのは意外だった。

最初問題を見たときは、変な昇り方してるなーとしか思わなかったね。

さすがのひまり先輩も、こんな昇り方はしなさそう。

その後は、この問題はグラフに落としてダイクストラだの、聞いたことのない単語のオンパレードだった。

結局ひまり先輩が哀先輩より先に三問解いた。

私にもっと時間をかけて解説してくれてもいいんですよ？