[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;
}
この記事が気に入ったらサポートをしてみませんか?