torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, SRM 629, Division 1, Level 1 : RectangleCovering

問題概要

 サイズが holeH \times holeW である長方形の穴がある。また、長方形の板を複数枚もっていて、i 番目の板のサイズは boardH_i \times boardW_i である。この板たちを使って穴を塞ぎたい。板は回転させて配置してもよいが、板の辺は穴の辺に対して並行または直角でなければならない。また、板の角は穴の外側(辺上は不可)でなければならない。板同士が重なることは許容される。
 穴を完全に塞ぐために必要な板の枚数の最小値を求めよ。不可能な場合は -1 で示せ。

解法

 穴に対する板の位置の自由度は、実はそれほど高くありません。穴のいずれかの辺に対し、それより長い板の辺を対応させて配置するという配置のみが可能です。
 端から端まで一枚の板によって覆われる(穴側の)辺を固定したとします。このとき、各板に関してそれを使うことができるか判定することができて、

  • どちらの辺も、穴の辺の長さより長い → 短い方の辺を穴側の辺に当てる
  • 片方の辺だけ、穴の辺の長さより長い → その辺を穴側の辺に当てる
  • それ以外 → 使えない

となります。使える板の集合を求めたら、他方の向きの辺にだけ着目すればよくなります。残った部分問題は、整数の集合の部分集合で、和がある値以上になるものの内、要素数最小のものを求める問題になります。明らかに大きい要素から使った方が得になるので、この部分問題は貪欲法で簡単に解けます。

コード

using LL = long long;
using VI = vector<int>;
using PII = pair<int,int>;
template < typename T = int > using LIM = numeric_limits<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )

#define fst first
#define snd second

constexpr int INF = LIM<>::max();

class RectangleCovering
{
public:
	int minimumNumber( int holeH, int holeW, vector <int> boardH, vector <int> boardW )
	{
		const int res = min(
				solve( holeH, holeW, boardH, boardW ),
				solve( holeW, holeH, boardH, boardW ) );

		return res < INF ? res : -1;
	}

	int solve( const int s, const int L, const VI &hs, const VI &ws )
	{
		const int N = hs.size();

		VI as;
		REP( i, 0, N )
		{
			PII p = minmax( hs[i], ws[i] );
			if ( s < p.fst )
			{
				as.PB( p.snd );
			}
			else if ( s < p.snd )
			{
				as.PB( p.fst );
			}
		}
		sort( ALL( as ), greater<int>() );
		
		LL sum = 0;
		REP( i, 0, as.size() )
		{
			sum += as[i];
			if ( L <= sum )
			{
				return i + 1;
			}
		}

		return INF;
	}
};