2項間漸化式 2

今回は paiza のDPで「2項間漸化式 2」の問題に挑戦！

ちなみに、「2項間漸化式（にこうかんぜんかしき）」とは、
ある数列の次の項が すぐ前の1つ前の項だけを使って表される漸化式のこと！

問題概要

• 与えられるもの：
  • 整数 ( x ), ( d )（数列の初項と公差）
  • クエリ数 ( Q )
  • クエリごとに整数 ( k_i )（求めたい数列の項番号）

• 数列の定義：

a_1 = x
a_n = a_{n-1} + d;(n \geq 2)

• 出力：
  各クエリ ( i ) について、数列の ( k_i ) 項目 ( a_{k_i} ) を順に出力する。

入力フォーマット

• 1行目：( x ) と ( d )（半角スペース区切り）
• 2行目：クエリ数 ( Q )
• 3行目以降：各行にクエリの項番号 ( k_i )

出力フォーマット

• ( Q ) 行出力し、
• 各行に数列の該当項 ( a_{k_i} ) の値を出力する。
• 余計な空行や文字は含めない。

条件

・ -1,000 ≦ x ≦ 1,000
・ -1,000 ≦ d ≦ 1,000
・ 1 ≦ Q ≦ 1,000
・ 1 ≦ k_i ≦ 1,000 (1 ≦ i ≦ Q)

入力例:

0 7
5
1
2
3
4
5

出力例:

0
7
14
21
28

❌NG例：

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

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

rl.on('close', () => {
    const [x, d] = lines[0].split(' ').map(Number);
    const Q = Number(lines[1]);
    
    const a = [];
    a[1] = x;
    
    for(let i = 2; i <= Q; i++){
        a[i] = a[i-1] + d;
    }
    
    for(let i = 0; i < Q; i++){
        const k = lines[i + 2];
        console.log(a[k]);
    }
}); 

このコードの問題点は、数列 a[] の計算範囲。
Q は クエリの個数であって、a[] の最大インデックスではないため、次のようなミスが起きる：

❌ 問題点：

for (let i = 2; i <= Q; i++) {
    a[i] = a[i-1] + d;
}

ここで k は 任意のインデックス（例: 1000とか） なので、
Q < k_i だと a[k] が undefined になる。

✅OKコード例：解決策→a[1] 〜 a[1000] まであらかじめ計算しておく

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

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

rl.on('close', () => {
    const [x, d] = lines[0].split(' ').map(Number);
    const Q = Number(lines[1]);

    // a[1] 〜 a[1000] を作成
    const a = Array(1001).fill(0);
    a[1] = x;
    for (let i = 2; i <= 1000; i++) {
        a[i] = a[i - 1] + d;
    }

    // 各クエリに対して a[k] を出力
    for (let i = 0; i < Q; i++) {
        const k = Number(lines[2 + i]);
        console.log(a[k]);
    }
});

✅ 学習のまとめ・ポイント

• 数列の定義を理解する
  • 初項：a₁ = x
  • 漸化式：aₙ = aₙ₋₁ + d（n ≧ 2）

• Q はクエリ数であって、数列の最大項とは限らない
  → a[k] を求めるには、k の最大値を意識する必要がある。

• Q 個のクエリには任意の k_i（例：1000など大きな値）が含まれる可能性がある

• 間違いやすい例：
  a[1] ～ a[Q] までしか生成しないと、k > Q の場合に a[k] が undefined になる。
  • 対策方法：最大1000項まで数列を先に生成する

僕の失敗談(´;ω;｀)と解決法🐈