torus711 のアレ

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

TopCoder, Single Round Match 645, Division 1, Level 1 : JanuszTheBusinessman

問題概要

 Janusz はホテルを経営している.今年宿泊を予定している客について到着する日と出発する日が分かっていて,i 番の客は,arrivals_i に到着して,departures_i に出立する.
 Janusz は,全ての客によい評価のレビューをしてもらいたいと考えている.そこで,何人かの客に特別な宣伝をすることにした.特別な宣伝をされた客は,よい評価のレビューをする.また,特別な宣伝をされた客に会った客も,よい評価のレビューをする.
 2 人の客が「会う」とは,この 2 人の客がどちらもホテルに居る日が存在することと同値である(到着日と出立日を含む).
 Janusz は特別な宣伝を行う回数をできるだけ少なくしたい.全ての客がよいレビューをしてくれるようにするために必要な,特別な宣伝の回数を求めよ.

解法

 |arrivals| = N と書きます.
 特別な宣伝を行う客を何人か決めた状態を考えます.このとき,直接宣伝されず,かつ宣伝された客に会うこともない客には,直接的または間接的に宣伝をする必要があります.このような客の内,最も出立時間が早い客に着目します.この客を valid な状態にするためには,この客に宣伝を行うか,この客と会う客に宣伝をする必要があります.このとき,できるだけ長い期間をカバーできるように宣伝を行った方がよいので,この客と滞在区間が重複する客(この客自身を含む)の内で,最も遅くまで滞在する客に対して宣伝を行うのが最適な戦略となります.これを繰り返し適用することで,宣伝を行うべき客を全て決定できます.
 客の滞在期間を出立日をキーにソートしておくと,配列を走査する順序と客が処理される順序が一致するので,次に処理すべき invalid な客は簡単に発見できます.また,配列を後ろから走査することで,invalid な客と会う,最も出立が遅い客も O( N ) 時間で発見できます.従って,ソートの計算量を考慮しても,全体を O( N^2 ) 時間で実行できます.

コード

using PII = pair< int, int >;
using VPII = vector< PII >;
template < typename T = int > using VT = vector<T>;
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 SZ( v ) ( (int)( v ).size() )
#define BI back_inserter

#define MP make_pair
#define fst first
#define snd second

bool overlap( const PII &a, const PII &b )
{
	return !( b.snd < a.fst || a.snd < b.fst );
}

class JanuszTheBusinessman
{
public:
	int makeGuestsReturn( vector <int> arrivals, vector <int> departures )
	{
		const int N = SZ( arrivals );

		VPII ps;
		transform( ALL( arrivals ), departures.begin(), BI( ps ), []( const int a, const int b ){ return MP( a, b ); } );
		sort( ALL( ps ), []( const PII &a, const PII &b ){ return a.snd != b.snd ? a.snd < b.snd : a.fst < b.fst; } );

		int res = 0;
		VT< bool > done( N );
		REP( i, 0, N )
		{
			if ( done[i] )
			{
				continue;
			}

			const int t = find_if( ps.rbegin(), ps.rend(),
					bind( function< bool( PII, PII ) >( overlap ), _1, ps[i] )
					).base() - ps.begin() - 1;

			REP( j, 0, N )
			{
				done[j] = done[j] || overlap( ps[t], ps[j] );
			}

			++res;
		}

		return res;
	}
};