kmjp's blog

競技プログラミング参加記です

TopCoder SRM 614 Div1 Easy MinimumSquare

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したのでよかったけど、それがなかったらかなり埋もれてたな…。