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

パーティー (paizaランク A 相当)

https://paiza.jp/works/mondai/binary_search_advanced/binary_search_advanced__party


# 解説
大きな流れ

1. 普通に二重ループで計算すると条件が煩雑かつタイムオーバー→条件を簡単にできないか、二分探索できないか考える。

2. 条件を簡単に：同時にパーティーに参加していた人の合計人数=全人数-同時に参加しなかった人数=全人数-(その人が来る前にいた人数＋その人が帰った後に来た人数)

3. a,lを昇順にソートできるので、二分探索できる!

4. 二分探索ができるので、条件を満たす最小インデックスを返す、関数binary_searchを用いて、その人が来る前にいた人数と、その人が帰った後に来た人数を求める。

5. 以上から、同時にパーティーに参加していた人の合計人数が求まる。

***
## 1.普通に計算
普通に計算すると、タイムオーバーします。誤答例参照。

## 2.条件を簡単に
同時に参加していなかった人数を求めたほうが簡単です。(*)

その人がパーティーに参加していた時刻と重なりがなければよいので、
その人より先に帰ったか、その人より後に来たかのどちらか。

i番目の人が来たのがa_i、帰ったのがl_i、
i番目の人以外のj　番目の人が来たのがa_j,帰ったのがl_jとすると、

i 番目の人を考えたとき、a_i より小さい l_j の個数と、l_i より大きい a_j の個数の合計が、同時に参加していなかった人数になります。

(*の理由:a,lをA,Lとして、
同時に参加した人を求めると、
`(A_i <= A_j && A_j <= L_i) || (A_i <= L_j && L_j <= L_i)`の個数の合計。
同時に参加していなかった人数は、
`L_j < A_i` の個数と`L_i < A_j`の個数の合計で求められる。
式の複雑さを見ると、後者の方が簡単)


## 3.二分探索ができないか考える。

人数を求めればよく、どの人かは特定しなくて良いので、人の順番はバラバラにして良い。よって、ソートできる。

また、l_j < a_i の個数とl_i < a_jの個数の合計を求めるとき、aとlはバラして、それぞれソートできる。なぜなら、i番目の人を見るとき、j番目の人が重ならない条件l_j < a_iまたはl_i < a_jで、必然と(a_j < l_j) < a_iまたはl_i < (a_j < l_j)のどちらかになり、重複してカウントされることはないから。
よって、配列a,lでバラして、それぞれ昇順ソートができる。
a,lが単調増加するので、二分探索ができる。

## 4.条件を満たす人数を求める
配列インデックスの数直線をイメージする。

i番目の人より、先に帰った人の人数は、
配列lをソートした内、l_j < a_iを満たす人数
＝配列lをソートした内、a_i <= l_jを満たす最小のインデックスj。
(参照：paizaスキルアップ問題集、二分探索メニュー、STEP: 2 lower_bound)

i番目の人より、後に来た人の人数は、
配列aをソートした内、l_i < a_jを満たす人数
=(全人数-l_i < a_jを満たす最小のインデックスj)。
(参照：paizaスキルアップ問題集、二分探索メニュー、STEP: 3 upper_bound)


## 5. 同時にパーティーに参加していた人の合計人数を求める。
最終的な答えは、
その人と同時にパーティーに参加していた人の合計人数
=(他人の人数n-1)-同時に参加しなかった人数
=(他人の人数n-1)-(その人が来る前にいた人数＋その人が帰った後に来た人数)
で求まる。

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

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

//二分探索の関数定義
/**
    A_i >= k を満たす最小の インデックス を返す
    A_i >= k を満たす インデックス が存在しない場合は n を返す
*/
const binary_search = (A, n, k) => {//(A : 数列, n : 数列のサイズ, k : 基準)
    // 探索範囲 [left, right]
    let left = 0;
    let right = n;
    
    // 探索範囲を狭めていく
    while (left < right) {
        // 探索範囲の中央
        const mid = Math.trunc((left + right) / 2);

        if (A[mid] < k) {
            // A[0] ~ A[mid] は k 未満なので調べる必要が無い
            left = mid+1;
        } else {
            right = mid;
        }    
    }
    // 狭め終わったら最小のインデックスを返す
    return right;
};

//メイン
const [n] = lines[0].split(" ").map(Number);
//配列a,lとソートするsortedを用意する
const [a, l, a_sorted, l_sorted] = [Array(n), Array(n), Array(n), Array(n)];
//中身を入れる
for (let i = 0; i < n; i++) {
  [a[i], l[i]] = lines[i + 1].split(" ").map(Number);
  a_sorted[i] = a[i];
  l_sorted[i] = l[i];
}
//昇順にソートする
a_sorted.sort((a, b) => a - b);
l_sorted.sort((a, b) => a - b);

//i番目の人が来る前の人数と帰った後の人数の合計を求める
for (let i = 0; i < n; i++) {
  //i番目の人が来る前の人数before
  let before = binary_search(l_sorted, n, a[i]);//a[i]<=l_sorted_jを満たす最小のインデックス
  //i番目の人が帰った後の人数after
  let after = n - binary_search(a_sorted, n, l[i] + 1);//全人数-(a[i]<a_sorted[j]を満たす最小のインデックス)
  //同時にいた人＝他人の人数n-1 - 同時にいなかった人数
  console.log(n-1 - (before + after));
}
```
# 解答例(Pythonの場合参考)
メインの入力のところ、alにまとめてから、a,lに分けるところが違うだけです。
pythonの`a,l = [list(i) for i in zip(*al)]`ように、もっとスマートにしたかったのですが、何か良い方法をご存知の方がいればコメントください。

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

//二分探索の関数定義
/**
    A_i >= k を満たす最小の インデックス を返す
    A_i >= k を満たす インデックス が存在しない場合は n を返す
*/
const binary_search = (A, n, k) => {//(A : 数列, n : 数列のサイズ, k : 基準)
    // 探索範囲 [left, right]
    let left = 0;
    let right = n;
    
    // 探索範囲を狭めていく
    while (left < right) {
        // 探索範囲の中央
        const mid = Math.trunc((left + right) / 2);

        if (A[mid] < k) {
            // A[0] ~ A[mid] は k 未満なので調べる必要が無い
            left = mid+1;
        } else {
            right = mid;
        }    
    }
    // 狭め終わったら最小のインデックスを返す
    return right;
};

//メイン
const [n] = lines[0].split(" ").map(Number);
const al = lines.slice(1).map(line => line.split(" ").map(Number));
const [a, l] = [[], []];
for (let i = 0; i < n; i++) {
  a[i] = al[i][0];
  l[i] = al[i][1];
}

//昇順にソートする
a.sort((a, b) => a - b);
l.sort((a, b) => a - b);

//i番目の人が来る前の人数と帰った後の人数の合計を求める
for (let i = 0; i < n; i++) {
  //i番目の人が来る前の人数
  let before = binary_search(l, n, al[i][0]);
  //i番目の人が帰った後の人数
  let after = n - binary_search(a, n, al[i][1] + 1);
  //同時にいた人＝他人の人数-同時にいなかった人数
  console.log(n-1 - (before + after));
}
```
メイン入力const[a,l]のところ、reduceでもできます。
```javascript
const [a, l] = al.reduce((acc, cur) => {
  acc[0].push(cur[0]);
  acc[1].push(cur[1]);
  return acc;
}, [[], []]);
```
同様の場所、１行短く。
```javascript
const [a, l] = al.reduce((acc, cur) => {
  acc.map((v, i) => v.push(cur[i]))
  return acc;
}, [[], []]);
```


# 誤答例
普通に二重ループで解くとタイムオーバーします。
また、条件が複雑です。
```javascript
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);

//i番目の人
for (let i = 1; i <= N; i++) {
  const [A_i, L_i] = lines[i].split(" ").map(Number);
  const meet = Array(N).fill(0);
  
  //i以外の人を調べる
  for (let j = 1; j <= N; j++) {
    if (j === i) continue;//i以外
    const [A_j, L_j] = lines[j].split(" ").map(Number);
    if ((A_i <= A_j && A_j <= L_i) || (A_i <= L_j && L_j <= L_i)) { //条件が複雑
      meet[j] = 1;
    }
  }  
  //その人と同時にパーティーに参加していた人の合計人数
  console.log(meet.reduce((a, b) => a + b));
}
```