Hatena::Grouptopcoder

yaottiの日記

2010-03-05

SRM 462 DIV2続き

| 14:09

medium

AgeEncoding.cpp

scoreと所用時間はメモしわすれた

例外的なケース実装に手間取った…1, "00101"とかそういうケース

2分探索実装したの初めてだ.


以下ソース

public:
    double getRadix(int age, string candlesLine) {
        // age > BASE > 0
        int len = candlesLine.size();
        double base;
        double l = 0, u = age;
        int i;
        for (i = 0; i < len; i++) {
            if (candlesLine[i] != '0') break;
        }
        if (i == len) {     // 全て0
            return (double)-1;
        }
        if (i + 1 == len) {     // 最後が1
            if (age == 1) return (double) - 2;
            return (double) - 1;
        }
        if (age == 1 && candlesLine[len - 1] == '1') {         // 2ビット以上立っている&最後が1
            return (double) - 1;
        }
        for(;;) {
            base = (l + u) / 2.0;
            double sumup = 0.0;
            double p = 1.0;
            LP(candlesLine) {
                if (candlesLine[len - i - 1] == '1') {
                    sumup += p;
                }
                p *= base;
            }
            if (abs(sumup - age) < EPSM) {
                break;
            }else if (sumup > age) {
                u = base;
            }else {
                l = base;
            }
        }
        return base;
    }
}

DedeDede 2012/08/30 06:02 Play informative for me, Mr. internet wrietr.

vdsiweebvvdsiweebv 2012/08/30 22:57 uRlawh <a href="http://dnvcxgpigien.com/">dnvcxgpigien</a>

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/yaotti/20100305