SRM614に参加。
Easyでちょっと時間を食ったけど、1Chal成功したおかげでそこそこの順位に。
おかげでHighest更新したけど、いい加減Mediumが解けないと先に進めないな…。
http://community.topcoder.com/stat?c=problem_statement&pm=12976
問題
2次元座標中でN個の格子点が与えられる。
この座標中で、4つの格子点で構成される軸に平行な正方形のうち、K個以上の点を含む面積最小の正方形を求めよ。
解法
この正方形は、以下のうち3つ以上を満たすはずである。
(2つだけ、たとえば上下辺だけ条件を満たすこともあるが、その場合左右辺は左右に動かしても条件を満たすので、左右に動かして3つ満たすようにできる)
- 正方形内の一番上の点より1大きなY座標に上辺がある。
- 正方形内の一番下の点より1小さなY座標に下辺がある。
- 正方形内の一番左の点より1小さなX座標に左辺がある。
- 正方形内の一番右の点より1大きなX座標に右辺がある。
この法則をもとにすると、各点の1つX座標が小さい位置は左辺、大きい位置は右辺の候補となるはずである。
このようにして、まず左辺の位置と右辺の位置を総当たりする。ここまでO(N^2)。
左辺と右辺を求めたら、その中に含まれる点をY座標でソートし、K個以上含む上辺・下辺を求め、右辺-左辺と上辺-下辺のうち大きい方を正方形の1辺とすればよい。
ソート処理がO(N logN)なので全体でO(N^3 logN)。
class MinimumSquare { int N; public: long long minArea(vector <int> x, vector <int> y, int K) { int i,j,k; ll ma=1LL<<62; N=x.size(); vector<ll> XX; FOR(i,N) XX.push_back(x[i]+1); FOR(i,N) XX.push_back(x[i]-1); sort(XX.begin(),XX.end()); FOR(i,XX.size()) for(j=i+1;j<XX.size();j++) { ll L=XX[i]; ll R=XX[j]; vector<ll> YY; FOR(k,N) { if(L<x[k] && x[k]<R) YY.push_back(y[k]); } sort(YY.begin(),YY.end()); for(k=0;k+K-1<YY.size();k++) { ll he=max(R-L,YY[k+K-1]-YY[k]+2); ma=min(ma,he*he); } } return ma; } }
まとめ
本番長方形と勘違いして無駄に時間をロスした。
1Chalしたのでよかったけど、それがなかったらかなり埋もれてたな…。