前回は高速処理を行うために「Kボナッチ数列」を累積和から解いてみました。
今回は漸化式を使って解いていきましょう。
漸化式とは何か、明快な答えが見当たらないのですが、その配列が持っている特有の法則を式にしたものと理解しました。
6-5 「K ボナッチ数列」を解くために:part5
説明
前の問題では累積和を用いて N 項目を求める方法を紹介しました。
ここでは別の方法を紹介します。
前の問題と同様に、K ボナッチ数列の i 項目を KB_i とします。
N ≦ K の場合は K ボナッチ数列の定義より KB_N = 1 であるため、以下 N > K の場合を考えます。
KB_N = KB_{N-K} + KB_{N-K+1} + ... + KB_{N-2} + KB_{N-1} です。
同様に、KB_{N-1} = KB_{N-K-1} + KB_{N-K} + KB_{N-K+1} + ... + KB_{N-2} です。
この 2 つの式を用いて KB_N を高速に求める方法を考えてみましょう。
問題
整数 K と N が与えられるので、 K ボナッチ数列の N 項目を 10000 で割ったあまりを求めてください。
| 入力例 | 出力例 | |
| 3 | 105 | |
| 10 |
あいかわらずの問題文です、
これを紐解いてみますと、
本問の漸化式の考え方は問題文のとおり、前項との差分に
注目します 。
A[i+1] = A[i] + A[i-1]+A[i-2]・・・・・KB[i-K+1]
A[i]= A[i-1] + A[i-2]・・・・・・+A[i-K+1]+KB[i-K]
i=10 K =3
A[11]= A[10] + A[9]+A[8]+A[7]
A[10] = A[9] + A[8]
A[11]-A[10] = A[10] + A[7]
A[i+1]-A[i] = A[i] - A[i-K]
A[i+1] = 2*A[i] - A[i-k] 漸化式となる
この式を使ってプログラムすればOK！
A = []
C = []
K = int(input())
N = int(input())
A.append(0)
for i in range(K):
A.append(1)
A.append(K)
x = 0
for i in range(K+2,N+1):
x = (2*A[i-1]-A[i-K-1])% 10000 ←漸化式になります。
A.append(x)
print(A[N])
A:[0, 1, 1, 1, 3, 5, 9, 17, 31, 57, 105]
6-6 K ボナッチ数列
最終問題は今回の漸化式か前回の累積和のどちらかのプログラムをそのまま使えば解けますので
ここでは省略します。
これで、Aランク獲得問題全問制覇しました。万歳！万歳！
ありがとうございました。
次回は何をするか考えます。