WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};