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

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

問題概要

• 本問題では、前問に続いて K ボナッチ数列を扱う
• K ボナッチ数列は次のように定義される

K ボナッチ数列の定義

• 1 項目〜 K 項目：すべて 1
• K+1 項目以降：直前の K 項の和
• i 項目の値を KBᵢ と表す

累積和の定義

• K ボナッチ数列の i 項目までの累積和を Cᵢ とする
• 累積和は次のように定義される
• Cᵢ = KB₁ + KB₂ + … + KBᵢ

求めるもの

• 整数 K と N が与えられる
• K ボナッチ数列の N 項目までの累積和 C_N を求める
• 結果は 10000 で割ったあまりを出力する

入力

• 1 行目：整数 K
• 2 行目：整数 N

出力

• 累積和 C_N を 10000 で割ったあまりを出力する

制約条件

• 1 ≤ K ≤ 1000
• K ≤ N ≤ 2000
• N, K が小さいため、

各項で 直前 K 項をそのまま足す実装でも時間内に収まる

入力例:

3
10

出力例:

230

✅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;
    
    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;
    }
    
    
    let ans = 0;
    KB.forEach(k => {
        ans += k;
        ans %= MOD;
    });
    
    console.log(ans);
});

🔍コードの流れ

入力の読み込み

• 標準入力から K と N を読み取る
• 余り計算用に定数 MOD = 10000 を用意する

初期化

• Kボナッチ数列を保存する配列KB` を用意する
• インデックスと項番号を対応させるため、`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] に代入する

累積和の計算

• 変数 ans を 0 で初期化
• 配列 KB の全要素を順に足し合わせる
  • 各加算後に 10000 で割ったあまりを取る
• 結果として KB₁ + KB₂ + … + KB_N が ans に入る

出力

• 累積和 ans を出力する
• 出力値はすでに 10000 で割ったあまりになっている

✅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];

    // 1項目〜K項目はすべて1
    for (let i = 1; i <= K; i++) {
        KB[i] = 1;
    }

    // 累積和 C_K（最初のK項はすべて1）
    let C = K % MOD;

    // K+1項目以降を計算
    for (let i = K + 1; i <= N; i++) {
        let sum = 0;

        // 直前K項の和
        for (let j = i - K; j < i; j++) {
            sum += KB[j];
            sum %= MOD;
        }

        KB[i] = sum;

        // 累積和を更新
        C += KB[i];
        C %= MOD;
    }

    console.log(C);
});

📝まとめ

• K ボナッチ数列は、フィボナッチ数列（K=2）の 一般化
  -累積和は
  • 「すべて足す」
  • 「前の累積和に 1 項足す」
    の 2 通りで考えられる
• mod を求める問題では、途中計算でも必ず mod を取る
• 前問との差分は、「値を求める」→「値を合計する」