TopCoder, SRM 623, Division 2, Level 1 : CatchTheBeatEasy

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13208&rd=15856

問題概要

　Division 1, Level 2 と同じゲームをする。
　全てのフルーツを拾得することができるか否か、判定せよ。
　N <= 50

解法

　プレイヤーキャラクターがフルーツに触れる順序は、与えられる添字の順序ではなく X 軸に落ちてくる順番です。従って、フルーツを X 軸上に落ちてくる時刻の昇順にソートしておくと処理が簡潔になります。このソートは、配列 x, y を ( Y 座標, X 座標 ) の順序対（ std::pair ）にパックして std:sort することで実現できます。
　ソート済み順序に於ける添字付けに於ける i 番のフルーツの X 座標・Y 座標を求める関数をそれぞれ X, Y と書きます。さて、i 番のフルーツが X 軸上に落ちてきてから、i + 1 番目のフルーツが落ちてくるまでの時間は Y( i + 1 ) - Y( i ) です。一方、この間にプレイヤーが移動しなければならない距離は | X( i + 1 ) - X( i ) | なので、Y( i + 1 ) - Y( i ) < | X( i + 1 ) - X( i ) ならば間に合いません。そうでなければ、i 番のフルーツを拾得してから i + 1 番のフルーツを拾得することができます。各有効な i についてこの判定をして、全ての i について連続的に拾得可能であれば、全体でも拾得可能であると言えます。
　ただし、最初のフルーツの扱いには注意が必要です。最初のフルーツの Y 座標が、その X 座標の絶対値より小さいとき、最初のフルーツを拾得できません。これを例外として別途判定してもよいのですが、初期座標 ( 0, 0 ) の仮想的なフルーツを予め配列に加えておくと統一的に扱うことができます。

コード

using PII = pair<int,int>;
using VPII = vector< pair<int,int> >;

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

#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

class CatchTheBeatEasy
{
public:
	string ableToCatchAll(vector <int> x, vector <int> y)
	{
		const int N = x.size();

		VPII ps( 1 );
		transform( ALL( y ), x.begin(), back_inserter( ps ), []( const int a, const int b ){ return MP( a, b ); } );
		sort( ALL( ps ) );

		REP( i, 0, N )
		{
			if ( ps[ i + 1 ].fst - ps[i].fst < abs( ps[i].snd - ps[ i + 1 ].snd ) )
			{
				return "Not able to catch";
			}
		}
		return "Able to catch";
	}
};