今回も引き続き「Kボナッチ数列」を解いていきましょう。
前回で「Kボナッチ数列」とはどんなものか理解できたと思います。
6-3 「K ボナッチ数列」を解くために:part3
引き続き「K ボナッチ数列」を考えます。
1, 2, ..., K 項目を 1 とし、 K + 1 項目以降は前項 K 項の和となる数列のことを、「K ボナッチ数列」と呼ぶことにします。
K ボナッチ数列の i 項目を KB_i とします。
この K ボナッチ数列の i 項目までの累積和 C_i は C_i = KB_1 + KB_2 + ... + KB_i と定義されます。
整数 K と N が与えられるので、 この K ボナッチ数列の N 項目までの累積和 C_N を 10000 で割ったあまりを求めてください。
今回の問題では N, K の値が小さいことが保証されるため、各項を求めるときに毎回前項 K 項の和を計算しても実行時間制限に間に合います
| 入力例 | 出力例 | |
| 3 | 230 | |
| 10 |
今回は数列の累積和を作成する問題です。
A = []
K = int(input())
N = int(input())
for i in range(K):
A.append(1)
for i in range(N-K):
a = sum(A[i:i+K])
A.append(a)
print(sum(A) % 10000)
累積和ですので、Kボナッチ数列を作成し、その合計が解答となります。
A:[1, 1, 1, 3, 5, 9, 17, 31, 57, 105]
ΣA＝sum(A)となります。
6-4 「K ボナッチ数列」を解くために:part4
説明
前の問題で求めた累積和を用いて、K ボナッチ数列の N 項目を高速に求めることを考えます。 前の問題と同様に、K ボナッチ数列の i 項目を KB_i、i 項目までの累積和を C_i とします。
N ≦ K の場合は K ボナッチ数列の定義より KB_N = 1 であるため、以下 N > K の場合を考えます。
i 項目までの累積和 C_i は、C_i = KB_i + C_{i-1} として高速に求めることができます (C_0 = 0 とします)。
K ボナッチ数列の N 項目は N-K 項目 ~ N-1 項目の和、つまり KB_N = KB_{N-K} + KB_{N-K+1} + ... + KB_{N-1} です。
累積和は K ボナッチ数列の i 項目までの和であり、 C_i = KB_1 + KB_2 + ... + KB_i でした。 KB_N = KB_{N-K} + KB_{N-K+1} + ... + KB_{N-1} を累積和を用いた形に変形することで KB_N を高速に求める方法を考えてみましょう。
問題
整数 K と N が与えられるので、 K ボナッチ数列の N 項目を 10000 で割ったあまりを求めてください。
| 入力例 | 出力例 | |
| 3 | 105 | |
| 10 | ||
| ・1 ≦ K ≦ 100000 | ||
| ・K ≦ N ≦ 200000 | ||
いつものように、問題文は難しい説明で理解できないのですが、下記のようにすれば、累計和で
高速処理が可能なようです。
A = []
C = []
K = int(input())
N = int(input())
A.append(0)
C.append(0)
for i in range(K):
A.append(1)
d = 0
for i in range(1,K+1):
d += A[i]
C.append(d)
for i in range(K+1,N+1):
A.append((C[i-1]-C[i-K-1])%10000) ←この２行で累積和の処理をしています。
C.append((C[i-1]+ A[i])% 100000) ←Aが「Kボナッチ数列」Cが累積和になります。
print(A[-1])
A: [0, 1, 1, 1, 3]
C: [0, 1, 2, 3, 6]
A: [0, 1, 1, 1, 3, 5]
C: [0, 1, 2, 3, 6, 11]
A: [0, 1, 1, 1, 3, 5, 9]
C: [0, 1, 2, 3, 6, 11, 20]
A: [0, 1, 1, 1, 3, 5, 9, 17]
C: [0, 1, 2, 3, 6, 11, 20, 37]
A: [0, 1, 1, 1, 3, 5, 9, 17, 31]
C: [0, 1, 2, 3, 6, 11, 20, 37, 68]
A: [0, 1, 1, 1, 3, 5, 9, 17, 31, 57]
C: [0, 1, 2, 3, 6, 11, 20, 37, 68, 125]
A: [0, 1, 1, 1, 3, 5, 9, 17, 31, 57, 105]
C: [0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230]
A: 105 = 125-20
C: 230 = 105 + 125
問題文が高尚すぎて、読んで、こういう仕組になっていること理解できますか？
もう少し数学的な説明ではなく、具体的な仕組みを説明してほしいです。