極座標の街 / Town of polar coordinates [JOI2018 予選模試 C]

https://www.hackerrank.com/contests/joi2018/challenges/challenge-1716

解説

(x,y)から(a,b)への移動の最短ルートを考えてみよう。

x=0のとき
(0,0)からの移動は中央から一直線で行けるので、aだけかかる
　
a=0のとき
(0,0)への移動は中央へ一直線で行けるので、xだけかかる
　
そうでないとき
最短経路となる可能性が2択ある。
① xをあわせてから、時計回りまたは反時計回りでy座標をあわせる
abs(a - x) + min(1LL * abs(b - y), N - abs(b - y))
abs(a - x) := x座標をあわせるのに掛かるコスト
min(1LL * abs(b - y), N - abs(b - y)) := 時計回りabs(b - y)、または、反時計回りN - abs(b - y)で掛かるコスト
② 中心を経由して合わせる
(x,y) -> (0,0) -> (a,b)とするため、a+xかかる
どちらかの小さい方が最適戦略となる。
　
これをすべてのクエリで行うと答えが出る。

ll M, N; int Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> M >> N >> Q;
    int x = 0, y = 0;
    ll ans = 0;
    rep(q, 0, Q) {
        int a, b; cin >> a >> b;

        if (x == 0) ans += a;
        else if (a == 0) ans += x;
        else {
            ll opt = infl;
            chmin(opt, abs(a - x) + min(1LL * abs(b - y), N - abs(b - y)));
            chmin(opt, 1LL * a + x);
            ans += opt;
        }

        x = a;
        y = b;
    }
    cout << ans << endl;
}