2014-08-23

POJ 3579: Median

POJ 蟻本

概要

N個の配列が与えられる．この中から2つの要素を取り出し，その差を計算し別の数列とする．
新しく作った配列の中央値を探索する．ただし，この問題において偶数長(m)の配列の中央値はm/2番目に小さい値と定義する．

解法

解を仮定して二分探索．

入力された配列はソートする．（絶対値をとっていて，順番には左右されないので）
そうすることで，個数のカウントが二分探索を使って行える．

制限時間がかなり厳しい．

int N;
int x[100010];
ll M;
bool C(int mid){
    ll cnt = 0;
    for(int i = 0; i < N; ++i){
        cnt += lower_bound(x + i + 1, x + N, x[i] + mid) - (x + (i + 1));
    }
    return cnt < M;
}
int main(){
    while(~scanf("%d", &N)){
        for(int i = 0; i < N; ++i) scanf("%d", x+i);
        M = (ll)N * (N - 1) / 2;
        if(M % 2) M = M / 2 + 1;
        else      M = M / 2;

        sort(x, x+N);
        int lb = 0, ub = 1000000010;
        while(ub - lb > 1){
            int mid = (lb + ub) / 2;
            if(C(mid)){
                lb = mid;
            }
            else{
                ub = mid;
            }
        }
        printf("%d\n", lb);
    }
    return 0;
}

2014-08-23

POJ 3111: K Best

POJ 蟻本

概要

n個の宝石があって，k個を残して売り払いたい．その時，残したk個の宝石の単位重さあたりの評価値を最大化したい．

解法

蟻本そのままで二分探索．謎WA連発の末，探索終えた後にもう一回答えを計算したほうがいいという結論に至る．
繰り返し回数が結構シビアかもしれない．

int n, k;
int v[100010], w[100010];

pair<double, int> y[100010];
bool C(double x){
    for(int i = 0; i < n; ++i) y[i] = make_pair(v[i] - w[i] * x, i + 1);
    sort(y, y + n);
    double sum = 0;
    for(int i = 0; i < k; ++i){
        sum += y[n-i-1].first;
    }
    return sum >= 0;
}
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i){
        scanf("%d%d", &v[i], &w[i]);
    }
    double lb = 0, ub = 1e8;
    for(int i = 0; i < 50; ++i){
        double mid = (lb + ub) / 2;
        if(C(mid)){
            lb = mid;
        }
        else{
            ub = mid;
        }
    }
    C(lb);
    for(int i = 0; i < k; ++i)
        printf("%d%c", y[n-i-1].second, i == k - 1 ? '\n': ' ');

    return 0;
}

2014-08-22

POJ 2976: Dropping Tests

概要

授業でn回のテストを受けた．i番目のテストではb[i]問中a[i]問正解した．
受けたテストのうちk回を取り除き， $100 \cdot (\sum_i a_i) / (\sum_i b_i)$ を最大化したい．

解法

二分探索．蟻本の練習問題まんま．

int n, k;
int a[1010], b[1010];
double v[1010];
bool C(double x){
    for(int i = 0; i < n; ++i) v[i] = 100LL * a[i] - x * b[i];
    sort(v, v + n);
    double sum = 0;
    for(int i = k; i < n; ++i){
        sum += v[i];
    }
    return sum >= 0;
}
main(){
    for(;;){
        scanf("%d%d", &n, &k);
        if( n == 0  && k == 0 ) return 0;
        for(int i = 0; i < n; ++i){
            scanf("%d", &a[i]);
        }
        for(int i = 0; i < n; ++i){
            scanf("%d", &b[i]);
        }
        double lb = 0, ub = 100;
        for(int i = 0; i < 100; ++i){
            double mid = (lb + ub) / 2;
            if(C(mid)){
                lb = mid;
            }
            else{
                ub = mid;
            }
        }
        printf("%d\n", (int)floor(lb + 0.5));
    }
}

2014-08-21

POJ 3045: Cow Acrobats

POJ 蟻本

概要

牛がN匹いる．i番目の牛は重さがw[i]で，強さがs[i]であることがわかっている．
この牛でタワーをつくりたい．タワーは牛が別の牛一頭にのることを繰り返してつくられる．
この時，牛iの危険度は (牛iの上に乗っている牛の重さの合計) - (牛iの強さ) で求められる．
N匹の牛を使って作るとき，牛の危険度の最大値を最小化したい．

解法

危険度を仮定して二分探索．

調べてみると二分探索使わなくても貪欲で解けるらしい．
貪欲力が低い．．．

const ll MAX_S = 1000000100;

int N, sum;
pair<int, int> cow[50010];

bool C(ll risk){
    priority_queue<int> Q;
    int i = 0;
    int tsum = sum;
    while(i < N){
        for(; i < N && tsum - cow[i].first <= risk; ++i){
            Q.push(cow[i].second); 
        }
        if(i < N && Q.empty()) return false;
        tsum -= Q.top();
        Q.pop();
    }
    return true;
}
int main(){
    scanf("%d", &N);
    sum = 0;
    for(int i = 0; i < N; ++i){
        int w, s;
        scanf("%d%d", &w, &s);
        cow[i] = make_pair(s + w, w);
        sum += w;
    }
    sort(cow, cow + N);
    reverse(cow, cow + N);
    ll lb = -MAX_S, ub = MAX_S;
    while(ub - lb > 1){
        ll mid = (ub + lb) / 2;
        if(C(mid)){
            ub = mid;
        }
        else{
            lb = mid;
        }
    }
    printf("%lld\n", ub);
    return 0;
}

2014-08-15

POJ 3104: Drying

POJ 蟻本

概要

洗濯物がn個あって，自然乾燥だと1分間に洗濯物の水が1だけ減る．暖房機を使えば，1分間にkだけの水を減らすことができるが，これは1分間に1つの洗濯物についてだけしか使えない．
暖房機を最適に使った時，すべての洗濯物を乾かすのに必要な最小の時間はいくつか．

解法

洗濯物を乾かすために必要な時間を仮定して二分探索．

「暖房機を使えば1分間にkだけ水を減らすことができる＝自然乾燥に比べて1分間あたりk-1多く水を減らすことができる」に注意して，二分探索の判定を行う．
洗濯物iの水分量をa_iとする．時間tだけかけて洗濯物の乾燥が終わるかどうかの判定は，水分量がtより多い洗濯物iに対しceil(a_i-t/(k-1))を求め，その総和がt以下であるかどうかで行うことができる．
計算式を見ればわかるが，k=1のコーナーケースには気を付けること．

解法の勘違いとコーナーケースの見落としでWA出した．

int n, k;
ll a[100010];
bool C(ll t){
    ll sum = 0;
    for(int i = 0; i < n; ++i){
        if(a[i] > t){
            sum += (a[i] - t + k - 1) / k;
        }
    }
    return sum <= t;
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);
    scanf("%d", &k);

    --k;
    ll l = 0, u = 0;
    for(int i = 0; i < n; ++i) u = max(u, a[i]);
    if(k == 0){
        printf("%lld\n", u);
        return 0;
    }
    while(u - l > 1){
        ll mid = (l + u) / 2;
        if(C(mid)){
            u = mid;
        }
        else{
            l = mid;
        }
    }
    printf("%lld\n", u);
    return 0;
}

2014-08-14

POJ 3273: Monthly Expense

POJ 蟻本

概要

要素数Nの数列{a_i}が与えられる．この数列をM個の連続した部分に分け，各部分の要素の合計の最大値を最小化したい．

解法

合計の最大値に対して二分探索を行う．
下限の初期化を間違っていたせいか，WA出した．

あと，最近気が付いたんだけど，二分探索の書き方が蟻本と違う．．．

int N, M;
int a[100010];
int C(int d){
    int cnt = 1, sum = 0;
    for(int i = 0; i < N; ++i){
        if(sum + a[i] > d){
            ++cnt;
            sum = 0;
        }
        sum += a[i];
    }
    return cnt;
}
int main(){
    scanf("%d%d", &N, &M);
    int l = 0, u = 1000000000;
    for(int i = 0; i < N; ++i){
        scanf("%d", &a[i]);
        l = max(l, a[i]);
    }
    int res = -1;
    while(l <= u){
        int mid = (l + u) / 2;
        if(C(mid) <= M){
            res = mid;
            u = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    printf("%d\n", res);
    return 0;
}

2014-08-13

POJ 3258 : River Hopscotch

POJ 蟻本

概要

スタートの石とゴールの石が川の中にあって，その間の距離がLだけ離れている．スタートとゴールの間には，N個の石が一列に並んでいて，i番目の石はスタートからd_iだけ離れた位置にある．
スタートとゴールの石をM個以下だけ取り除いて，石（スタートとゴールも含む）の間の距離の最小値を最大化したい．

解法

許容する距離Dを仮定して二分探索．

距離Dだけ離せるかの判定は，スタートからDより小さい距離にある石を削除．その結果，残る石の中でスタートからの距離が最小のものを選び，それについて同様の処理を施す．これを続けていって最終的に削除した石の個数がM以下か確認すればいい．

int L, N, M;
int d[50010];

bool C(int a){
    int s = 0, cnt = 0;
    for(int i = 0; i < N; ++i){
        if(d[i] - s < a)
            ++cnt;
        else
            s = d[i];
    }
    if(L - s < a) ++cnt;
    return cnt <= M;
}

int main(){
    scanf("%d%d%d", &L, &N, &M);
    for(int i = 0; i < N; ++i){
        scanf("%d", &d[i]);
    }
    sort(d, d + N);

    int b = min(L - d[N-1], d[0]);
    for(int i = 1; i < N; ++i){
        b = min(b, d[i] - d[i-1]);
    }

    int res = -1;
    int lb = 1, ub = L;
    while(lb <= ub){
        int mid = (lb + ub) / 2;
        if(C(mid)){
            res = mid;
            lb = mid + 1;
        }
        else{
            ub = mid - 1;
        }
    }
    printf("%d\n", res);
    return 0;
}