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

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

解説

切れ目の選び方を工夫したとき、最も短い太巻きの長さを最大でいくつにできるかを答えてください。

とあるので、最も短い太巻きの長さについて、二分探索ができそうです。

最も短い太巻きの長さと、与えられたAの情報から、何か関係式が作れないか考えます。

---

与えられた情報から、太巻きの切れ目ごとの長さを求めます。

ある最も短い太巻きの長さをmidとすると、太巻きを切った長さは、少なくともmid以上でないといけません。

また、midを以上の場合、できるだけmidに近づけたいので、できるだけ短く切ります。
すなわち、mid以上ならすぐに切ります。

太巻きの１つ１つの長さを調べていきます。

midに満たなかったら、切らずに次の太巻き１つと長さを出します。
mid以上ならば、すぐに切ります。

これを繰り返して、最後の切り身を１本として、全部で切り身が何個になったか調べます。

n人で分けないといけないので、nに満たない場合は、もっとmidを短くして(right=midにして)再度調べます。
nを超えたら、midをもっと長くします。left=midとして再度調べます。

答えは整数なので、範囲が１以下になれるまで繰り返せばよいです。すなわち、範囲の両端を右端right,左端leftとすると、right-left<=1です。

解答例

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] = [0, L + 1];//太巻きの長さの範囲
while (right - left > 1) {//範囲が1以下になればよい
  
  let mid = (left + right) / 2;
  //長さがx以上ならy<=xの全てのyについても成り立つので、left=mid
  //Aから、midの入った関係式を導く
  let tmp = 0;//一時的な長さ
  let num = 0;//太巻きの本数
  //最短を求めるので１本ができるだけ短くなるようにする
  for (let j = 0; j <= k; j++) {
    tmp += B[j];//加えて検討する
    if (tmp >= mid) { //もし最低限の長さをクリアしていたら
      num += 1;//そこでカットして１本に
      tmp = 0;//一旦リセット
    }
    //最後まで行ったら残りを１本に
    if (j === k) num += 1;
  }

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

解答例(Python3の場合参考)

答えは整数であることがわかっているので、left と right の差が 1 以下になるまで狭めればよいです。

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 + 1];
while (right - left > 1) { //答えは整数なので差が1以下まででよい
  
  let mid = Math.trunc((left + right) / 2);//整数なので切り捨て

  let last_index = 0;//最後に太巻きを切った番号
  let parts = 0;//太巻きの本数
  for (let i = 0; i < k + 2; i++) { //太巻きの切れ目で切った時の本数
    //切った太巻き１本分の長さがmid以上になるように
    if (A[i] - A[last_index] >= mid) { //太巻き長さ＝末尾側切れ目ー先頭側切れ目
      parts += 1;//太巻き１本とする
      last_index = i;//最後に太巻きを切った番号
    }
  }
  //切った本数が少なかったら、もっと短くする
  if (parts < n) {
    right = mid;
  //多かったら、長く
  } else {
    left = mid;
  }
}
console.log(left);