Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-07-25

WordParts

| 09:31

問題文

問題文が短く、問題の意味は理解できたが、解法が思いつかず、Editorialを見た。メモ化か。慣れない。

class WordParts {
public:
    int partCount(string original, string compound) {
        const int ori_len = original.length();
        len = compound.length();
        dict.clear();
        dict.insert(original);
        for (int i = 1; i < ori_len; i++) {
            dict.insert(original.substr(0,ori_len-i));
            dict.insert(original.substr(ori_len-i));
        }
        memo = vector<int>(len, -1);
        const int parts = minParts(compound, 0);
        if (parts >= INFTY) return -1;
        else return parts;
    }
private:
    int len;
    set<string> dict;
    vector<int> memo;
    const static int INFTY = INT_MAX/2;
    int minParts(const string& compound, const int pos) {
        if (pos == len) return 0;
        if (memo[pos] != -1) return memo[pos];
        memo[pos] = INFTY;
        for (set<string>::const_iterator w = dict.begin();
                    w != dict.end(); w++) {
            const int w_len = (*w).length();
            if (*w == compound.substr(pos, w_len))
                memo[pos] = min(memo[pos], 1+minParts(compound,pos+w_len));
        }
        return memo[pos];
    }
};

BombSweeper

| 05:47

問題文

ゲームの勝率を求める。

class BombSweeper {
public:
    double winPercentage(vector <string> board) {
        const int height = board.size();
        const int width = board[0].length();
        const static int DIR_KINDS = 8;
        const int d[DIR_KINDS][2] = {
            {-1,-1}, {-1, 0}, {-1, 1},
            { 0,-1},          { 0, 1},
            { 1,-1}, { 1, 0}, { 1, 1} };

        int wins=0, loses=0;
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (board[y][x] == 'B') {
                    loses++;
                    continue;
                }
                for (int i = 0; i < DIR_KINDS; i++) {
                    const int dy = y + d[i][0];
                    const int dx = x + d[i][1];
                    if (0<=dy&&dy<height && 0<=dx&&dx<width) {
                        if (board[dy][dx] == 'B') break;
                    }
                    if (i == DIR_KINDS-1) wins++;
                }
            }
        }
        const double percentage = 100.0l * wins / (wins+loses); 
        return percentage;
    }
};

DiskSpace

| 05:47

問題文

使うハードディスクの数を最小限にする。

class DiskSpace {
public:
    int minDrives(vector <int> used, vector <int> total) {
        int totalUsed = accumulate(used.begin(),used.end(),0);
        sort(total.rbegin(), total.rend());
        for (int i = 0; i < total.size(); i++) {
            if (totalUsed <= total[i]) return i+1;
            else totalUsed -= total[i];
        }
        return total.size();
    }
};