GCJ 2015 Qual B. Infinite House of Pancakes

2015/04/13 (Mon) gcj 二分探索

問題

https://code.google.com/codejam/contest/6224486/dashboard

人間が無限にいて、全員の前にその人の皿がおいてある。 初期状態で、そのうち $D$ 人の皿の上にはパンケーキが乗っていて、それ以外の人には無い。

あなたは 1 分毎に次の 2 つの操作のうちいずれかができる。

  • 皿にパンケーキが乗っている人全員に食べさせる。各人は 1 枚だけ食べることができる
  • 皿にパンケーキが乗っている人を 1 人選び、その人のパンケーキを任意の人の皿に任意の枚数だけ移す

全てのパンケーキを食べさせるのにかかる時間の最小値は？

方針

同時に食べる人数は多いほうが良いので、移動するならまとめて最初にやってしまったほうが良い。 また、分散させるならなるべく均等に分けたほうが良い。 移動の回数 $cut$ と各人が食べる数の最大値 $len$ を決め、そうすることが可能なら更新していった。

これで small は通る。

実装

bool check(int cut, int len, vector<int> const & P){
    int rem = cut;
    rep(i,P.size()){
        int c = P[i]%len==0 ? P[i]/len-1 : P[i]/len;
        if(rem < c) return false;
        rem -= c;
    }
    return true;
}

int solve(int D, vector<int> P){
    int ans1 = 1<<29;
#ifdef TEST
    int ans2 = 1<<29;
#endif
    int S = accumulate(all(P),0);
    for(int cut = 0; cut <= S; cut++){
        int len_l = 0;
        int len_r = 1010;
        int len_m;
        while(len_l + 1 < len_r){
            len_m = (len_l + len_r) / 2;
            if(check(cut, len_m, P)){
                len_r = len_m;
            } else {
                len_l = len_m;
            }
        }
        ans1 = min(ans1, cut + len_r);

#ifdef TEST
        for(int len = 1; len <= 1010; len++){
            if(check(cut, len, P)){
                ans2 = min(ans2, cut+len);
            }
        }
#endif
    }
#ifdef TEST
    if(ans1 != ans2){
        dump(ans1, ans2);
        dump(P);
        abort();
    }
#endif
    return ans1;
}

signed main(){
    int T;
    cin >> T;
    rep(i,T){
        int D;
        cin >> D;
        vector<int> P(D);
        rep(j,D) cin >> P[j];
        int x = solve(D,P);
        cout << "Case #" << i+1 << ": " << x << endl;
    }
}