Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-05

QuickSums

| 11:11

問題文, SRM 197

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

合計値が指定された数にするために、最低必要な足し算の数。この問題、分類がDynamic Programmingになっているけど、最悪のケースが2^9なのでBrute Forceな方法で解いてしまった。

669.36/1100

class QuickSums {
public:
    int minSums(string numbers, int sum) {
        int result = INT_MAX;
        D = numbers.length();
        for (int i = 0; i < power2(D-1); i++) {
            bitset<9> plus(i);
            int thisSum = getSum(numbers, plus);
            if (thisSum == sum) 
                result = min(result, (int)plus.count());
        }
        if (result == INT_MAX) return -1;
        else return result;
    }
private:
    int D;
    int power2(int d) {
        int ret = 1;
        while (d-- > 0) ret *= 2;
        return ret;
    }
    int getSum(const string& nums, const bitset<9>& plus) {
        int sum = 0;
        int pre = 0;
        for (int i = 0; i < D-1; i++) {
            if (plus[i]) {
                sum += atoi(nums.substr(pre,i-pre+1).c_str());
                pre = i+1;
            }
        }
        sum += atoi(nums.substr(pre,D-pre).c_str());
        return sum;
    }
};