今回は paiza のDPで「特殊な2項間漸化式 1」の問題に挑戦！
前回と違うのは、添字の偶奇によって漸化式の形が変わること！
問題概要
与えられた整数 x, d₁, d₂, k に対して、次のように定義された数列の k 項目 aₖ を求める問題。
- 初項：a₁ = x
- 漸化式（n ≥ 2）
・n が 奇数 → aₙ = aₙ₋₁ + d₁
・n が 偶数 → aₙ = aₙ₋₁ + d₂
入力例:
5 -7 10 5 // x d_1 d_2 k
出力例:
11 // a_k
✅OK例：
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [x, d1, d2, k] = lines[0].split(' ').map(Number);
const a = [];
a[1] = x;
for(let i = 2; i <= k; i++){
if (i % 2 !== 0) a[i] = a[i-1] + d1;
if (i % 2 === 0) a[i] = a[i-1] + d2;
}
console.log(a[k]);
});
-
a[1] = xから始めてa[k]までループで構築 -
偶奇を
% 2で判定してd1,d2を正しく加算 -
出力は
a[k]のみ -
入力制約（k ≦ 1000）なので配列利用でも全く問題なし
※例：「配列なしでメモリ節約」したいなら
let current = x;
for (let i = 2; i <= k; i++) {
current += (i % 2 !== 0 ? d1 : d2);
}
console.log(current);
📝めも
- 数列の漸化式は 添字の偶奇 で変化するパターン。
- 基本方針は「前から順に1つずつ計算していく」DPの基本スタイル。
- a₁ を初期値として用意し、a₂ 〜 aₖ をループで構築する。
-
iが 奇数 か 偶数 かで d₁ または d₂ を加算するだけ。
-
a[k]を出力すればOK。
※1-indexed なのでa[1] = xに注意。