TopCoder SRM 602 Div2 Medium PilingRectsDiv2

Div2 MediumはDiv1 Mediumをアレンジした問題。
そこそこ正答者は少ない。
http://community.topcoder.com/stat?c=problem_statement&pm=12928

問題

N個の長方形が与えられ、幅と高さがわかっているとする。
これらの長方形のうちいくつかを重ね、その共通部分がlimitを上回るようにしたい。
N個中任意の長方形を選択できるとき、最大何個重ねることができるか。

なお、長方形は90度回転させて幅と高さを逆にしてもよい。

解法

幅と高さを逆にできるので、まず各長方形で長い辺を幅とする。
次に各長方形を幅順で昇順ソートする。

照準ソートすると各長方形の幅の下限をX[i]として、i<=j= limitとなる数を求めればよい。

下限のとり方がO(N)、それぞれX[i]*Y[j]の判定でO(N)かかるのでO(N^2)で終わる。

class PilingRectsDiv2 {
	public:
	int getmax(vector <int> X, vector <int> Y, int limit) {
		int L=X.size();
		int i,x,y,r,j;
		pair<int,int> P[1000];
		
		FOR(i,L) if(X[i]<Y[i]) swap(X[i],Y[i]);
		FOR(i,L) P[i]=make_pair(X[i],Y[i]);
		sort(P,P+L);
		
		r=-1;
		FOR(i,L) {
			vector<int> YY;
			x=0;
			for(j=i;j<L;j++) if(P[i].first*P[j].second >= limit) x++;
			if(x) r = max(r, x);
		}
		return r;
	}
};

まとめ

同じような題材で、うまくDiv1とDiv2で異なる問題を作れるセンスは羨ましいね。