LoginSignup
0
0

More than 1 year has passed since last update.

@ZampieriIsa

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

Last updated at Posted at 2023-02-15

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

解説

大きな流れ

  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++の場合参考)

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)]ように、もっとスマートにしたかったのですが、何か良い方法をご存知の方がいればコメントください。

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でもできます。

const [a, l] = al.reduce((acc, cur) => {
  acc[0].push(cur[0]);
  acc[1].push(cur[1]);
  return acc;
}, [[], []]);

同様の場所、１行短く。

const [a, l] = al.reduce((acc, cur) => {
  acc.map((v, i) => v.push(cur[i]))
  return acc;
}, [[], []]);

誤答例

普通に二重ループで解くとタイムオーバーします。
また、条件が複雑です。

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0