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としています。

view plainprint?

1. int main() {  
2.     int t;  
3.     cin >> t;  
4.   
5.     REP(ii, t) {  
6.         int c, d;  
7.         cin >> c >> d;  
8.   
9.         int v, vs = 0;  
10.         vector<int>ps;  
11.         int p;  
12.         REP(i, c) {  
13.             cin >> p >> v;  
14.             vs += v;  
15.             REP(j, v)  
16.                 ps.push_back(p);  
17.         }  
18.         SORT(ps);  
19.         double hi = 1.0E+13;    // 10^6 * 10^6 < 10^13  
20.         double lo = 0;  
21.         double ret;  
22.   
23.         REP(i, 100) {  
24.             ret = (hi + lo) / 2;  
25.   
26.             bool ck = true;  
27.             double next = -1e100;    // -inf  
28.             REP(j, vs) {  
29.                 if (ps[j] + ret < next) {  
30.                     ck = false;  
31.                     break;  
32.                 }  
33.                 next = MAX(next + d, ps[j]- ret + d);  
34.             }  
35.             if (ck)  
36.                 hi = ret;  
37.             else  
38.                 lo = ret;  
39.         }  
40.         printf("Case #%d: %lf\n", ii+1,ret);  
41.     }  
42.   
43.     return 0;  
44. }  

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;
}