paizaラーニング レベルアップ問題集 二分探索メニュー応用編 JavaScript 記念写真

記念写真 (paizaランク A 相当)

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

ジャンプした高さの最小値で二分探索します。

各人が最小値の高さmid以上になるためには、燃料を(最小値の高さ/ジェットパックの燃料 1 つにつき高さ A)の切り上げの個数、すなわち、Math.ceil(mid / A)個、使います。

全員、mid以上になる時に使った燃料がK個を満たすか調べます。

---

探索範囲rightの初期値が、問題文によると

1 ≦ A_i ≦ 1,000,000,000 = 10^6

なのですが、1,000,000,000 と 10^6、どちらが正しいかわかりませんでした。paizaに問い合わせました。
模範解答から、ジャンプの最小値の探索範囲の最大値、右端rightを1000000000000000001=10^18+1にしたら、うまくいきました。

ジャンプの高さは、A_i * Kで、Kの最大値は10^12なので、おそらく、A_iの最大値は10^6が題意のようです。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//あなたと友達の合計人数を表す整数 N, ジェットパックの燃料の個数 K
const [N, K] = lines[0].split(" ").map(Number);

//ジェットパックの燃料 1 つにつき高さ A_i だけ上昇
//ジャンプの最小値から、K個を満たすか探索する
//A_iの高さの範囲
let [left, right] = [0, 1000000000000000001];

while (right - left > 1) {
  const mid = Math.trunc((left + right) / 2);//仮のジャンプの高さの最小値
  
  //mid以上になるように、ジェットパック燃料を分配する
  let numFuel = 0;
  for (let i = 1; i <= N; i++) {
    const A = Number(lines[i]);
    numFuel += Math.ceil(mid / A);
    
  }
  //使った燃料がK個を満たすか
  if (numFuel <= K) {
    //燃料の個数がK以下なら、高さはもっと高くできる
    left = mid;
    
  } else { //燃料の個数がKを超えたら、高さは低く
    right = mid;
  }
}
console.log(left);

解答例(Pythonの場合参考)

ちなみに、x / y を切り上げた値を求める際には、(x + y - 1) / y を切り捨てた値を用いることができます。

こちらもleft=1<<47だとうまくいかず、1000000000000000001=10^18+1にしたら、うまくいきました。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//あなたと友達の合計人数を表す整数 N, ジェットパックの燃料の個数 K
const [N, K] = lines[0].split(" ").map(Number);
//ジェットパックの燃料 1 つにつき高さ A_i だけ上昇
const A = lines.slice(1).map(Number);

//ジャンプの最小値から、K個を満たすか探索する
//k個以内でジャンプできるときは true, できないときは false
const check = x => {
  let cnt = 0;//燃料の個数
  for (let i = 0; i < N; i++) {
    cnt += Math.floor((x + a[i] - 1) / a[i]);
  }
  if (cnt <= K) {
    return true;
  } else {
    return false;
  }
};

//A_iの高さの範囲
//leftは常に条件を満たす，rightは常に条件を満たさない
let [left, right] = [0, 1000000000000000001];

while (right - left > 1) {
  const mid = Math.trunc((left + right) / 2);//仮のジャンプの高さの最小値

  //使った燃料がK個を満たすか
  if (check(mid)) {
    //燃料の個数がK以下なら、高さはもっと高くできる
    left = mid;
    
  } else { //燃料の個数がKを超えたら、高さは低く
    right = mid;
  }
}
console.log(left);