Div2 MediumはDiv1 Mediumをアレンジした問題。
そこそこ正答者は少ない。
http://community.topcoder.com/stat?c=problem_statement&pm=12928
問題
N個の長方形が与えられ、幅と高さがわかっているとする。
これらの長方形のうちいくつかを重ね、その共通部分がlimitを上回るようにしたい。
N個中任意の長方形を選択できるとき、最大何個重ねることができるか。
なお、長方形は90度回転させて幅と高さを逆にしてもよい。
解法
幅と高さを逆にできるので、まず各長方形で長い辺を幅とする。
次に各長方形を幅順で昇順ソートする。
照準ソートすると各長方形の幅の下限をX[i]として、i<=j
下限のとり方が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で異なる問題を作れるセンスは羨ましいね。