【シミュレーション 3】燃費

今回は paiza 「【シミュレーション 3】燃費」の問題に挑戦！

問題概要

◯ 状況
車は停車後に再発進すると、最初の X m は燃費が悪い。

• 発進直後 X m → 1 m あたり F1 ml の燃料を使う
• それ以降 → 1 m あたり F2 ml　

◯ 入力

• 発進してから燃費がよくない距離 X m
• 燃料 F1 F2
• 総走行距離 L m
• 途中で N 回停車（s1, s2, …, sN にて停車）

◯ 条件

• 停車中の燃料消費は無視。

• L は最大 10^9

• N は最大 1000

◯ 出力

• 停車を考慮した「全燃料の合計値（ml）」を出力する。

入力例:

10
7 3
100 1
50

出力例:

380

❌ NG例：

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

rl.on('line', (line) => lines.push(line));
rl.on('close', () => {
    const X = Number(lines[0]);
    const [F1, F2] = lines[1].split(' ').map(Number);
    const [L, N] = lines[2].split(' ').map(Number);
    const s = (lines[3] || "").trim() === "" ? [] : lines[3].split(' ').map(Number);

    const stops = new Set(s); // O(1) 判定のため Set に変換

    let fuel = 0;
    let remainingF1 = X; // 発進から残り何mが F1 か（最初は発進直後扱い）

    for (let i = 0; i < L; i++) {
        // この地点 i が停車地点なら、次に進む1mは"発進直後"扱いにリセット
        if (stops.has(i)) remainingF1 = X;

        if (remainingF1 > 0) {
            fuel += F1;
            remainingF1--;
        } else {
            fuel += F2;
        }
    }

    console.log(fuel);
});

🔍 特徴

• 1mごとに処理する。

• 発進直後かどうかを判定

• 停車地点に到達したら「再発進」に切り替える。

◯ 流れ

• 出発して 1m 進むごとに処理する。

• 「停車地点に着いたら remainingF1 をリセット」＝発進直後扱いに戻す。

• 発進から X m までは F1、それ以降は F2 を加算。

• これを L 回繰り返す。

◯ メリット

• 発想が直感的。
  → 「車を1mずつ進めて、燃費を加算する」というイメージ通りの実装。

◯ デメリット

• L が大きい（例：10万 m とか）と 処理が遅くなる。

→ ❌ 実際、テストケースでもいくつかタイムーバーでの不正解も出た。

" ✅ OK例：

const X = Number(lines[0]);
const [F1, F2] = lines[1].split(' ').map(Number);
const [L, N] = lines[2].split(' ').map(Number);
const s = lines[3].split(' ').map(Number);

let fuel = 0; // 燃料
let prev = 0; // 前の発進地点

for (let stop of [...s, L]) { // 停車地点＋ゴール まで処理
    const dist = stop - prev; // 停車地点から次の停車地点までの区間
    const runF1 = Math.min(X, dist); // 発進直後の距離
    const runF2 = dist - runF1;   // 残り通常走行の距離
    fuel += runF1 * F1 + runF2 * F2;
    prev = stop; // 次の出発地点に更新
}

console.log(fuel);

🔍 特徴

• 「停車地点から次の停車地点まで」を ひとつの区間としてまとめて計算。

• 発進直後の X m は F1、それ以降は F2、という区間計算をする。

◯ 流れ

• prev = 0 からスタート地点を記録。

• 各区間（prev から stop までの距離）を一気に計算する。

  • 発進直後の X m → F1
  • 残りの距離は1mごとに → F2

• その区間の燃料を合計して fuel に加える。

• 次の出発地点 prev を更新。

• 最後にゴール地点 L まで処理。

◯ メリット

• L が大きくても 高速。

• 状態管理がシンプル（「発進直後の距離」だけ考えればいい）。

🗒️ まとめ

• 1mずつシミュレーション（❌）
  • 出発からゴールまで 1m ごとに加算。
  • 発進直後かどうかを remainingF1 で管理。
  • L が大きいと ループ回数が膨大になり TLE（10^9 回など）。

• 区間ごとのまとめ計算 （✅）
  • 停車地点から次の停車地点までを ひと区間として処理。
  • 区間長 = dist = stop - prev
    • 発進直後部分 → runF1 = min(X, dist)
    • 残り → runF2 = dist - runF1
    • 燃料 = runF1 * F1 + runF2 * F2
  • 計算量は O(N)（最大 1001 区間）なので高速。

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