「K ボナッチ数列」を解くために:part2

今回は 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

出力例:

105

✅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 項の和を計算しても実行時間制限に間に合あったが、次回以降は工夫が必要かもしれない。