Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-31

StampPads

| 13:51

問題文, SRM 158

欲しい色を全部そろえるには、何種類のスタンプパッドを買えば良いのか。Brute forceで解ける問題だったが、DPで解こうとした。2回タイムアウトで落とされたが、始めにmaskを作る方法に変えたら通った。

150.00/500 (2 failed)

class StampPads {
public:
    int bestCombo(vector <string> pads, vector <string> wishlist) {
        numPads = pads.size();
        pds = vector<vector<string> >(numPads, vector<string>(5));
        for (int i = 0; i < numPads; i++) {
            istringstream iss(pads[i]);
            for (int j = 0; iss >> pds[i][j]; j++) ;
        }
        bitset<32> got;
        numWishes = wishlist.size();
        wishL = wishlist;
        mask = vector<bitset<32> >(numPads);
        for (int i = 0; i < numPads; i++)
            for (int j = 0; j < numWishes; j++)
                mask[i][j] = find(pds[i].begin(),pds[i].end(),wishL[j]) != pds[i].end();
        return go(0, 0, got);
    }
    int numPads;
    vector<vector<string> > pds;
    vector<string> wishL;
    vector<bitset<32> > mask;
    int numWishes;
    int go(const int bought, const int idx, const bitset<32>& got) {
        if (got.count() >= numWishes) return bought;
        if (idx >= numPads) return -1;
        bitset<32> next(got | mask[idx]);
        if (next != got) {
            int retBuy = go(bought+1, idx+1, next);
            int retNot = go(bought, idx+1, got);
            if (retBuy == -1 && retNot == -1) return -1;
            else if (retBuy == -1) return retNot;
            else if (retNot == -1) return retBuy;
            else return min(retBuy, retNot);
        } else {
            return go(bought, idx+1, got);
        }
    }
};

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/caligue/20090831