二分探索の応用

皆さんご存知の二分探索。この応用について今回は書いていきたいと思う。

二分探索の一般化

二分探索とはつまり、範囲を特定することである。

億マス計算

そこで今回は二分探索を使う下記問題を解いていく

愚直に2重ループで解くと

O(N²)になるため、時間が足りなくなる

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {

  int N, M;
  cin >> N >> M;
  vector<long long> a(N);
  vector<long long> b(N);
  vector<long long> r(N * N);

  for (int i = 0; i < N; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < N; ++i) {
    cin >> b[i];
  }

  int ind = 0;
  // O(N)
  for (int i = 0; i < N; ++i) {
    // O(N)
    for (int j = 0; j < N; ++j) {
      r[ind] = a[i] * b[j];
      ind++;
    }
  }
  // O(log_N^2)
  sort(r.begin(), r.end());
  cout

これを二分探索 in 二分探索でとくと

O(log_(MAX(A)*MAX(B))*N*log_N)

で解けるようになる。

今回、 std:upper_bound を使う。

これは、指定した数よりも大きい最初のイテレータを返す。これを使用し、x以下の個数を求めることができる。

※内部で二分探索を使用している

詳細はこちら https://cpprefjp.github.io/reference/algorithm/upper_bound.html

std:upper_bound とstd:lower_boundの使い方は下記がわかりやすい

考え方ざっくり

掛け算した結果をもとに二分探索する(外側)
↑の結果をa[i]で割った数値以下の数値を二分探索で探し、カウントする

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
const long long INF = 1LL << 60;
int main() {
 
  int N, M;
  cin >> N >> M;
  vector<long long> a(N);
  vector<long long> b(N);
 
  for (int i = 0; i < N; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < N; ++i) {
    cin >> b[i];
  }
  // O(log_N)
  sort(b.begin(), b.end());
 
  long long left = 0;
  long long right = INF;
 
  // O(log_(MAX(A)*MAX(B)))
  while (right - left > 1) {
    long long mid = (right + left) / 2;
    long long cnt = 0;
    // O(N)
    for (int i = 0; i < N; ++i) {
      // O(log_N)
      cnt += upper_bound(b.begin(), b.end(), mid / a[i]) - b.begin();
    }
    if (cnt >= M) {
      right = mid;
    } else {
      left = mid;
    }
  }
 
  cout << right << endl;
}