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

連番 (paizaランク A 相当)

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

連番の最大の長さで二分探索する。
正整数列 A = (A_1, A_2, ..., A_N) を先頭から順に見ていく。
cnt は現在見ている連番の長さ,sum はとりだした連番の個数として、
cntがmid以上になったら、とりだす。cntをリセットする。
また、Aの最後の要素でない、かつ、連番でないならば、cntをリセットする。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, k] = lines[0].split(" ").map(Number);
const a = lines[1].split(" ").map(Number);

//連番の最大の長さで二分探索
let [left, right] = [1, n + 1];
while (right - left > 1) { //連番の長さは整数なので１以下になれば良い
  const mid = Math.trunc((left + right) / 2);//連番の最大の長さ
 
  //cnt は現在見ている連番の長さ,sum はとりだした連番の個数
  let [cnt, sum] = [0, 0];
  //Aの要素を順番に見ていく
  for (let i = 0; i < n; i++) {
    cnt++;//Aのi要素を見る
    if (cnt >= mid) { //現在見ている連番の長さが最大mid以上になったら、とりだす
      sum++; //とりだす
      cnt = 0; //とりだしたらリセット
    }
    /*今見てる要素が最後なら、リセット、または、次が連番でないなら、リセット
    →今見てる要素が最後でない、かつ、次が連番でないなら、リセット*/
    if (i !== n - 1 && a[i] + 1 !== a[i + 1]) { 
      cnt = 0; //連番カウントリセット
    }
  }
  
  //切り出した数列の個数がK以上なら長く
  if (sum >= k) { 
    left = mid;
  } else { 
    right = mid;
  }
}
console.log(left);

解答例(Python3の場合参考)

k以上か判定する関数checkを定義。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, k] = lines[0].split(" ").map(Number);
const a = lines[1].split(" ").map(Number);

//長さxの連番の合計が K 以上の時は true，小さいときは false を返す
const check = x => {
  let cnt = 0;
  let sum = 0;
  for (let i = 0; i < n; i++) {
    cnt += 1;
    if (cnt >= x) {
      sum += 1;
      cnt = 0;
    }
    if (i !== 1) {
      if (a[i] + 1 !== a[i + 1]) {
        cnt = 0;
      }
    }
  }
  if (sum < k) {
    return false;
  } else {
    return true;
  }
};

//連番の最大の長さで二分探索
//leftは常に条件を満たす，rightは常に条件を満たさない
  let [left, right] = [1, 1 << 47];
while (right - left > 1) { //連番の長さは整数なので１以下になれば良い
  const mid = Math.trunc((left + right) / 2);//連番の最大の長さ
 
  //切り出した数列の個数がK以上か
  if (check(mid)) { 
    left = mid;
  } else { 
    right = mid;
  }
}
console.log(left);