TopCoder SRM 580, Division 1, Level 1 ( Division 2, Level 2 ) : EelAndRabbit

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12575&rd=15500

概要

座標 0 にうさぎがいて、片側からうなぎが速度 1 で流れてくる。
i 番目のうなぎは時刻 で頭部が座標 0 を通り、 の長さをもつ。
うさぎは二度、うなぎを捕まえる事ができる。
うなぎを捕まえるとき、うさぎの目の前にいるうなぎをすべて捕まえることができる。
捕まえることができるうなぎの最大数を求めよ。

解法

t と l の情報から、初期状態でそれぞれのうなぎがどの座標からどの座標まで存在しているかが分かります。
うなぎは相対的な位置関係を変えずに流れてくるので、うなぎを取るタイミングを選ぶことは、初期状態に於いて二箇所の座標を選択することと言い換えられます。

うなぎの頭・尾の部分とその両隣ではない座標は必要がありませんので、はじめに座標圧縮をします。
その後、座標毎にそこにいるうなぎの番号を列挙します。
最後に、どの座標でうなぎを掴むかを全探索し、最大のものを探します。
座標が決まったときに捕まえられるうなぎの数は、それぞれの座標の集合の和集合の要素数になります。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#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 )

class EelAndRabbit
{
public:
	int getmax( vector <int> l, vector <int> t )
	{
		const int N = l.size();

		VI points;
		REP( i, 0, N )
		{
			points.PB( t[i] );
			points.PB( t[i] - 1 );
			points.PB( t[i] + 1 );
			points.PB( t[i] + l[i] );
			points.PB( t[i] + l[i] - 1 );
			points.PB( t[i] + l[i] + 1 );
		}
		sort( ALL( points ) );
		points.erase( unique( ALL( points ) ), points.end() );

		map<int,int> pos2idx;
		REP( i, 0, points.size() )
		{
			pos2idx[ points[i] ] = i;
		}

		VVI ary( points.size() );
		REP( i, 0, N )
		{
			for ( int p = pos2idx[ t[i] ]; points[p] <= t[i] + l[i]; p++ )
			{
				ary[p].PB( i );
			}
		}

		int res = 0;
		REP( i, 0, ary.size() )
		{
			REP( j, 0, ary.size() )
			{
				VI tmp;
				set_union( ALL( ary[i] ), ALL( ary[j] ), back_inserter( tmp ) );
				res = max<int>( res, tmp.size() );
			}
		}

		return res;
	}
};