TopCoder SRM 623 Div1 Medium CatchTheBeat

面白い問題だった。
http://community.topcoder.com/stat?c=problem_statement&pm=12807

問題

２次元座標上、プレイヤーは初期状態で原点におり、X軸上を時速1で任意に移動できる。
ここで、N個のフルーツが座標(X[i],Y[i])になっており、これらのフルーツは時速1で落下していく。
フルーツがX軸を通過するとき、プレイヤーが同じ時刻に同じX座標にいれば、そのフルーツを獲得できる。

プレイヤーが最適に移動する場合、最大何個のフルーツを獲得できるか。

解法

フルーツが落ちるのではなく、プレイヤーのY座標時速1で上昇すると考える。
すると、プレイヤーは左上方向45度から右上方向45度の範囲に移動できることになる。

ここで、全ての座標を45度右に傾け、(x,y)→(y-x,x+y)と座標変換してみる。
すると、プレイヤーは変換後の座標上でX座標とY座標を増加する方向にしか移動できない。

後は、フルーツの座標を(変換後の)X座標でソートしてY座標を並べたとき、Longest Increasing Subsequenceの長さを求めればよい。
(ただし、本来のLISと異なり、Y座標が増加せず同じ値を連続しても良い点に注意。)

class CatchTheBeat {
	public:
	template<class CC> int LIS_num(vector<CC>& v) {
		int i,N=v.size();
		vector<CC> dp(N,(numeric_limits<CC>::max)()),id(N);
		FOR(i,v.size()) dp[id[i]=lower_bound(dp.begin(),dp.end(),v[i]) - dp.begin()] = v[i]-1;
		return *max_element(id.begin(),id.end())+1;
	}

	int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset) {
		int i;
		vector<ll> X(n,0),Y(n,0);
		vector<pair<int,ll> > P;
		X[0]=x0;
		Y[0]=y0;
		for(i=1;i<n;i++) {
			X[i]=(X[i-1]*(ll)a+b)%mod1;
			Y[i]=(Y[i-1]*(ll)c+d)%mod2;
		}
		FOR(i,n) {
			X[i]-=offset;
			if(Y[i]-X[i]<0 || X[i]+Y[i]<0) continue;
			P.push_back(make_pair(Y[i]-X[i],X[i]+Y[i]));
		}
		if(P.empty()) return 0;
		
		sort(P.begin(),P.end());
		vector<ll> V;
		ITR(it,P) V.push_back(it->second);
		return LIS_num(V);
	}
}

まとめ

座標変換するとX,Y座標が増加しかしない、と気づけば簡単。450ptだしね。
X,Y座標の移動速度が同じ場合、45度回転させてみるというテクニックは覚えておこう…。