SRM623 Div1 Medium "CatchTheBeat"
問題
TopCoder Statistics - Problem Statement
訳
"osu!"というゲームのモードの1つに"catch the best"と呼ばれるものがある。このモードでは、落ちてくるフルーツをキャッチするため、キャラクターを動かす。
このゲームは画面は(ファミコンのマリオみたいな)横視点となる。簡単のため、キャラクターとフルーツの両方を平面上の点とする。
ゲームを始めると、まずキャラクターは(0, 0)の位置にいる。子のキャラクターはx軸方向(横方向)にしか動かすことができない。移動スピードは1秒につき距離1となる。例えば(-2, 0)から(1, 0)まで移動するのに少なくとも3秒を要する。
キャラクターのほか、フルーツがn個ある。フルーツには0からn-1の番号が付けられている。i番目のフルーツは、ゲーム開始時には(x[i], y[i])の位置にある。全てのフルーツは1秒につき距離1という一定のスピードで落ちてくる。つまり、あるフルーツが現在(xf, yf)にあるとすると、t秒後には(xf, yf - t)の位置にあるだろう。ある瞬間に、キャラクターとフルーツが同じ場所にある場合、そのフルーツを拾うことができる。
上記で用いたフルーツの位置x, yは次のような擬似コードで生成される。
x[0] = x0 for i = 1 to n-1: x[i] = (x[i-1] * a + b) % mod1 for i = 0 to n-1: x[i] = x[i] - offset y[0] = y0 for i = 1 to n-1: y[i] = (y[i-1] * c + d) % mod2
あなたは上記の擬似コードで用いた整数を全て与えられる。拾うことができるフルーツの最大値を返せ。
制約
1 <= フルーツの数 <= 500,000
0 <= x[i], y[i] < 10^9
考えたこと
2時間考えたが、あきらめカンニング
TopCoder SRM 623 Div1 Medium CatchTheBeat - kmjp's blog
コチラを参考にしましたm(_ _)m
45度変換かー
まさか単純なLISにまで帰着できるとはな・・・
ちなみにカンニングした後、実装だけで40分かかった。
とても本番中にできる気がしない・・・
実装力も足りない・・・
ソースコード
const int MAX_N = 500050; const int INF = (int)2e9 + 50; int x[MAX_N], y[MAX_N]; vector<pair<int, int>> p; vector<int> v; vector<int> dp; 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) { p.clear(); v.clear(); dp.clear(); // フルーツ生成 x[0] = x0; for (int i = 1; i < n; i++) { x[i] = ((long long)x[i - 1] * a + b) % mod1; } for (int i = 0; i < n; i++) { x[i] -= offset; } y[0] = y0; for (int i = 1; i < n; i++) { y[i] = ((long long)y[i - 1] * c + d) % mod2; } // 45度傾ける for (int i = 0; i < n; i++) { int px = y[i] + x[i]; int py = y[i] - x[i]; if (px < 0 || py < 0) continue; p.push_back(make_pair(px, py)); } // x軸->y軸でソート sort(p.begin(), p.end()); // y座標を並べる for (int i = 0; i < p.size(); i++) { v.push_back(p[i].second); dp.push_back(INF); } dp.push_back(INF); dp.push_back(INF); // 最長部分増加列 dp[0] = 0; for (int i = 0; i < v.size(); i++) { *upper_bound(dp.begin(), dp.end(), v[i]) = v[i]; } // 答え for (int i = 1; i < dp.size(); i++) { if (dp[i] == INF) return i - 1; } return -1; } };