paizaラーニング レベルアップ問題集 二分探索メニュー JavaScript 太巻きを分けよう (おなかいっぱい)

太巻きを分けよう (おなかいっぱい) (paizaランク A 相当)

解答例

太巻き１つ１つの大きさを求め配列Bとする。太巻きを左端から１本１本長さがmid以内のできるだけ長い長さにする。分けた本数がnを超えるか以下で分けて、範囲を狭めていく。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//長さ L [cm] の太巻き, n 人で分け, k 個の切れ目
const [L, n, k] = lines[0].split(" ").map(Number);
const A = lines[1].split(" ").map(Number);
//太巻きのそれぞれの長さB
const B = A.map((v, i, arr) => {
  if (i === 0) {
    return v;
  } else {
    return v - arr[i - 1];
  }
});
B.push(L - A[A.length - 1]);

//最も長い太巻きの長さについて二分探索する
let [left, right] = [1, L];//太巻きの長さの範囲

//最も長い太巻きの長さは、太巻き１本１本の中で最も長い太巻き以上になるので、
//これの-1を範囲の左端(最長の長さの範囲の最短)leftに設定する
left = B.reduce((a, b) => Math.max(a, b), left) - 1;

while (right - left > 1) { //制約により整数なので1以下になればよい

  let mid = Math.trunc((left + right) / 2);//最長の長さの上限を仮に決める

  let tmp = 0;//一時的な長さ
  let num = 0;//太巻きの本数
  
  //最長を求めるので１本ができるだけ長くなるようにする
  for (let j = 0; j <= k; j++) {
    tmp += B[j];//１本の長さに加えて検討する
    
    //太巻き１本の長さが最長を超えそうなら
    if (tmp > mid) {
      num += 1;//そこで切って1本
      tmp = B[j];//新しく更新
    }
    //最後まで行ったら
    if (j === k) num += 1;//残ったものを１本にする
  }

  //切った本数がnより多かったら、最長の長さをもっと長く
  if (num > n) {
    left = mid;
  //切った本数がn以下なら、最長の長さをもっと短く
  } else {
    right = mid;
  }

}
console.log(right);

解答例(Python3の場合参考)

太巻きの両端を含む切れ目の配列Aを作る。最も短い太巻きの長さについて二分探索する。左端から切り身がmid以下でできるだけ長くなるように、切れ目を選ぶ。切り出した本数がnを超過するか以下かで分け、範囲を狭めていく。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//長さ L [cm] の太巻き, n 人で分け, k 個の切れ目
const [L, n, k] = lines[0].split(" ").map(Number);
const A = lines[1].split(" ").map(Number);

A.unshift(0);
A.push(L);

//最も短い太巻きの長さについて二分探索する
let [left, right] = [0, L];

/*どんなに短くしようと工夫しても、最も長い太巻きの長さは 
max(a[i]-a[i-1]) (1 ≦ i ≦ k+1) 以上になるので、具体的に計算*/
for (let i = 1; i < k + 2; i++) { //i=1:太巻き2つめからスタート
  left = Math.max(left, A[i] - A[i - 1]);
}

left -= 1;//探索範囲の左端を上の値から-1したものにしている。
while (right - left > 1) { //答えは整数なので差が1以下まででよい
  let mid = Math.trunc((left + right) / 2);//整数なので切り捨て

  let last_index = 0;//最後に切った切れ目の番号
  let index = 0;//今切った切れ目の番号
  /*太巻きの切れ目は、左端がlast_index、右端がindexとなる。*/
  let parts = 0;//太巻きの本数

  //太巻きを端から切り出していく
  while (true) {
    //できるだけ１本の太巻きが長くなるように切り出す
    //切れ目の位置が最後に到達する前、かつ、切った太巻きの長さがmid以下、ならば
    while (index + 1 < k + 2 && A[index + 1] - A[last_index] <= mid) { //index+1次切ろうとしている切れ目
      index += 1;//次の切れ目へ
    }
    parts += 1;//切れ目の探索が終わったら、切って1本の太巻きに
    if (index === k + 1) {//太巻きの右端まで行ったら
      break;//終わり
    } 
    last_index = index;//切ったら、最後の切れ目は、今切った切れ目になる
  }
  
  //切った本数が多かったら、最も長い太巻きはもっと長くできる
  if (parts > n) {
    left = mid;
  } else {
    right = mid;
  }
}
console.log(right);