🍎 りんご購入アルゴリズム詳細解析

📋 問題の概要

目標： n個以上のりんごを最小コストで購入する

制約条件：

🔍 アルゴリズムの全体フロー

入力読み取り
DP配列初期化
状態遷移計算
最小値探索
結果出力

💻 コード詳細解析

1. 入力処理とメモリ効率

const input = fs.readFileSync('/dev/stdin', 'utf8').trim(); const [n, x, a, y, b] = input.split(' ').map(Number);

同期読み取りを使用することで、大きなファイルでもメモリ使用量を最小限に抑制。非同期処理のオーバーヘッドも回避。

2. DP配列のサイズ最適化

const maxApples = n + Math.max(x, y) - 1; const dp = new Array(maxApples + 1).fill(Infinity);

📊 メモリ最適化の理論

なぜ n + max(x,y) - 1 で十分なのか？

例： n=4, x=2, y=5 の場合

maxApples = 4 + 5 - 1 = 8 → インデックス0〜8の9要素

3. 動的計画法の状態遷移

for (let i = 0; i <= maxApples; i++) { if (dp[i]===Infinity) continue; // x個パック購入 const nextX=Math.min(i + x, maxApples); dp[nextX]=Math.min(dp[nextX], dp[i] + a); // y個パック購入 const nextY=Math.min(i + y, maxApples); dp[nextY]=Math.min(dp[nextY], dp[i] + b); }

🔢 具体例での動作追跡 (n=4, x=2, a=110, y=5, b=200)

1

初期化

maxApples = 4 + 5 - 1 = 8

dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

2

i=0での遷移

2個パック: dp[2] = min(∞, 0+110) = 110

5個パック: dp[5] = min(∞, 0+200) = 200

📈 DP配列の状態変化

りんご個数 0 1 2 3 4 5 6 7 8
初期状態 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
i=0処理後 0 ∞ 110 ∞ ∞ 200 ∞ ∞ ∞
i=2処理後 0 ∞ 110 ∞ 220 200 ∞ 310 ∞
i=5処理後 0 ∞ 110 ∞ 220 200 ∞ 310 400
最終状態 0 ∞ 110 ∞ 220 200 310 310 400

🎯 状態遷移の詳細

i=0

0個の状態から

2個パック購入:
dp[0+2] = dp[2] = min(∞, 0+110) = 110

5個パック購入:
dp[0+5] = dp[5] = min(∞, 0+200) = 200

i=2

2個の状態から

2個パック追加購入:
dp[2+2] = dp[4] = min(∞, 110+110) = 220

5個パック追加購入:
dp[2+5] = dp[7] = min(∞, 110+200) = 310

i=5

5個の状態から

2個パック追加購入:
dp[5+2] = dp[7] = min(310, 200+110) = 310

5個パック追加購入:
dp[5+5] = dp[8] = min(∞, 200+200) = 400

🔍 最小値探索

let minCost = Infinity; for (let i = n; i <= maxApples; i++) { minCost=Math.min(minCost, dp[i]); }

n=4の場合の候補:

答え: 200円

⚡ 計算量とメモリ効率の分析

🕐 時間計算量

O(n × max(x, y))

💾 空間計算量

O(n + max(x, y))

🚀 最適化ポイント

1

配列サイズ最適化

理論的最小サイズでメモリ使用量を削減

2

早期スキップ

dp[i] === Infinity の状態をスキップして無駄な計算を回避

3

境界チェック

Math.min()で配列範囲外アクセスを防止

4

同期I/O

大きな入力でもメモリ効率的な読み取り

🎯 アルゴリズムの特徴

この動的計画法の解法は、貪欲法では解けない問題を効率的に解決します。

理由: 大きなパックを買うことで小さなパックを複数買うより安くなる場合があり、局所最適解では全体最適解にならないため。