TopCoder SRM 718 Div2 Hard: ChainCity

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

次元座標上に点が 個並んでいる。ここに新たに点を 個まで追加することを考える。

点 から まで移動するときにかかる時間は、通常は 動くごとに 秒かかるが、新たに追加した点どうしは瞬時に移動でき、時間はかからない。このとき、任意の 点間の移動時間の最大値を最小化せよ。

解説

最大値の最小化なので、二分探索がしたい気持ちになります。この場合、どのように二分探索できるでしょうか？

最小値を にできるかを判定することを考えます。この判定は、長さ の区間を 個以下用いて、元からあった頂点すべてを被覆できるかどうかを見る ことで可能です。

なぜこれでうまくいくのでしょうか？まず、ひとつの区間に含まれている点どうしの移動時間は当然 以下なので条件を満たしています。また、異なる区間に含まれている点同士であったとしても、各区間の中点に相当するところに新たに点を (瞬間移動可能な点を) 置くことによって、最大で の移動時間になり、条件を満たしています。この区間の長さを短くしていくと、条件を満たすためにはより多くの区間が必要になるという単調性があり、この条件で二分探索が可能です。

ソースコード

class ChainCity {
    public:
    // 長さ x の区間を k 個まで使って全てを被覆できるか
    bool d(ll x, ll k, vector<int> dist) {
        ll ub = x, pos = 0, cnt = 1;
        for(size_t i=0; i<dist.size(); i++) {
            pos += dist[i];
            if(pos > ub) {
                ub = pos + x;
                cnt++;
            }
        }
        return cnt <= k;
    }
    int findMin(vector<int> dist, int k) {
        ll lb = -1, ub = INF;
        while(ub - lb > 1) {
            ll mid = (lb + ub) / 2;
            (d(mid, k, dist) ? ub : lb) = mid;
        }
        return ub;
    }
};