paizaラーニング レベルアップ問題集 二分探索メニュー JavaScript 長い長い数列

長い長い数列 (paizaランク A 相当)

方針

大きな流れ：

０、ふつうに二重ループだと、処理が多すぎて、タイムオーバーする。(誤答例参照)

１、二分探索に持ち込めないか考える。
「k番目に小さい値」は、「数列に x 以下の値が k 個以上含まれるような値 x の最小値」と　言い換えられる。
→xを二分探索する。本問においてx=表に書き込まれる値| A_i - B_j |。

２、xの二分探索の中で、x=midとしたときの、| A_i - B_j |<=midとなる値の個数を、別の二分探索を利用して求める。

各解説

大きな流れ１の解説：二分探索に持ち込めないか考える。

言い換えられないか考えることが大事です。

数列の k 番目に小さい値は、
「数列に x 以下の値が k 個以上含まれるような値 x の最小値」
と言い換えることができます。

例えば、入力例1の| A_i - B_j |を計算した、以下の配列を考えます。
[
0, 0, 1, 1, 1, 1, 1,
2, 2, 2, 3, 3, 3, 3,
4, 4, 5, 5, 6, 7
]
数列のk=12番目に小さい値は3です。
言い換えると、
x以下の値が12個以上含まれるような値xの最小値は3です。
(x=2だと10個、x=3だと14個、x=4だと16個、故に３)

答えがわかっている状態で、xを二分探索してみます。
xを仮に決めてから、個数を求め、k個以上か判定します。

x探索範囲の、左端右端は、left=0,right=7。
仮に、真ん中のmid=(left+right)/2=4(切り捨て)から調べていきます。

この時mid=4以下の値の個数は16、k=12より大きい。最小xはもっと小さいので、midより大きい範囲は調べなくてよい。よって、right=mid=4。

探索2回目、mid=2、この時2以下の値の個数は10。k=12より小さいので、最小xはもっと大きいので、midより小さい範囲は調べなくてよい。よってleft=mid=2。

探索3回目、mid=(right+left)/2=(4+2)/2=3。３以下の値の個数は14。k=12より大きいので、right=3。

ここで、(right=3)-(left=2)=1なので、探索終了。
境目は2と３。数列にx以下の値がk=12個以上含まれる、最小値はx=3。

よって、right=3を出力する。

大きな流れ2の解説:x=midとした二分探索で、| A_i - B_j |<=midとなる値の個数の求め方。

2-1.| A_i - B_j |<=midについて式変形

絶対値の性質から、
これはA_i - B_j>=0のとき、A_i - B_j <=midなので、A_i - mid <=B_jと変形できる。
また、A_i - B_j<0のとき、-A_i + B_j <=midなので、B_j <= A_i + midと変形できる。
したがって、| A_i - B_j |<=midを満たすB_iは、

A_i - mid <=　B_j <= A_i + mid

と変形できる。

2-2.A_i - mid <=　B_j <= A_i + midを満たす値の個数の求め方

これは、
「①　A_i + mid < B_jを満たすBの最小のインデックス」　ー
「②A_i - mid <=　B_jを満たすBの最小のインデックス」
を求めればよい。(数直線をイメージするとわかりやすい)

②A_i - mid <=　B_jを満たすBの最小のインデックスは、
STEP: 2 lower_boundで習った、関数binary_searchを定義して、A_i-midを基準kとして、k<=B_jを満たすBの要素の、最小のインデックスを求めればよい。
すなわちbinary_search(B, B.length, A[i] - mid)で求まる。

①　A_i + mid < B_jを満たすBの最小のインデックスは、
STEP: 3 upper_boundで学んだが、
　A_i + mid + 1 <= B_jを満たすBの要素の最小のインデックスを求めればよい。
さらに、これも定義した関数binary_searchで、基準k=A_i + mid + 1としてk<=B_jを満たすBの要素の最小のインデックスを求める。
すなわち、binary_search(B, B.length, A[i] + mid + 1)で求まる。

以上から、| A_i - B_j |<=midとなる値の個数は、①-②の
binary_search(B, B.length, A[i] + mid + 1) - binary_search(B, B.length, A[i] - mid)
で求められる。
これを、変数smallerに、足し合わせていく。
1 ≦ i ≦ nについて、全て足し合わせたら、全体の合計個数smallerが求まる。

解答例(Python3 の場合参考)

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

//基準k以上を満たす配列Aの要素のインデックスの最小値を求める二分探索の関数定義(STEP: 2 lower_bound参照)
const binary_search = (A, n, k) => {//配列A、配列Aの要素の個数n、基準k
    let [left, right] = [0, n];
    while (left < right) {
        const mid = Math.trunc((left + right) / 2);
        if (A[mid] < k) { //A[mid]がk未満なら
            left = mid + 1;//mid以下も当然k未満になる
        } else { //A[mid]がk以上なら
            right = mid;//mid以上も当然k以上になる
        }    
    }
    return right;//基準k以上を満たす配列Aのインデックスの最小値
};

//入力
const [n] = lines[0].split(" ").map(Number);
const A = lines[1].split(" ").map(Number);
const [m] = lines[2].split(" ").map(Number);
const B = lines[3].split(" ").map(Number);
const [k] = lines[4].split(" ").map(Number);

//メイン
B.sort((a, b) => a - b);//小さい順にして、単調性を持たせ、二分探索ができるように。
let [left, right] = [-1, 200000000];//探索範囲
while (right - left > 1) {//答えは整数なので、差は1まで
    const mid = Math.trunc((left + right) / 2);//両端の真ん中
    let smaller = 0;//xより小さい値の個数をここに足し合わせていく
    //Aの各要素A_iについて、B_jと組み合わせた計算| A_i - B_j |<=midを考える
    for (let i = 0; i < n; i++) { 
        /* | A_i - B_j |<=midとなる値の個数を求める。
            →A_i - mid <=　B_j <= A_i + midとなる値の個数を求める
            →①`A_i + mid < B_j`を満たすBの最小のインデックス　ー　②`A_i - mid <=　B_j`を満たすBの最小のインデックス
            →①`A_i + mid + 1<=B_j`を満たすBの最小のインデックス　ー ②`A_i - mid <=　B_j`を満たすBの最小のインデックス
            →①binary_search(B, B.length, A[i] + mid + 1) - ②binary_search(B, B.length, A[i] - mid)
            ※詳しくは解説参照 */
        smaller += binary_search(B, B.length, A[i] + mid + 1) - 
                   binary_search(B, B.length, A[i] - mid);
    }    
    //midより小さい値の個数smallerがkより少ないなら、xはもっと大きい値
    if (smaller < k) {
        left = mid;
    //midより小さい値の個数smallerがk以上なら、xはもっと小さい値
    } else {
        right = mid;
    }    
}
console.log(right);//十分狭まったときの右端

誤答例

書き込まれる数 | A_i - B_j |を配列masuに入れ、小さい順に並べ、k番目を出力したが、一部正解だった。一部ランタイムエラーになっていたが、おそらく二重ループに時間がかかったと思われます。したがって、二分探索を用いて処理を早くする必要があります。

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

const [n] = lines[0].split(" ").map(Number);
const A = lines[1].split(" ").map(Number);
const [m] = lines[2].split(" ").map(Number);
const B = lines[3].split(" ").map(Number);
const [k] = lines[4].split(" ").map(Number);

let masu = [];
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    masu.push(Math.abs(A[i] - B[j]));
  }
}
console.log(masu.sort((a, b) => a - b)[k - 1]);