Mister雑記

競プロやります。

AGC019-C 「Fountain Walk」 (900)

AGCというよりARC寄り?な問題。 こういうのが自力で解けるととても嬉しい。

問題リンク

概要

x軸方向とy軸方向にそれぞれ 10^8本の道が 100m間隔で通っている。

この道の交差点上に N個の噴水がそれぞれ (X_i, Y_i)に置かれている。噴水は半径 10mの円形をしていて、その外周に道が通っている。また1つの道上に2つ以上の噴水が置かれていることはない

このとき、 (x_1, y_1)から (x_2, y_2)へ移動するための最短距離を求めよ。

公式の解説図は以下の通り。

制約

  •  0 \leq x_1, y_1, x_2, y_2, X_i, Y_i \lt 10^8
  •  1 \leq N \leq 2 \times 10^5
  •  i \neq jのとき、 X_i \neq X_jかつ Y_i \neq Y_j
  • スタートとゴールに噴水は置かれていない

解説

以降、 x_1 \lt x_2かつ y_1 \lt y_2として考える。

最短経路ということで、まずx正方向とy正方向に移動することだけ考えればいい。 この時点で (x_1, y_1) (x_2, y_2)を対頂角とする長方形に入っていない噴水は無視していいことがわかる。

そういったルートの中で、できるだけ多く噴水で曲がるようなルートを探すことを考える。 1つのルートで2つの噴水 i, jで曲がることができる条件は、 X_i \lt X_jかつ Y_i \lt Y_jが成立することである。 つまり任意の2つがこれを満たすような最大の噴水の組を見つけて、その回数分だけ噴水で曲がるとして答えを計算すればいい。

これを計算するには、以下のようにBinary Indexed Tree(BIT)を使えばいい。

  • 噴水を Xについてソートする。
  • 噴水の数だけ容量をもつBITを用意する
  • 以下のような手順で、 Xの小さい方から順に噴水を追加していく。
    • 自分よりY座標(key)が小さい中で、最も大きいvalueをもつものをBITで探す
    • その値に1を加えたものを Y_iにおけるvalueとして、BITを更新する

わかりにくいと思うが、上のBITは

  • 「噴水のY座標」をkey
  • 「その噴水を通る時点で最も多く曲がれる回数」をvalue

として保持している。

ちなみに制約からY座標をそのままkeyにすることは難しい。これを解決するために、一旦Y座標について座標圧縮を行う必要がある。

最後に、この問題にはコーナーケースが存在する。それが「曲がる噴水の数が長方形の幅と同じケース」である。

f:id:misteer:20180912113113p:plain

この場合、必ず1回は噴水を突っ切る必要があるため、その分のロスが生じる。

実装例

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;

#define SIZE(v) (static_cast<ll>((v).size()))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))

const double PI = acos(-1);


// BITオブジェクト、Range Maximum Queryバージョン
class BIT {
public:
    explicit BIT(ll N, ll v) : V_NUM(N) {
        data.resize(N);
        fill(ALL(data), v);
    }

    ll query(ll i) {
        ll ret = 0;
        while (i > 0) {
            ret = max(ret, data[i]);
            i -= (i & -i);
        }
        return ret;
    }

    void update(ll i, ll v) {
        while (i < V_NUM) {
            data[i] = max(data[i], v);
            i += (i & -i);
        }
    }

    ll V_NUM;
    V<ll> data;
};

// 座標(coordinate)を保持する構造体
struct coo {
    coo(ll _x = 0, ll _y = 0) : x(_x), y(_y){};
    ll x;
    ll y;
    
    // ソートするために比較演算子をオーバーロードする
    bool operator<(const coo& r) const {
        return x == r.x ? y < r.y : x < r.x;
    }
};

// Y座標で座圧をする
map<ll, ll> compress(const V<coo>& a) {
    set<ll> sety;
    for (coo c : a) {
        sety.insert(c.y);
    }

    map<ll, ll> ret;
    ll idx = 1;
    for (ll y : sety) {
        ret[y] = idx;
        ++idx;
    }

    return ret;
}

int main() {
    cout << fixed << setprecision(12);
  
    // startとgoal
    coo s, g;
    cin >> s.x >> s.y >> g.x >> g.y;

    // startの方が下にくるようにする
    if (s.y > g.y) swap(s, g);

    ll N;
    cin >> N;
    V<coo> a;
    // 長方形領域内にある噴水のみを記録する
    
    for (ll i = 0; i < N; ++i) {
        ll x, y;
        cin >> x >> y;
        if (y < s.y || g.y < y) continue;

        if (s.x < g.x) {
            if (s.x <= x && x <= g.x) {
                a.push_back(coo(x - s.x, y - s.y));
            }
        } else {
            // startとgoalのX座標が逆の場合はこっちも左右反転する
            if (g.x <= x && x <= s.x) {
                a.push_back(coo(s.x - x, y - g.y));
            }
        }
    }

    SORT(a);
    map<ll, ll> com = compress(a);

    BIT bit(SIZE(com) + 1, 0);

    for (coo c : a) {
        ll y = com[c.y];
        bit.update(y, bit.query(y) + 1);
        // bit.query(y)でy以下の最大値を求める
        // それに1加えた値で更新
    }

    // BIT全体の最大値が答え
    ll turn = bit.query(SIZE(com));

    double ans = (abs(g.x - s.x) + abs(g.y - s.y)) * 100;
    // 噴水を無視した場合の距離
    ans -= (20 - PI * 5) * turn;
    // 曲がる分だけ削れる
    
    // コーナーケース
    if (turn == abs(g.y - s.y) + 1 || turn == abs(g.x - s.x) + 1) ans += PI * 5;

    cout << ans << endl;
    return 0;
}

感想

  • 典型の積み重ねという感じが強くて面白い。
  • 座圧は実装コストがかなり高いのでライブラリとして持っておくのが吉かもしれない。
  • typo、許されません。