[ABC330] F - Minimize Bounding Square

[Q] F - Minimize Bounding Square

のこり70分。正方形の辺の値で二分探索。
なんとなく中央値に寄せるのが最適？と思い、{xの中央値,yの中央値}を中心とした正方形で試すが、違うらしい。

のこり50分。xとyをそれぞれ独立に考えればいいと気づく。
このとき、スタート地点となる正方形の左辺と上辺を三分探索して、最も移動距離の小さいスタート地点を求めればよかった。

のこり35分。いったと思いきや、8ケースでTLE。
三分探索する箇所をO(N)で探しているところがダメらしい。累積和で高速化できるのはすぐに気づく

のこり20分。不具合が取れないよ？なんで？頭が混乱している？？

のこり-10分。AC。ただの累積値のindexずれ。

考察
1. 正方形の辺の大きさで二分探索
2. 正方形をどこに設置しよう？
3. xとyを独立して考えられる。xについて考える。昇順でソートする。
xの点を正方形に収めるような最小の移動コストはなんだろう？
二分探索の値で幅が固定されていて、スタート地点を任意に選べる状況なので、スタート地点を知りたい。
4. スタート地点を三分探索すればいい。
5. コストはO(N)で求めるとTLEになってしまうので、累積和を利用する。
6. スタート地点sよりも左側の要素が、sに移動するためにコストがどれだけかかるかと、
スタート地点s+幅wより右側の要素が、s+wに移動するためにコストがどれだけかかるかを求めればいい。
7. xの最小の移動コストと、yの最小コストの和がK以下なら、正方形が作れる。

実装

int main() {
  cincout();

  ll N, K;
  cin >> N >> K;
  vector<ll> X(N), Y(N);
  rep(i, N) {
    ll x, y;
    cin >> x >> y;
    X[i] = x;
    Y[i] = y;
  }
  // XとYを独立して考えるので、sortしてよい。
  sort(all(X));
  sort(all(Y));

  // 高速化のため累積和をとる
  vector<ll> accX(N + 1, 0), accY(N + 1, 0);
  rep(i, N) {
    accX[i + 1] = accX[i] + X[i];
    accY[i + 1] = accY[i] + Y[i];
  }

  // 三分探索。mid辺の正方形に収める場合の最小のコストを求める
  auto sabutan = [&](ll low, ll high, ll width, vector<ll> &V, vector<ll> &acc) -> ll {
    ll max_cost = oo;
    while (high - low > 2) {
      ll mid1 = (low * 2 + high) / 3;  // start地点
      ll mid2 = (low + high * 2) / 3;
      ll cost1 = 0, cost2 = 0;
      ll start1 = lower_bound(all(V), mid1) - begin(V);
      ll start2 = lower_bound(all(V), mid2) - begin(V);
      ll end1 = upper_bound(all(V), mid1 + width) - begin(V);
      ll end2 = upper_bound(all(V), mid2 + width) - begin(V);

      // mid1より左側の要素をmid1にもってくるコスト
      cost1 += (start1 * mid1 - acc[start1]);
      // mid1+widthより右側にある要素をmid1+widthに持ってくるコスト
      cost1 += acc[N] - acc[end1] - (mid1 + width) * (N - end1);

      cost2 += (start2 * mid2 - acc[start2]);
      cost2 += acc[N] - acc[end2] - (mid2 + width) * (N - end2);
      if (cost1 < cost2)
        high = mid2;
      else
        low = mid1;
      chmin(max_cost, min(cost1, cost2));
    }

  // 二分探索。答えとなる正方形の大きさを探索する。
  auto nibutan = [&](ll low, ll high) -> ll {
    while (high - low > 1) {
      ll mid = (low + high) / 2;

      // mid辺の正方形に収める場合の最小のコストを求める
      ll cost = sabutan(-1, 1e9, mid, X, accX);
      cost += sabutan(-1, 1e9, mid, Y, accY);
      if (cost <= K)
        high = mid;  // でかくてもできる
      else
        low = mid;
    }
    return high;
  };
  cout << nibutan(-1, 1e9) << endl;
}

https://atcoder.jp/contests/abc330/submissions/47947587