はまやんはまやんはまやん

hamayanhamayan's blog

Fountain Walk [AtCoder Grand Contest 019 C]

http://agc019.contest.atcoder.jp/tasks/agc019_c

前提知識

解法

http://agc019.contest.atcoder.jp/submissions/1548182

まず、スタートが左下、ゴールがそれに対して右上となるように座標を変換する。
これは

  • X1 > X2であれば全てのX座標を10^8 - Xとする
  • Y1 > Y2であれば全てのY座標を10^8 - Yとする

ことで変換できる。
 
経路が最小となるパターンは、スタートからゴールまでなるべく多くの○を通るパターンである。
スタートとゴールへの最短経路のうち○が最も多くなる時の個数を計算するが、これはLISとなっていることが分かる。
これは○をX座標昇順で並べた時に、そのY座標の配列に対するLISが求めたい個数と一致している。
そのため、X座標昇順ソートして、Y座標に対してLISを取る。
 
1つ○を経由するごとに「20-5π」だけ経路を減らせるため、-LIS(20-5π)をすれば答え。
コーナーケースとして最後のサンプルのように円を直線に横切らないといけないパターンがあるが、
これはLIS=min(X2-X1,Y2-Y1)+1のときだけである。
これを満たさないということは空いたスペースがあるということで、ここで直進とならないパターンに変更できるためである。
直線に横切るため、追加で+5πをして答え

double PI = 2 * acos(0.0);
typedef long long ll;
string A;
int X1, Y1, X2, Y2, N, X[201010], Y[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X1 >> Y1 >> X2 >> Y2 >> N;
    rep(i, 0, N) cin >> X[i] >> Y[i];
    if (X1 > X2) {
        X1 = 100000000 - X1;
        X2 = 100000000 - X2;
        rep(i, 0, N) X[i] = 100000000 - X[i];
    }
    if (Y1 > Y2) {
        Y1 = 100000000 - Y1;
        Y2 = 100000000 - Y2;
        rep(i, 0, N) Y[i] = 100000000 - Y[i];
    }

    vector<pair<int, int>> v;
    rep(i, 0, N) if (Y1 <= Y[i] && Y[i] <= Y2 && X1 <= X[i] && X[i] <= X2) v.push_back({ X[i], Y[i] });
    sort(v.begin(), v.end());

    vector<int> vv;
    vv.push_back(-1);
    fore(p, v) vv.push_back(p.second);
    vv.push_back(INT_MAX / 2 - 1);
    LIS lis(vv);

    double ans = 100.0 * (X2 - X1 + Y2 - Y1);
    ans += (5.0 * PI - 20.0) * lis.lis;
    if (lis.lis == min(X2 - X1, Y2 - Y1) + 1) ans += 5.0 * PI;
    printf("%.15f\n", ans);
}