Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-12-23

CutSticks (SRM456 DIV1 Medium)

| 23:40 | CutSticks (SRM456 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CutSticks (SRM456 DIV1 Medium) - TopCoder煮ブログ

n個の棒をC回切って、K番目に長い棒の最大長を求める問題。上位の人のソースを読んで意図を解読した。

最大C回切ることが許されているときに、長さが m 以上となる棒がK個以上あるかを求めることができる。

この長さ m を 0 と無限長の中点から始めて、m 以上か m 以下かで2分探索していく。

上位の人のソースを解読して、自分なりに書き換えてコメントいれた。ループ回数に最大回数が入ってるのは二分探索の罠を回避するため。

高レート部屋でこの定番が使えなかったのが痛いけど、見るべきは「二分探索の終了条件」です

例えば、差が1e-9以下になったらーとかいってたら、出来るだけでかいのをぶち込みますっ

仮数部が確か52bitしかないはずだから、まぁ16桁くらいまでなのかな、だとすると、答えが1e10くらいのものをぶち込まれたときに、差がそれ以下にならずに無限ループに入ったりしちゃうわけです

ただこれは入るときと入らないときがあるから落とせない、ってのが難しいところですorz

chokudaiのブログ - chokudaiのブログ

奥が深い。。。

以下、ソース。

class CutSticks {
public:
    // 最大C回切ることが許されているときに、
    // 長さが m 以上となる棒の数を返す
    int Count(vector<int> sticks, double m, int C){
        // 戻り値
        int ret = 0;

        for(int i = 0; i < sticks.size(); i++){
            // i 本目の棒の長さを s とする
            int s = sticks[i];

            // i 本目の棒が m より小さいときは数には含まれない
            if (s < m) continue;

            // 最大何回切れるかを求める
            // s が 2 * m 程度のときは、1回切ることができる
            int count = int(s / m) - 1;

            // count の上限を残り切れる回数 C にする
            count = min(count, C);

            // 戻り値を(切れる回数+1)だけ増やす
            ret += count + 1;

            // 残り切れる回数 C を更新する
            C -= count;
        }

        return ret;
    }

    double maxKth(vector <int> sticks, int C, int K) {
        // 左端、右端を設定する
        double l = 0;
        double r = 1e9;

        // 回数制限用のカウンタ
        int count = 0;

        // 差が小さくなるか500回ループしたら終わる
        while(fabs(l - r) > 1e-10 && count < 500){
            // 中点を取得する
            double m = (l + r) / 2.0;

            // m 以上となる棒が K 個以上のときは
            // 求めるべき値は m より大きい。
            if(Count(sticks, m, C) >= K){
                l = m;
            } else {
                r = m;
            }

            count++;
        }

        return r;
    }
};