問題概要
次のようなゲームをする。
- 2D ゲームである
- プレイヤーキャラクターの初期位置は原点 ( 0, 0 )
- プレイヤーキャラクターは X 軸上のみを移動することができ、その速度は 1 である
- 開始と同時に N 個のフルーツが出現する
- i 番のフルーツの初期座標は ( x[ i ], y[ i ] ) である
- 各フルーツは、速度 1 で下方向（ Y 軸マイナス方向）に移動する
- プレイヤーキャラクターとフルーツが同じ座標に存在したとき、プレイヤーキャラクターはそのフルーツを拾得する
最適にプレイしたとき、いくつのフルーツを拾うことができるか、求めよ。
N <= 500,000
解法
フルーツが落ちてくるのではなく、プレイヤーキャラクターが常に Y 軸正方向に速度 1 で動いていると考えます。このとき、プレイヤーキャラクターの移動方向は Y 軸正方向からの角度（の絶対値）が 以下となる向きです。分かりにくいので原点を中心に右へ
傾けると、プレイヤーキャラクターの移動方向は座標の値が広義単調増加する方向となります。座標の回転は、回転行列を用いることで簡単に書くことができます。
などの絶対値は
ですが、今回は移動の角度だけに着目しているので、符号のみを取り出して（全体を
倍にして）、座標 ( x, y ) から ( x + y, -x + y ) に写してしまって大丈夫で、おそらくこの方が色々楽です。また、回転後にいずれかの座標が負になる点には絶対に移動できないので、予め remove しておくと無駄な条件分岐が発生せずに済みます。
回転後の座標を順序対にして昇順ソートしたとすると、X 座標に関しては、i < j であるような i, j についてこの順で拾得することしかできません。座標に関する制約はソートした段階で充足されているので、X 座標について深く考える必要はありません。一方 Y 座標に関しては、i < j であって、Y( i ) <= Y( j ) であるような i, j をこの順で拾得しなければなりません。Y 座標だけを取り出した列を考えると、これは広義単調増加部分列です。拾得するフルーツの数を最大化するのが目的なので、そのような列の中で最長のものを求めることで、問題に対する答えを得ることができます。
N の最大値がそれなりに大きいので、二分探索を用いて で計算する動的計画法（蟻本参照）を適用する必要があります。
コード
using LL = long long; using VI = vector<int>; using PII = pair<int,int>; using VPII = vector< pair<int,int> >; template < typename T = int > using LIM = numeric_limits<T>; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( e, c ) for ( auto &e : c ) #define ALL( c ) (c).begin(), (c).end() #define MP( a, b ) make_pair( ( a ), ( b ) ) #define fst first #define snd second const int INF = LIM<>::max() / 2; class CatchTheBeat { public: int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset) { VI xs = generate( n, x0, a, b, mod1 ); VI ys = generate( n, y0, c, d, mod2 ); transform( ALL( xs ), xs.begin(), bind( minus<int>(), _1, offset ) ); VPII ps( n ); REP( i, 0, n ) { ps[i] = MP( xs[i] + ys[i], -xs[i] + ys[i] ); } ps.emplace_back( 0, 0 ); ps.erase( remove_if( ALL( ps ), []( const PII &p ){ return min( p.fst, p.snd ) < 0; } ), ps.end() ); sort( ALL( ps ) ); VI as; transform( ALL( ps ), back_inserter( as ), []( const PII &p ){ return p.snd; } ); const int M = as.size(); VI dp( M + 1, INF ); FOR( a, as ) { *upper_bound( ALL( dp ), a ) = a; } return lower_bound( ALL( dp ), INF ) - dp.begin() - 1; } VI generate( const int n, const int x0, const int a, const int b, const int mod ) { VI res( n ); res[0] = x0; REP( i, 1, n ) { res[i] = ( LL( res[ i - 1 ] ) * a + b ) % mod; } return res; } };
