長い長い数列

二分探索メニュー【パイプを切り出そう・効率よく盗もう・太巻きを分けよう(おなかペコペコ・おなかいっぱい)・長い長い数列】

問題【STEP: 1】パイプを切り出そう
Task
n 本のパイプから k 本の同じ長さのパイプを切り出したい。切り出し可能な最大長は?

【パイプを切り出そう】コード 1/2

reader.on('close', () => {
   const [n, k] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);  // 入力を数値化して A で受取り
   let [left, right] = [0, Math.max(...A)];  // パイプの長さの[下限値,上限値]
   while (right - left > 0.000001) {  // 誤差が 0.000001 以上の間
      const mid = (left + right) / 2;  // 中央値
      let cut_out_num = 0;  // 切り出したパイプの数
      for (let i = 0; i < n; i++) {  // n 本のパイプを…
         cut_out_num += Math.floor(A[i] / mid);  // 中央値の長さに分割して切出せたパイプ数を加算
      if (cut_out_num >= k) {  // 切出した数が k 本以上になれば
         left = mid;  // パイプの長さの下限値を中央値で上書き(長くする)
            break;  // 処理を止める
         }
      }
      if (cut_out_num < k) {  // 切出せる数が k 本に満たなかった場合
         right = mid;  // パイプの長さの上限値を中央値で上書き(短くする)
      }
   }
   console.log(left.toFixed(6));
});
hogeちゃんの画像

切出すパイプの長さの上限値は A の最大値に設定。(下限値は 0)

誤差が 10^-6 (0.000001) 以下であれば正解とみなされます。

…なので ループの条件はright - left > 0.000001 の間に設定して

各パイプを 中央値の長さでカットした場合の切り出すことができるパイプ数を算出して kと比較しながら 上限値と下限値を狭めています。

何処から手を付けるべきかと悩みました。

top

【パイプを切り出そう】コード 2/2

reader.on('close', () => {
   const Pipe_length = (a, n, left, right, k) => {  // 配列, 要素数, 下限値, 上限値, 切り出す数
      if (right - left < 0.000001) {  // 誤差が既定値未満になったら…
         return left.toFixed(6);  // left を四捨五入して出力
      }
      const mid = (left + right) / 2;  // 中央値
      let cut_out_num = 0;  // 切り出したパイプの数
      for (let i = 0; i < n; i++) {
         cut_out_num += Math.floor(A[i] / mid);  // 各パイプを 中央値の長さに 分割して切り出した場合のパイプの数 を 加算
         if (cut_out_num >= k) {  // 切り出した数が k 本以上になれば
            return Pipe_length(a, n, mid, right, k);  // 下限値を mid にして再帰呼出し
         }
      }
      if (cut_out_num < k) {  // 切出せる数が k 本に満たなかった場合
         return Pipe_length(a, n, left, mid, k);  // パイプの長さの上限値を mid にして再帰呼出し
      }
   };
   const [N, K] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   console.log(Pipe_length(A, N, 0, Math.max(...A), K));
});
hogeちゃんの画像

コード 1/2 を再起関数にしました。

top
問題【STEP: 2】効率よく盗もう
Task
n 個の財宝の中から k 個の財宝を効率よく盗み出すと 平均価値は最大でいくつ?
※平均価値を  (価値の和) ÷ (重さの和) で定義

【効率よく盗もう】コード 1/2

reader.on('close', () => {
   const [n, k] = lines [0].split(' ').map(Number);  // n 個から k 個 選ぶ
   const W = lines [1].split(' ').map(Number);  // 重さ
   const V = lines [2].split(' ').map(Number);  // 価格(重さ*価値)
   let [left , right ] = [0, 5001];  // 検索範囲(平均価値)
   while (right - left > 0.000001) {  // 誤差が 0.000001 以上の間
      const v_value  = (left  + right) / 2;  // 仮想平均価値(検索範囲の中央値)
      const dif  = new Array(n);  // n 個の各財宝の実際の価格と(重さ*仮想平均価値)の差
      for (let i = 0; i < n; i ++) {
         dif [i] = V[i] - W[i] * v_value;  // 価格(重さ*価値) - 仮想価格(重さ*仮想平均価値)
      }
      dif.sort((s, b) => b - s);  // 降順に並替え
      const D = dif.slice(0, k).reduce((a, b) => a + b);  // k 個の価格と(重さ*仮想平均価値)の差
      if (D >= 0) {  // k 個の価格 - 仮想価格 が0以上なら
         left = v_value;  // 0 に近付くように 仮想価値 を上げる
      } else {  // k 個の価格 - 仮想価格 が 0 未満なら
         right = v_value;  // 0 に近付くように 仮想価値 を下げる
      }
   }
   console.log(left );
});
hogeちゃんの画像

(k 個の財宝の価格の和) / (k 個の財宝の重さの和) >= 仮想価値

上の式を変形すると…

(k 個の財宝の価格の和) – x * (k 個の財宝の重さの和) >= 0

(価格[1] – 仮想価値 * 重さ[1]) +  … + (価格[k] – 仮想価値 * 重さ[k]) >= 0

となるので (k 個の財宝の価格の和) – x * (k 個の財宝の重さの和) が 0 に近づくように２分探索…。

top

【効率よく盗もう】コード 2/2

reader.on('close', () => {　
   const Value = (n, left, right, k) => {　
      if (right - left < 0.000001) {　
         return left;　
      }
      const dif = [];　
      const mid = (left + right) / 2;　
      for (let i = 0; i < n; i++) {
         dif.push(V[i] - W[i] * mid);  // 価格(重さ*価値) - 仮想価格(重さ*仮想価値)
      }　
      dif.sort((s, b) => b - s);  // 降順に並替え
      const D = dif.slice(0, k).reduce((a, b) => a + b);  // k 個の価格と(重さ*仮想平均価値)の差
      if (D >= 0) {  // k 個の価格 - 仮想価格 が0以上なら…
         return Value(n, mid, right, k);  // left を mid にして再帰呼出し
      } else { // k 個の価格 - 仮想価格 が 0 未満なら
         return Value(n, left, mid, k);  // right を mid にして再帰呼出し
      }
   };
   const [N, K] = lines[0].split(' ').map(Number);  // N = 財宝数, K = 盗品数
   const W = lines[1].split(' ').map(Number);  // 重さ
   const V = lines[2].split(' ').map(Number);  // 価格(重さ*価値)
   console.log(Value(N, 0, 5001, K));
});
hogeちゃんの画像

コード 1/2 を再起関数にしました。

top
問題【STEP: 3】太巻きを分けよう (おなかペコペコ)
Task
k 個の切れ目が入った太巻きを n 人で分けた時 最も短い太巻きの長さは何センチ?
(皆がなるべくたくさん食べられるように分ける)

【太巻きを分けよう (おなかペコペコ)】コード 1/2

reader.on('close', () => { 
   const [L, n, k] = lines [0].split(' ').map(Number);
   const A = [0, ...lines [1].split(' ').map(Number), L ];  // 太巻きの両端と切り込みの位置
   let [left , right ] = [0, L ];  // 切り分ける長さの範囲
   while (right - left > 1) {
      let mid = Math.floor((left + right ) / 2);  // 切り分ける長さの中央値
      let l = 0;  // 左の切り分けた位置
      let slices = 0;  // 切り分けた数
      for (let r = 1; r < k + 2; r++) {
         if (A[r] - A[l] >= mid) {  // 長さが mid 以上になったら
            slices ++;  // 切り分ける
            l = r;  // l を切り分けた位置で更新して ループ継続
         }
      }
      if (slices < n) {  // 切り分けた数が人数分に満たなければ
         right = mid;  // サイズを縮小
      } else {  // 人数分以上あれば
         left = mid;  // サイズを拡張
      }
   }
   console.log(left );
});
hogeちゃんの画像

問題の意味を理解するのにかなり時間がかかった。

top

【太巻きを分けよう (おなかペコペコ)】コード 2/2

reader.on('close', () => {
   const binary_search = (n, min, max, k) => {
      if (max - min <= 1) {
         return min;
      }
      const mid = Math.floor((min + max) / 2);  // 切り分ける長さの中央値
      let l = 0;  // 左の切り分ける位置(切り分けた位置)
      let slices = 0;  // 切り分けた数
      for (let r = 1; r < k; r++) {
         if (A[r] - A[l] >= mid) {  // 長さが mid 以上になったら
            slices++;  // 切り分ける
            l = r;  // l を切り分けた位置で更新して ループ継続
         }
      }
      if (slices < n) {  // 切り分けた数が人数分に満たなければ…
      return binary_search(n, min, mid, k);
      } else {  // 人数分以上あれば
      return binary_search(n, mid, max, k);
      }
   };
   const [L, N, K] = lines[0].split(' ').map(Number);
   const A = [0, ...lines[1].split(' ').map(Number), L];  // 太巻きの両端と切り込みの位置
   console.log(binary_search(N, 0, L, K + 2));
});
hogeちゃんの画像

コード 1/2 を再起関数にしました。

top
問題【STEP: 4】太巻きを分けよう (おなかいっぱい)
Task
k 個の切れ目が入った太巻きを n 人で分けた時 最も長い太巻きの長さは何センチ?
(食べる量が少なくなるように分ける)

【太巻きを分けよう (おなかいっぱい)】コード 1/2

reader.on('close', () => {
   const [L, n, k] = lines [0].split(' ').map(Number);
   const A = [0, ...lines [1].split(' ').map(Number), L];  // 太巻きの両端と切り込みの位置
   const S = new Set();  // A を全ての切込みで切り離した場合の1個あたりのサイズ
   for (let i = 1; i < k + 2; i++) {
      S.add(A[i] - A[i - 1]);
   }
   let [left, right] = [Math.max(...S) - 1, L ];  // left は S の要素の最大値
   while (right - left > 1) {
      let mid = Math.floor((left + right ) / 2);
      let l = 0;  // 左の切り分けた位置
      let slices = 0;  // 切り分けた数
      for(let r = l + 1; r <= k + 2; r++){
         while (A[r] - A [l] <= mid) {
            r++;  // 次の切れ目へ
         } 
         slices++;
         l = r - 1;
      }
      if (slices > n) {  // 切り分けた数が人数分より多ければ…
         left = mid;  // 長く
      } else {  // 人数分に以下なら…
         right = mid;  // 短く
      }
   }
   console.log(right );
});
hogeちゃんの画像
とりあえずup。
top

【太巻きを分けよう (おなかいっぱい)】コード 2/2

reader.on('close', () => {
   const binary_search = (n, min, max, k) => {
      if (max - min <= 1) {
         return max;
      }
      const mid = Math.floor((min + max) / 2);  // 切り分ける長さの中央値
      let l = 0;  // 左の切り分ける位置(切り分けた位置)
      let slices = 0;  // 切り分けた数
      for (let r = l + 1; r <= k; r++) {
         while (A[r] - A[l] <= mid) {
            r++;  // 次の切れ目へ
         }
         slices++;
         l = r - 1;
      }
      if (slices > n) {  // 切り分けた数が人数分より多ければ…
         return binary_search(n, mid, max, k);  // 長く
      } else { // 人数分以下なら…
         return binary_search(n, min, mid, k);  // 短く
      }
   };
   const [L, N, K] = lines[0].split(' ').map(Number);
   const A = [0, ...lines[1].split(' ').map(Number), L];  // 太巻きの両端と切り込みの位置
   const S = new Set();  // A を全ての切込みで切り離した場合の1個あたりのサイズ
   for (let i = 1; i < K + 2; i++) {
      S.add(A[i] - A[i - 1]);
   }
   console.log(binary_search(N, Math.max(...S) - 1, L, K + 2));
});
hogeちゃんの画像

コード 1/2 を再起関数にしました。

top
問題【FINAL】長い長い数列
Task
n 行 m 列のマス目に書き込まれた数を昇順に並べたとき k 番目にくる値を求めてね。

【長い長い数列】コード

reader.on('close', () => {
   function binary_search(a, n, k) {
      let [left , right ] = [0, n];
      while (left < right ) {
         const mid = Math.floor((left + right ) / 2);
         if (a [mid] < k) {
            left = mid + 1;
         } else {
            right = mid;
        }
      }
      return right ;
   }
   const [n, m, k] = [lines [0], lines [2], lines [4]].map(Number);  //5 4 12
   const A = lines [1].split(' ').map(Number);
   const B = lines [3].split(' ').map(Number).sort((s , b ) => s - b );
   let [left , right ] = [-1, 200000000];
   while (right - left > 1) {
      const mid = Math.floor((left + right ) / 2);
      let smaller = 0;
      for (let i = 0; i < n; i ++) {
           smaller += binary_search(B, m, A [i ] + mid + 1) - binary_search(B, m, A [i ] - mid);
      }
      if (smaller < k) {
         left = mid;
      } else {
         right = mid;
      }
   }
   console.log(right );
});

  /* ランタイムエラーで45点
reader.on('close', () => {
  const [n, m, k] = [lines [0], lines [2], lines [4]].map(Number);  //5 4 12
  const A = lines [1].split(' ').map(Number);
  const B = lines [3].split(' ').map(Number);
  const Abs = [];
  // console.log(n,m,k);
  for (let i = 0; i < n; i ++) {
   Abs.push([]);
   for (let j = 0; j < m; j++) {
     Abs[i ].push(Math.abs(A [i ] - B[j]));
   }
  }
  console.log(Abs.flat().sort((s , b ) => s - b )[k - 1]);
});
*/
hogeちゃんの画像

とりあえずup。

top

コメント