2008年日本情報オリンピック春合宿OJ Cheating: カンニング対策

問題へのリンク

問題概要

M人の受験者をN個の機械で監視するとき、機械がが監視しないといけない最大範囲を最小にしたときの値をもとめよ。

また監視はx,y両方の方向から行う。

制約

2 <= n <= 200,000
1 <= m <= 100,000
0 <= x,y <= 1,000,000,000

考えたこと

x方向,y方向それぞれ独立に考えることができる

最大範囲を二分探索で求めれそう

受験者が存在するx座標、y座標をソートしてX,Yに格納しておく。

最大範囲をmとするとき、あるi,j (i < j)に関してX[j] - X[i] <= mなら x座標がX[i]以上X[j]以下の受験者はひとつの機械で監視できる。同様のことがy方向に対しても言えるため、最大範囲を決めたとき貪欲的に必要な機械の数がわかる。

よって以下の方法でこの問題が解ける。

mを決める
必要な機械数を求める
必要な機械数がN以下ならmよりも小さい最大範囲で観測ができるか試す。Nより大きいなら最大範囲を大きくして試す。(二分探索)
mが定まるまで1〜3を繰り返す

#include <bits/stdc++.h>
#define INF 2000000000000000000
#define ll long long
using namespace std;

int main() {
  ll N, M;
  cin >> N >> M;
  vector<ll> X, Y;
  for (ll i = 0; i < M; ++i) {
    ll x, y;
    cin >> x >> y;
    X.push_back(x);
    Y.push_back(y);
  }
  sort(X.begin(), X.end());
  X.erase(unique(X.begin(), X.end()), X.end());//かぶってるx座標を1つにしている 　例{1, 1, 1, 2, 3, 3}  ⇒ {1, 2, 3}  
  sort(Y.begin(), Y.end());
  Y.erase(unique(Y.begin(), Y.end()), Y.end());
  ll l = -1, r = pow(10, 9);//二分探索の範囲を設定
  while (l + 1 != r) {
    //1.mを決める
    ll m = (l + r) / 2;

    //2.機械の数を数える
    ll cnt = 2;//機械の数　x,y方向に必ず1ずつは使うためcnt = 2始まり
    ll before = X.at(0);//beforeの位置に機械をおく
    for (ll i = 0; i < X.size(); ++i) {
      //一つ前の機械からの距離がmより大きいときは新しく機械を設置する
      if (X.at(i) - before > m) {
        cnt += 1;
        before = X.at(i);
      }
    }
    before = Y.at(0);
    for (ll i = 0; i < Y.size(); ++i) {
      if (Y.at(i) - before > m) {
        cnt += 1;
        before = Y.at(i);
      }
    }

    //3.機械の数によって探索する範囲を変更する
    if (cnt <= N) {
      r = m;
    }
    else {
      l = m;
    }
  }
  cout << r << "\n";
}