面白い問題だった。
http://community.topcoder.com/stat?c=problem_statement&pm=12807
問題
2次元座標上、プレイヤーは初期状態で原点におり、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度回転させてみるというテクニックは覚えておこう…。