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

垣根 (paizaランク B 相当)

誤答例

1秒ごとに全ての木についてK以上か判定しているとタイムオーバーする。

誤答

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);
//t秒ごとにすべての木の長さ判定
let t = 1; //t秒後
while (true) {
  let flag = true;//全ての木の高さがK以上ならtrue  
  //i本目の木の高さを求め、K以上か判定
  for (let i = 1; i <= N; i++) {
    const [A, B, C] = lines[i].split(" ").map(Number);
    const l = A * t ** 2 + B * t + C; //木の高さl
    if (l < K) {
      flag = false; //木の高さがKに満たなかったものがあれば抜ける
      break;
    }
  }  
  //全ての木の高さがK以上
  if (flag) {
    break;//探索終わり
  }  
  //高さK未満の木が１本でもあったら次の秒
  t++;
}

console.log(t);//すべての木の高さが K 以上になるのは何秒後か

解説

t秒の範囲1<=t<=1000000(10^6)において、二分探索をすると速く処理できる。

tの範囲について、最も小さいときは、t=1だが、
tが最も大きくなる時を考えると、1 = A_i, B_i, C_iかつK = 1,000,000,000,000 = 10^12の時。このとき、木の長さはt^2+t+1で、これがK=10^12以上になるには、木の長さにt^2があるのでt=10^6であればt^2=10^12となるので、tについては10^6まで考えれば良い。

解き方１：二分探索で選んだt秒において、それぞれの木について、長さがK以上になるか判定し、答えが求まるまで繰り返す

tの範囲、左端leftと右端rightの中間midについて、木の長さがK以上か判定する。
K以上ならmidをrightに、K未満ならmidをleftに更新して、再びmidについて木の長さを調べる。
繰り返して、rightとleftの差が1、すなわち、１つに決まったらその時のrightが求める値。

解き方２：それぞれの木について、二分探索でK以上になるt秒を求め、その中で最大値を求める

別解としては、それぞれの木について高さK以上になるtを二分探索で求め、その中から最大の値を求めてもよい。これも二分探索なので、速く処理ができる。

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

解説の通り、tの範囲1<=t<=1000000において、二分探索をする。

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);

//t秒の範囲で二分探索をする。
//t秒の範囲の左側(最小)をleft、右側(最大)をrightとする。
let [left, right] = [0, 1000001]; //1<=t<=1000000より1範囲外を初期値とする

while (right - left > 1) { //1つに決まるまで
  const mid = Math.trunc((left + right) / 2);
  
  let ok = true;//すべての木の高さがK以上ならtrue
  for (let i = 1; i <= N; i++) { //それぞれの木について
    const [A, B, C] = lines[i].split(" ").map(Number);
    //木の長さがK未満か調べる
    if (A * mid * mid + B * mid + C < K) {
      ok = false;
      break;
    }
  }
  
  //すべての木の高さがK以上ならば
  if (ok) {
    right = mid;
  //1本でもK未満なら  
  } else {
    left = mid;
  }
}
//すべての木の高さがK以上になる、最小の秒数はright
console.log(right);

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

別解の方法で解いてみる。

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);

let ans = 0; //求める値。すべての木がK以上になる秒数の最大値。

//それぞれの木について、K以上になる秒数を求める
for (let i = 1; i <= N; i++) { //それぞれの木について

    //t秒の範囲で二分探索をする。
    //t秒の範囲の左側(最小)をleft、右側(最大)をrightとする。
    let [left, right] = [0, 1000001]; //1<=t<=1000000より1範囲外を初期値とする
    
    while (right - left > 1) {
      const mid = Math.trunc((left + right) / 2);
  
      const [A, B, C] = lines[i].split(" ").map(Number);
      //木の長さがK以上か調べる
      if (A * mid * mid + B * mid + C >= K) {
        right = mid;
      } else {
        left = mid;
      }
    }
    
    //i本目の木がK以上になる秒数rightが、今まで求めたansより大きいか判定
    ans = Math.max(ans, right);
}

//すべての木の高さがK以上になる秒数ans
console.log(ans);

解答例(Pythonの場合参考)

関数を使います。

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);
//木の長さの二次元配列
const abc = lines.slice(1).map(line => line.split(" ").map(Number));

//木の長さを判定する関数check定義
const check = (t) => {
  for (let array of abc) {
    const A = array[0];
    const B = array[1];
    const C = array[2];
    if (A * t * t + B * t + C < K) {
      return 0; //falseの意
    }
  }
  return 1; //trueの意
};

//メイン
//leftは常に条件を満たさない，rightは常に条件を満たす
let [left, right] = [1, 1 << 24]; //tの初期値

while (right - left > 1) {
  const mid = Math.trunc((left + right) / 2);
  //木の長さがK以上か調べる
  if (check(mid)) {
    right = mid;
  } else {
    left = mid;
  }
} 
console.log(right); //K以上になるt秒はright 

解答例(参考別解(Python))

それぞれの木についてK以上となるt秒を求め、その中で最大の値を求めます。
関数を定義して使います。メインが短くなり、わかりやすくなります。

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);
//木の長さの二次元配列
const abc = lines.slice(1).map(line => line.split(" ").map(Number));

//木の長さを判定する関数check定義
const check = (i, t) => {
  const A = abc[i][0];
  const B = abc[i][1];
  const C = abc[i][2];
  if (A * t * t + B * t + C < K) {
    return 0;
  } else {
    return 1;
  }
};

//二分探索関数binaty_search定義
//i本目の木について、K以上になるt秒であるrightを求める
const binary_search = (i) => {
  //leftは常に条件を満たさない，rightは常に条件を満たす
  let [left, right] = [1, 1 << 24]; 
  while (right - left > 1) {
      const mid = Math.trunc((left + right) / 2);
      //木の長さがK以上か調べる
      if (check(i, mid)) {
        right = mid;
      } else {
        left = mid;
      }
  }  
  return right; //K以上になるt秒はright  
};

//メイン
let ans = 0; //求める値、すべての木がK以上になる秒数の最大値
//それぞれの木について、K以上になる秒数を求める
for (let i = 0; i < N; i++) { //それぞれの木について
    //i本目の木がK以上になる秒数rightが、今まで求めたtより大きいか判定
    ans = Math.max(ans, binary_search(i));
}
//すべての木の高さがK以上になる秒数ans
console.log(ans);