Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-07-24

BenfordsLaw

| 05:41

問題文

Benford's Law により計算される、期待される取引金額の先頭数字の出現数より、実際の出現数が基準よりずれているかどうかを調べる。

class BenfordsLaw {
public:
    int questionableDigit(vector <int> transactions, int threshold) {
        const int numTrans = transactions.size();
        double expected[10];
        for (int d = 1; d <= 9; d++) {
            expected[d] = log10(1.0l+1.0l/d) * numTrans;
        }
        vector<int> count(10, 0);
        for (int i = 0; i < numTrans; i++) {
            int first = transactions[i];
            while (first >= 10) first /= 10;
            count[first]++;
        }
        for (int d = 1; d <= 9; d++) {
            if (count[d] > threshold*expected[d] 
                  || count[d] < expected[d]/threshold)
                return d;
        }
        return -1;
    }
};