SRM 629 DIV1 Easy - RectangleCovering (×)

September 19, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13344&rd=16060

長方形のホールがあり、縦と横の長さがわかっている。
また複数の長方形のボードが与えられ、それぞれのボードの縦と横の長さもわかっている。
ホールを覆うように複数のボードをつなげるとき、必要な最小のボードの数を求める。
ただし、ボードは重ねるようにしてつなげてもよいが、ホールにボードの角が覆われないようにする。

解き方

・普通に考えるとかなりの場合の数がありそう。
・なにか制約がないか例をあげてみる。
・あるボードが使えるかどうかは、そのうち小さい１辺がボードのどちらか１辺よりも大きくないといけない。
・これで使えるボードが選別できそう。

・ただ、それでも色々なつなげ方がありそう。
・角が覆われないようにする条件を満たすためには、ボードは縦一列、横一列のどちらかしか並べられない。
・これであとは上記を満たす長さのうち降順に並べればよさそう。

・System Failed

・ホールについて、縦に並べるか横に並べるか、両方の場合の検討が必要だった
・さらにボードについて、例外条件を見落としていた。
　ボードの縦横両方が１辺よりも大きければ大きい方を取る。
　そうでないとき、小さい方の辺が1辺より小さければ大きい方ととる。
　そのうえでつなげる方の辺以上の長さになればよい。

・System　Passed

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class RectangleCovering {

public:

int minimumNumber(int holeH, int holeW, vector<int> boardH, vector<int> boardW) {
int ret=1e+9;

FORE(x,0,2){
vector<int> vx;
FORE(i,0,boardH.size()){
int minx=min(boardH[i],boardW[i]);
int maxx=max(boardH[i],boardW[i]);

if(maxx<=holeW)continue;
if(minx>holeW)vx.push_back(maxx);
else vx.push_back(minx);
}
sort(vx.rbegin(),vx.rend());

int score=0;
FORE(i,0,vx.size()){
score+=vx[i];
if(score>=holeH)ret=min(ret,i+1);
}
swap(holeH,holeW);
}

return ret==1e+9 ? -1 : ret;
}

};

カバー