Google Code Jam 2011 Round1B

ぼろ負けでした。

集中力がなかったです。

変数名の重複とか、違う変数を参照していたりとか初歩的なミスが多すぎました。

Problem Bの二分探索が面白かったので簡単に解説。

基本的なアイディアはtに対して二分探索をかけます。与えられたtに対してすべての商人がdの間隔を保って拡散できるなら、tを小さく、できないならtを大きくします。

問題は、与えられたtに対して、商人が十分に拡散できるかどうか。。

これは一番左にいる商人から処理をしていけばいいです。一番左の人は他の人からより離れるためできる限り左に行きます。左から二番目の人も同様にできる限り（一番左の人との間隔がd以下にならない範囲で）左にいきます。これを続ければいいです。

途中で、どうがんばっても自分の左の人からd以上離れることができないとなった時点で、そのtでは十分に拡散できないと判断します。

ということで、binary search + greedyで解ける問題でした。

以下練習で通したソース。

largeの問題は、商人の人数および、間隔dが10^6なので、二分探索の上限は10^6 * 10^6程度です。ちょっと余裕をもって10^13としています。

int main() {
    int t;
    cin >> t;

    REP(ii, t) {
        int c, d;
        cin >> c >> d;

        int v, vs = 0;
        vector<int>ps;
        int p;
        REP(i, c) {
            cin >> p >> v;
            vs += v;
            REP(j, v)
                ps.push_back(p);
        }
        SORT(ps);
        double hi = 1.0E+13;    // 10^6 * 10^6 < 10^13
        double lo = 0;
        double ret;

        REP(i, 100) {
            ret = (hi + lo) / 2;

            bool ck = true;
            double next = -1e100;    // -inf
            REP(j, vs) {
                if (ps[j] + ret < next) {
                    ck = false;
                    break;
                }
                next = MAX(next + d, ps[j]- ret + d);
            }
            if (ck)
                hi = ret;
            else
                lo = ret;
        }
        printf("Case #%d: %lf\n", ii+1,ret);
    }

    return 0;
}