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

ケーキ同好会10

今日の情報Iの授業は$\texttt{print()}$についてだった。

私は$\texttt{print()}$はもう大丈夫だから、一昨日のPBCでまだ解いてないF問題を解こうかな。

哀先輩にもPBCの問題は全部やった方が良いって言われたし。

あ、部室のホワイトボードに書かれてた問題もついでに解いちゃおうかな。

自分が思ったことをプログラムに書けるようになってから、プログラミングが楽しくなってきた。

「あの」

隣に座っていた女の子から話しかけられたので、一人でニコニコしてたのがばれないように、すぐに振り返った。

「えっと、どうしたの？」

「プログラムの実行方法教えてください」

どうやら、プログラムを書いたけど実行の仕方を聞いていなかったらしい。

「ターミナルにpython main.pyって入力するとできるよ」

「たーみなる......？ぱいそん......？」その子は首を傾げた。

「あー、打ってあげるね」

>python main.py

Hello, World!

「できた？」

その子は私の隣から画面をのぞき込んでいた。

「できたよ、ほら、ここ見て」

私はターミナルを指差した。

「ほんとだ」

その女の子はこちらをじっと見つめてきた。

「名前は」

「えっと、灰崎ゆい、だけど」

「ゆいちゃんは、プログラミングしたことあるの？」

「私も先週始めたばっかりだよ」

「予習？」

その女の子は首を傾げた。

「部活でね」

「そんな部活あった？」

「......ケーキ同好会っていう名前なの」

「ふーん、なんでプログラミング？」

「プログラミングの大会に出ることになったの」

「なんで？？」

私も分かりません。すべては哀先輩の手のひらの上......

「それがプログラミングの問題？」

彼女は私のパソコンの画面に表示されている問題を指差した。

A - First Collatz

実行制限時間:$2$sec/メモリ制限:$1024$MB

配点:$100$点

問題文

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

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

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

制約

入力はすべて整数

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

入力形式

$N$

彼女は問題を一瞥して、すぐに頷いた。

「これ、フィボナッチ数列でしょ」

「え、すごい、そんなすぐに分かるの？」

「数学だと典型的な問題だから」

そのとき、チャイムが鳴った。

今日の授業はこれで終わり。

私はあることを思いついた。

「よし、じゃあ今から部活行ってみようよ」

●

女の子と並んで、私たちは部室に向かった。

「そういえば、名前なんて言うの？」

「月待(つきまち)　望結(みゆ)」

「いつもは何してるの？」

月待さんが私に尋ねた。

「先輩方が来るまでは自習してるかな、あの分厚い教科書を進めてる」

「あれか」

月待さんが苦い顔をした。

「ここだよ」

私は部室のドアを開けた。

「ゆいちゃん、やっほー！」

「あれ、ゆいちゃんともう一人いる！」

「入部希望です」

望結ちゃんがひまり先輩の方を振り返って言った。

「名前は何ていうの？」

「月待(つきまち)　望結(みゆ)です」

「やったー！哀ちゃん、部活にみゆちゃんが入ってくれるって！」

「おー、いらっしゃい」

哀先輩に向かって望結ちゃんはぺこりと頭を下げた。

「ところで、みゆちゃんはどうして私たちの部活に入ってくれたの？」

特に宣伝とかしてなかったし、とひまり先輩は首を傾げた。

「この部活で数学やってるってゆいちゃんに聞いたから」

「そうなんだ！」

ひまり先輩がパンと手を打った。

「じゃあ今日は、関数について話そうかなー」

●

「問題です！「関数」ってどういうもののことを言うでしょう？」

「ある数に対してある数がそれぞれ一つづつ対応するとき、その対応のこと」

「正解！」

「今みゆちゃんが言ってくれたのは数学における関数だね！」

「実は、数学における関数と、プログラミングにおける関数は別のもの」

「そうなんだ」

「プログラミングにおいては、ある処理に名前を付けたもののことを関数っていうよ！」

「例えば、みんなが使ったことあるものだと、$\texttt{print()}$だね」

「あと、入力を受け取る$\texttt{input()}$もね」

哀先輩が付け加えた。

# input()関数

str = input()

print("print()関数！")

「$\texttt{input()}$関数はキーボードで入力された文字列を返す関数で、$\texttt{print()}$関数は文字列を受け取って画面に出力する関数だったんだよ」

「関数は自分で作ることもできるよ」

def func(x):

return x + 1

x = func(1)

print(x)

「でふ、ふぁんくって何ですか？」

「関数にfuncって名前を付けてる」

「defはdefine(定義)、funcはfunction(関数)の略で、よく使われるよ」

「関数に注目してね。今回作った関数は、数を受け取って、1を足して返すよ」

「$\texttt{x}$っていうのが受け取る数ですか？」

「そうだね！」

「$\texttt{return}$ の後ろに書いたものが関数の戻り値となる」

returnは確か、「戻る、返却」みたいな意味だったかな。

今回は$\texttt{return x + 1}$だね。$\texttt{x}$が入力だったから1足しただけってことね。

「関数がなくても同じことができるんじゃないですか？」

「そうだね。でも、文字を表示するのに何行もコードを書くより、$\texttt{print(x)}$って書いた方が分かりやすいよね！」

「なるほど......」

「処理に「名前を付けて、あとで使える」ものっていう認識が大事で、こんなこともできるよ」

n = 6

def F(x):

if x == 0:

return 0

if x == 1:

return 1

return F(x - 1) + F(x - 2)

print(F(n))

$\texttt{F}$は関数の名前で、$\texttt{return}$の後ろにまた$\texttt{F}$が書かれてる？どうなるのこれ？

「関数の中でまた関数が呼ばれるよ」

「？？？」

「この関数は、フィボナッチ数列を計算する？」

「おっ、みゆちゃん鋭い！」

「フィボナッチ数列の漸化式そのままだから」

「そうだね！これは整数$x$を受け取って、フィボナッチ数列の$x$番目を返す関数だよ」

\[F(x) = F(x-1) + F(x-2)\]

\[F(0) = 0\]

\[F(1) = 1\]

「$\texttt{F(x)}$のグラフを書いてみるとこんな感じになるよ」

【挿絵表示】

「円の中は関数$\texttt{F(x)}$に渡される数$\texttt{x}$が書かれてて、下の円の関数が呼ばれるよ」

「こういう感じの、関数の内部で自分自身を呼ぶ関数のことを、再帰関数って言う」

「自分自身を呼ぶ？」

「ああ、関数を実行することを、関数を呼ぶ、とか、関数を呼び出すとか言ったりするんだよ」

へえー。

「ところで皆さん、この図を見て何か思いませんか？」

「ほら、例えばこことここ、同じでしょ」

【挿絵表示】

「同じ計算してて、もったいないと思わない？」

「たしかに......」

「今は$\texttt{F(6)}$を求めるのに25回関数が呼ばれてるよね。この回数は、$\texttt{F(x)}$の$\texttt{x}$が大きくなっていくにつれてどんどん多くなっていく」

「例えば、$\texttt{F(4)}$を一回計算したら、その結果を変数に入れておけばもう一回計算する必要はないよね」

「つまり、このプログラムはもっと高速にできる。一回$\texttt{F(x)}$を呼び出したら、その結果を保存しておいて次に使いまわせばいい」

n = 6

none = -1

memo = [none] * (n + 1)

memo[0] = 0

memo[1] = 1

def F(x):

if memo[x] != none:

return memo[x]

memo[x] = F(x - 1) + F(x - 2)

return memo[x]

print(F(n))

「$\texttt{F(x)}$の値を一回計算したら、配列$\texttt{memo}$の対応する場所$\texttt{memo[x]}$に保存することにした」

「$\texttt{none}$っていうのはなんですか？」

「$\texttt{F(x)}$の値をまだ計算してない場所には$\texttt{none}$を入れてる」

ああ、つまり$\texttt{if memo[x] != none:}$っていうのは、$\texttt{F(x)}$の値が計算済みかどうかを調べてるんだね。

「グラフはこんな感じになる」

【挿絵表示】

「確かに、前のグラフと比べて丸いところが減ってますね」

「このように、関数の返す値を配列に記録しておくことをメモ化という」

「再帰関数に限らず、何度も呼ばれる関数はメモ化しておくと計算コストが少なくできるよ！」

「メモ化した後のフィボナッチ数列を求める計算は$O(N)$だよ」

「おーえぬ？って何ですか？」

と望結ちゃんが言った。

「計算コストが$N$に比例してるってことだよ」

と哀先輩が答える。

$O(N)$っていうのは計算量だったかな。たしか計算回数$10^8$で1秒くらいだったから、フィボナッチ数列の第$10^8$項まで求めるのならすぐにできるってことかな。

「......あれ？今回の制約って$1 \leq N \leq 10^{12}$じゃありませんでした？」

制約

入力はすべて整数

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

「すごい！ゆいちゃん、制約を見れるようになったなら、もう初心者卒業だね！」

ひまり先輩とハイタッチした。いえーい！

「つまり、フィボナッチ数列はもっと速く計算できる」

数列を一瞬で求める方法......？あれ、なんか小学校でやったような気が。

1から100までの整数の和を全部足してみなくても求められたような記憶がある。

そうだ、数列には一般項がある。1から100までの整数の和が5050って一瞬で計算できるのも、1から$N$までの整数の和の一般項が $\frac{N(N+1)}{2}$ って求められたから、

\[\frac{100 \cdot 101}{2} = 101 \cdot 50 = 5050\]

みたいに計算できるんだよね。フィボナッチ数列の一般項は知らないけど、有名な数列だから調べたら出てきそう。

「フィボナッチ数列の一般項を使うとかどうですか？」

「いい線行ってるね！」

「フィボナッチ数列の一般項はこんな感じになるんだけど」

\[F_N = \frac{1}{\sqrt{5}} \left[\left( \frac{1 + \sqrt{5}}{2} \right)^N - \left( \frac{1 - \sqrt{5}}{2} \right)^N\right]\]

「フィボナッチ数列の第$N$項を求めるには、$\sqrt{~~}$が入った数字を$N$回掛け算しないといけないからね」

「結局前から足し算するのと計算する回数が同じってことですか」

「そうそう。計算量は$O(N)$のままだね！」

「あと無理数をちゃんと扱おうと思ったら結構面倒なんだよね」

と哀先輩が言った。

うーん。さすがにもう何も思いつかない。ていうか競技プログラミングを始めたばかりの割には

結構頑張った方じゃないだろうか。むしろ褒められるべき。

そう思っていると、ひまり先輩が答えを教えてくれた。

「フィボナッチ数列の一般項を整数の計算のみで求める方法があるんだよ」

「数列の漸化式を行列で表して、行列累乗をするよ」

「漸化式を行列で表す？」

「お店に並ぶことじゃないよ？数学のね」

テレビでやってた、行列のできる飲食店のランクが$N$っていうネタ好きだったなー、とひまり先輩が呟く。

「ゆいちゃんは行列知らない？」

「今日初めて聞きました」

「みゆちゃんは？」

「最近勉強した」

「お！すごいね！！」

「行列累乗は行列を知らないと説明するのが難しいから、行列を使わずにもうちょっと簡単な例で説明しようかな」

ひまり先輩がホワイトボードに数字を書いて教えてくれる。

「じゃあ、まずは繰り返し二乗法からだね！！」