FUNCoder-第8回活動

第8回活動 2024/06/26 18:15~19:45 @593教室

/icons/hr.icon

はじめに

ICPC に参加しない部員へ

ICPC に参加する部員へ

初回は、本番同様の時間で取り組むのが良いと思います。というのも、実際の時間を経験することで「長くてやることがなかった」、「もう少し時間あればできた」、「〇〇なら本番までにできそう」など色々な発見があると思います。

なので時間を測って取り組むことを強くオススメします。

全体へ

新年度から活動を始めて3ヶ月が経とうとしていますが、メンバーのレベル・意欲・活動日数など様々な部分に差が出始めてきた頃かと思います。

中間テストやブロック崩しの発表会等がひと段落し、競プロの力をもっと付けていきたい、と思っている学生はどんどん自主的に活動していくことをオススメします。

何度も言っていますが、競プロは週1回、90分程度集まっただけでは中々できるようにはなりません。伸ばしていこと思ったらどうしても1人で勉強する時間というのが必要不可欠となります。なので隙間時間を見つけて効率的な学習を心がけていきましょう！

個人的には毎週新しいことをどんどん取り入れて活動していこうと思っておりますので今後ともよろしくお願いいたします。ご要望やご意見等ありましたら遠慮なくご連絡ください。

/icons/hr.icon

本日のタイトル

/icons/hr.icon

1. フィボナッチ数列とは？

一般化すると、以下の式で表されます。

$ a_{n} = a_{n - 1} + a_{n - 2} \quad (n \geq 3, \quad a_1 = 1, \quad a_2 = 1)

一般項は以下の式で用いられます。

$ a_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1 + \sqrt{5}}{2} \right) ^ n - \left( \frac{1 - \sqrt{5}}{2} \right) ^ n \right\}

黄金比が出てきたりして、かなり美しい式で表されます。

/icons/hr.icon

2. フィボナッチ数列の性質

具体的には、

$ a_3 = a_2 + a_1

$ a_4 = a_3 + a_2 = 2a_2 + a_1

$ a_5 = a_4 + a_3 = 3a_2 + 2a_1

$ a_6 = a_5 + a_4 = 5a_2 + 3a_1

$ a_7 = a_6 + a_5 = 8a_2 + 5a_1

/icons/hr.icon

3. 再帰関数でフィボナッチ数列を求める

まずは再帰関数（DFS）を用いてフィボナッチ数列を求めることを考えます。

再帰関数とは、関数を再帰する、つまり関数の中で関数を呼び出すイメージです。

普通にやれば以下のように求めるのが一般的だと思います。

code:Python

ans = 0

for i in range(1, 11):

ans += i

print(ans)

code:Python

N = 10

ans = N * (N + 1) // 2

print(ans)

しかし、この問題をあえて再帰で解くと以下のようになります。

code:Python

def f(x: int):

if x <= 0:

return 0

return x + f(x - 1)

N = 10

print(f(10))

$ \begin{aligned} f(10) &= 10 + f(9) \\ &= 10 + (9 + f(8)) \\ &= 10 + 9 + (8 + f(7)) \\ &= 10 + 9 + 8 + (7 + f(6)) \\ &= 10 + 9 + 8 + 7 + (6 + f(5)) \\ &= 10 + 9 + 8 + 7 + 6 + (5 + f(4)) \\ &= 10 + 9 + 8 + 7 + 6 + 5 + (4 + f(3)) \\ &= 10 + 9 + 8 + 7 + 6 + 5 + 4 + (3 + f(2)) \\ &= 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + (2 + f(1)) \\ &= 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + (1 + f(0)) \\ &= 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 \\ &= 55 \end{aligned}

code:Python

def f(x: int):

if x <= 0:

return 0

return x + f(x - 1)

N = int(input())

print(f(N))

ここまで来たら話を戻します。

今やりたいことは再帰関数を用いてフィボナッチ数列を求めることです。

これは以下のように実現できます。

code:Python

def f(x: int):

if x <= 2:

return 1

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

N = int(input())

print(f(N))

このようにすることで答えを求めることができます。

一旦座学も飽きたと思うので以下の問題を解いてみましょう（10分）

再帰でフィボナッチ数列を解いた際の計算量を考えてみます

と、思いましたが、めんどかったので既存の解説を参考にしてください。

/icons/hr.icon

4. dp を用いてフィボナッチ数列を求める

次に、動的計画法を用いてフィボナッチ数列を求めることを考えます。

動的計画法（dinamic programming）とは、漸化式を立式し、解いていくような感じです。

code:Python

N = int(input())

if N <= 2:

print(1)

else:

for i in range(3, N + 1):

/icons/hr.icon

5. 行列累乗の準備をする

ここからが今日の最終目標である行列累乗による高速化です。

$ \left( \begin{array} {ccccc} a_{11} & \cdots & a_{1i} & \cdots & a_{1M}\\ \vdots & \ddots & & & \vdots \\a_{i1} & & a_{ii} & & a_{iM} \\ \vdots & & & \ddots & \vdots \\ a_{N1} & \cdots & a_{Ni} & \cdots & a_{NM} \end{array} \right) \cdot \left( \begin{array} {ccccc} a_{11} & \cdots & a_{1i} & \cdots & a_{1K}\\ \vdots & \ddots & & & \vdots \\a_{i1} & & a_{ii} & & a_{iK} \\ \vdots & & & \ddots & \vdots \\ a_{M1} & \cdots & a_{Mi} & \cdots & a_{MK} \end{array} \right) = \left( \begin{array} {ccccc} a_{11} & \cdots & a_{1i} & \cdots & a_{1K} \\ \vdots & \ddots & & & \vdots \\a_{i1} & & a_{ii} & & a_{iK} \\ \vdots & & & \ddots & \vdots \\ a_{N1} & \cdots & a_{Ni} & \cdots & a_{NK} \end{array} \right)

この時、具体例をいくつか考えてみます。

$ C_{1, 1} = A_{1, 1} B_{1, 1} + A_{1, 2}B_{2, 1} + A_{1, 3}B_{3,1} + \dots + A_{1,M} B_{M, 1}

$ C_{1, 2} = A_{1, 1} B_{1, 2} + A_{1, 2}B_{2, 2} + A_{1, 3}B_{3,2} + \dots + A_{1,M} B_{M, 2}

$ \vdots

$ C_{2,1} = A_{2,1} B_{1,1} + A_{2, 2}B_{2, 1} + A_{2,3}B_{3,1} + \dots + A_{2,M} B_{M,1}

$ \vdots

$ C_{N,K} = A_{N,1} B_{1,K} + A_{N,2} B_{2,K} + A_{N,3} B_{3,K} + \dots + A_{N,M} B_{M, K}

これは既習済みだと思うので各自時間を取って確認してみてください。

これを整理すると、一般的に以下のことが成り立ちます。

$ C_{i,j} = A_{i,1} B_{1,j} + A_{i,2} B_{2,j} + A_{i,3} B_{3,j} + \dots + A_{i,M} B_{M,j}

これをプログラムに起こすと下記のようになります。

code:Python

N, M, K = map(int, input().split())

# A は N*M 行列

# B は M*K 行列

# C は N*K 行列

# C の (i, j) 成分を全探索する

for i in range(N):

for j in range(K):

# 各 (i, j) 成分に対しては O(M) で求められる

for k in range(M):

# N 行を 1 行ずつ出力する

for i in range(N):

では、これを実際に手元で解いてみましょう。

また、この後この行列を何回も繰り返し計算する必要が出てくるので以下のように関数にしておきます。

code:Python

def matrix_multi(A: list, B: list) -> list:

for i in range(N):

for j in range(K):

for k in range(M):

return C

/icons/hr.icon

1. 行列の計算

2. （繰り返し二乗法）ダブリング

1. に関しては先ほどの解説の通りです。

問題は 2. についてです。

繰り返し二乗法は高度なアルゴリズムの１つですが、この際なんとなくでも良いので学んでみましょう。

ではここでビットが立っているかどうかをどのように判定するのか考える必要が出てきます。

話を元に戻します。

ここまでの問題をプログラムに落とし込むと下記のようになります。

code:Python

N = 101

ans = 1 # 2^N の答えを求める変数

cnt = 2 # 2の冪乗を計算する変数

while N > 0:

# ビットが立っている時に 2^k を ans に足す

if N % 2 == 1:

ans *= cnt

# cnt を 2乗する

cnt *= cnt

# N を右にシフト（2で割る）する

N //= 2

# 2^101 が求まっていることを確認する

print(ans, ans == 2**101)

この while 文の処理が繰り返し二乗法の本質になっています。

while 文の中身を1行ずつ確認していきましょう。

while 文 1周目

while 文 2周目

while 文 3周目

while 文 4周目

while 文 5周目

while 文 6周目

while 文 7周目

/icons/hr.icon

6. 繰り返し二乗法の何が良いの？

ここまで繰り返し二乗法について学習して来ましたが、これの何が良いのかについて考えます。

/icons/hr.icon

7. フィボナッチ数列を行列で表す

さて、色々遠回りをして来ましたが、本題に戻ります。

つまり、フィボナッチ数列を行列に乗せる必要があります。

フィボナッチ数列は以下で定義される数列でした。

$ a_{n} = a_{n - 1} + a_{n - 2} \quad (n \geq 3, \quad a_1 = 1, \quad a_2 = 1)

$ a = \{1,1,2,3,5,8,13,21,\ldots\}

これを行列に落とし込むと次の式を作ることが出来ます。

$ \left( \begin{array} {c} a_N \\ a_{N - 1} \end{array} \right) = \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} a_{N - 1} \\ a_{N - 2} \end{array} \right)

ここで具体例を計算してみましょう。

$ \left( \begin{array} {c} 2 \\ 1 \end{array} \right) = \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} 1 \\ 1 \end{array} \right)

$ \left( \begin{array} {c} 3 \\ 2 \end{array} \right) = \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} 2 \\ 1 \end{array} \right)

$ \left( \begin{array} {c} 5 \\ 3 \end{array} \right) = \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} 3 \\ 2 \end{array} \right)

$ \begin{aligned} \left( \begin{array} {c} 5 \\ 3 \end{array} \right) &= \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} 3 \\ 2 \end{array} \right) \\ &= \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} 2 \\ 1 \end{array} \right) \\ &= \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array} {c} 1 \\ 1 \end{array} \right) \\ &= \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right)^3 \left( \begin{array} {c} 1 \\ 1 \end{array} \right) \end{aligned}

$ \begin{aligned} \left( \begin{array} {c} a_{101} \\ a_{100} \end{array} \right) &= \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right)^{99} \left( \begin{array} {c} 1 \\ 1 \end{array} \right) \\ &= \left( \begin{array} {c} 573147844013817084101 \\ 354224848179261915075 \end{array} \right) \end{aligned}

といった具合に求めることが出来ます。

ここまで理解できてる人は気づいたと思います。

$ \left( \begin{array} {c} a_N \\ a_{N - 1} \end{array} \right) = \left( \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right)^{N - 2} \left( \begin{array} {c} 1 \\ 1 \end{array} \right)

/icons/hr.icon

8. 行列累乗を用いてフィボナッチ数列を求める

いよいよ本日のゴールです。

まずはこの行列をダブリングを用いて高速に計算するコードを以下に示します。

code:Python

def matrix_pow(a: list, n: int) -> list:

len_a = len(a)

# 計算するための行列の初期値

# 単位行列は体格成分が 1 なのでそれの処理をする

for i in range(len_a):

while n > 0:

if n % 2 == 1:

# ビットが立っている場合は A^i を行列に掛け算する

cnt = matrix_multi(a, cnt)

# A^{2i} の行列積を求めるために A^i × A^i の行列を計算する

a = matrix_multi(a, a)

# n を 2　で割る

n //= 2

return cnt

コード全体は以下になります。

code:Python

def matrix_multi(A: list, B: list) -> list:

for i in range(N):

for j in range(K):

for k in range(M):

return C

def matrix_pow(A: list, N: int) -> list:

len_a = len(A)

# 計算するための行列の初期値

# 単位行列は体格成分が 1 なのでそれの処理をする

for i in range(len_a):

while N > 0:

if N % 2 == 1:

# ビットが立っている場合は A^i を行列に掛け算する

matrix = matrix_multi(A, matrix)

# A^{2i} の行列積を求めるために A^i × A^i の行列を計算する

A = matrix_multi(A, A)

# n を 2　で割る

N //= 2

return matrix

N = int(input())

# 行列累乗を呼び出して N-2 乗回の計算を高速に行う

A = matrix_pow(A, N - 2)

print(ans)

/icons/hr.icon

最後に

かなり急ぎ早に説明したと思うので1回で理解するのはまず難しいと思います。

何度も見返して自分の糧にしていただければ幸いです。

P.S. 死にながら本日の議事録を作成していたので、誤字脱字や誤植等あるかもしれません。あったらこっそり教えてください😫