TopCoder SRM 629 Div1 Easy RectangleCovering

SRM629に参加。
EasyとMedium解いて3Challenge決めた、と思ったらEasyもMediumも凡ミスで落とした。
せっかくチャレンジでかなり高順位につけるチャンスだったのに…。
http://community.topcoder.com/stat?c=problem_statement&pm=13344

問題

H*Wの大きさの長方形の穴がある。
ここに幾つかの長方形の板が与えられるので、これで穴をふさぎたい。

板同士は以下のように配置する。

• 長方形の辺と穴の辺が平行になるように配置する。
• 板の４ツ角は穴でない場所に固定しなければならない。他の板があっても穴の上は不可。
• 板同士は重なっても良い。

最少の板で穴をふさぐとき、何枚の板が必要か。

解法

板を縦または横に並べて塞ぐことを考える。
例えば板を縦に並べるのであれば、穴を横に渡せる板のうち、縦幅の大きな順に穴をふさぐまで選択すればよい。
板を縦にしても横にしても穴の幅より大きいなら、縦幅が大きくなるように板を回転する必要がある。

class RectangleCovering {
	public:
	int minimumNumber(int holeH, int holeW, vector <int> boardH, vector <int> boardW) {
		int N=boardH.size();
		int mi=1000;
		int i,j;
		
		FOR(i,2) {
			vector<ll> B;
			FOR(j,N) {
				int a=boardH[j],b=boardW[j];
				if(a>b) swap(a,b);
				if(b<=holeW) continue;
				if(a>holeW) B.push_back(b);
				else B.push_back(a);
			}
			sort(B.begin(),B.end());
			reverse(B.begin(),B.end());
			ll tot=0;
			FOR(j,B.size()) {
				tot+=B[j];
				if(tot>=holeH) mi=min(mi,j+1);
			}
			
			swap(holeH,holeW);
		}
		if(mi>=1000) return -1;
		return mi;
	}
}

まとめ

ちょっとややこしいけど、面白い問題かな。
今回はEasyの割に非常に正答率が低かった。