paizaラーニング レベルアップ問題集 新・Bランクレベルアップメニュー JavaScript 【シミュレーション 3】燃費

【シミュレーション 3】燃費 (paizaランク B 相当)

解答例

一時停止地点ごとのひと区間あたり、条件よりs_N ≦ L ≦ 1,000,000,000なので、
ループを回して車が1mずつ進むシミュレーションをすると、処理時間が足らなくなる。
一時停止する区間の数は条件より1 ≦ N ≦ 1000なので、こちらでループすれば処理時間が足りる。一時停止する区間ごとに、必要燃料を、場合分けをして計算する。

出発地点を0とし、そこから s_1(m), ..., s_N(m) の地点で一時停止をし、最後L(m)まで走る。
配列sの最後にLを追加する。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//発進から X m 走る
const [X] = lines[0].split(" ").map(Number);
//発進から X m 走るまでは 1 m あたり燃料が F_1 ml, 発進から X m 走った後から止まるまでは 1 m あたり燃料が F_2 ml 
const [F_1, F_2] = lines[1].split(" ").map(Number);
//全長 L m , N個の地点で一時停止
const [L, N] = lines[2].split(" ").map(Number);
//途中、出発地点から s_1(m), ..., s_N(m) の地点で一時停止
const s = lines[3].split(" ").map(Number);
s.push(L);//最後の地点足す

let requiredFuel = 0;
for (let i = 0; i <= N; i++) {
  //一時停止地点ごとの区間の距離l
  let l = 0;
  if (i === 0) { //最初
    l = s[i];
  } else {
    l = s[i] - s[i - 1];
  }
  //ループせずに、場合分け
  if (l <= X) {
    requiredFuel += l * F_1;
  } else {
    requiredFuel += X * F_1 + (l - X) * F_2;
  }
}
console.log(requiredFuel);

解答例(C++の場合参考)

車の現在地を変数nowとして、ひと区間の距離を一時停止地点s[i]-現在地nowで求める。nowを更新していく。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//発進から X m 走る
const [X] = lines[0].split(" ").map(Number);
//発進から X m 走るまでは 1 m あたり燃料が F_1 ml, 発進から X m 走った後から止まるまでは 1 m あたり燃料が F_2 ml 
const [F_1, F_2] = lines[1].split(" ").map(Number);
//全長 L m , N個の地点で一時停止
const [L, N] = lines[2].split(" ").map(Number);
//途中、出発地点から s_1(m), ..., s_N(m) の地点で一時停止
const s = lines[3].split(" ").map(Number);
s.push(L);//最後の地点足す

let requiredFuel = 0;//必要燃料量
let now = 0;//車の現在地
for (let i = 0; i <= N; i++) {
  //走行距離で場合分け
  if (X < s[i] - now) { //Xよりひと区間s[i]-nowが大きかったら
    requiredFuel += F_1 * X + F_2 * (s[i] - now - X);
  } else { //ひと区間s[i]-nowがX以下なら
    requiredFuel += F_1 * s[i] - now;
  }
  now = s[i];//車は次の一時停止地点へ
}
console.log(requiredFuel);