Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-21

SmartElevator

| 13:12

問題文, SRM 156

エレベータが、全ての乗客を運び終えるのにかかる最短の時間を求める。

231.89/550

class SmartElevator {
public:
    int timeWaiting(vector <int> arrivalTime, vector <int> startingFloor, vector <int> destinationFloor) {
        int numPeople = arrivalTime.size();
        string pat(numPeople*2, '0');
        for (int i = 0; i < numPeople; i++)
            pat[i*2] = pat[i*2+1] = i+'0';  
        int minTime = INT_MAX;
        do {
            int floor = 1;
            int time = 0;
            vector<bool> pickedup(numPeople, false);
            for (int i = 0; i < numPeople*2; i++) {
                int e = pat[i]-'0';
                if (pickedup[e]) {
                    int distance = abs(floor-destinationFloor[e]);
                    time += abs(distance);
                    floor = destinationFloor[e];
                } else {
                    int distance = abs(floor-startingFloor[e]);
                    time = max(arrivalTime[e], time+distance);
                    floor = startingFloor[e];
                    pickedup[e] = true;
                }
            }
            minTime = min(minTime, time);
        } while (next_permutation(pat.begin(), pat.end()));
        return minTime;
    }
};

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();
    }
};