今回は paiza の「「K ボナッチ数列」を解くために:part2」の問題に挑戦！

問題概要

本問題では K ボナッチ数列という数列を扱う
K ボナッチ数列は、次の規則で定義される

数列の定義

1 項目〜 K 項目：すべて 1
K+1 項目以降：直前の K 項の和

例（K = 3 の場合）

1, 1, 1, 3, 5, 9, 17, ...

求めるもの

整数 K と N が与えられる
K ボナッチ数列の N 項目を求める
ただし、値は 10000 で割ったあまりを出力する

条件

1 ≦ K ≦ 1000
K ≦ N ≦ 2000

※ 今回の問題では N、 K の値が小さいことが保証されるため、各項を求めるときに毎回前項 K 項の和を計算しても実行時間制限に間に合う。

入力例:

3  // K
10 // N

出力例:

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const K = Number(lines[0]);
    const N = Number(lines[1]);
    const MOD = 10000
    
    // Kボナッチ数列
    const KB = [0];
    for (let i = 1; i <= K; i++) {
        KB[i] = 1;
    }
     
    for (let i = K+1; i <= N; i++) {
        let sum = 0;
        
        for (let j = i - K; j < i; j++) {
            sum += KB[j];
            sum %= MOD;
        }
        
        KB[i] = sum;
    }
    
    console.log(KB[N]);
});

🔍 コードの流れ

標準入力から K と N を読み取る
余りを求めるための定数 MOD = 10000 を用意する

初期化処理

配列 KB を用意する（K ボナッチ数列を保存する配列）
インデックスを項番号と対応させるため、KB[0] はダミーとして確保する
1 項目〜 K 項目をすべて 1 で初期化する
- 問題文の定義「1, 2, …, K 項目を 1 とする」に対応

K+1 項目以降の計算

i = K + 1 から N まで順に計算する
各項について次の処理を行う
- 変数 sum を 0 で初期化
- 直前の K 項（KB[i-K] 〜 KB[i-1]）を順に足し合わせる
- 足し算の途中で 10000 で割ったあまりを取る
  - 数値が大きくなりすぎるのを防ぐため
- 求めた合計値を KB[i] に代入する

出力

配列 KB の N 項目目を出力する
出力される値はすでに 10000 で割ったあまりになっている

📝まとめ

フィボナッチ数列は「前の項の和で定まる数列」の代表例
K ボナッチ数列は、フィボナッチ数列（K=2）の一般化
mod を求める問題では途中計算でも mod を取るのが重要
各項を求めるときに毎回前項 K 項の和を計算しても実行時間制限に間に合あったが、次回以降は工夫が必要かもしれない。