Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-30

MineField

| 11:43

問題文, SRM 169

マインスイーパ。

225.69/250

class MineField {
public:
    vector <string> getMineField(string mineLocations) {
        const static int SIZE = 9;
        vector <string> result(SIZE,string(SIZE,'0'));
        istringstream iss(mineLocations);
        char pad;
        int y, x;
        while (iss >> pad >> y >> pad >> x >> pad)
            result[y][x] = 'M';
        const static int d[8][2] = {
            {-1,-1}, {-1, 0}, {-1, 1},
            { 0,-1},          { 0, 1},
            { 1,-1}, { 1, 0}, { 1, 1} };
        for (y = 0; y < SIZE; y++)
            for (x = 0; x < SIZE; x++) {
                if (result[y][x] == 'M') continue;
                int counter = 0;
                for (int i = 0; i < 8; i++) {
                    int dy = y + d[i][0];
                    int dx = x + d[i][1];
                    if (0<=dy&&dy<SIZE && 0<=dx&&dx<SIZE 
                            && result[dy][dx] == 'M')
                        counter++;
                }
                result[y][x] += counter;
            }
        return result;
    }
};

2009-08-11

FairWorkload

| 13:17

問題文

仕事をなるべく均等になるように割り振る。良問。Level-2の問題より解きやすかった。

532.87/1000 - 00:32:37

class FairWorkload {
    public:
        int getMostWork(vector <int> folders, int workers) {
            amounts = vector<int>(workers, 0);
            maxOptimalAmount = INT_MAX;
            go(folders, 0, workers, 0);
            return maxOptimalAmount;
        }
    private:
        int maxOptimalAmount;
        vector<int> amounts;
        void go(const vector<int>& folders, const int f_id, 
                const int workers, const int w_id) {
            if (f_id == folders.size()) {
                for (int i = 0; i < workers; i++)
                    if (amounts[i] == 0)
                        return;
                maxOptimalAmount = min(maxOptimalAmount, 
                        *max_element(amounts.begin(),amounts.end()));
                return;
            }
            if (maxOptimalAmount <= amounts[w_id]) return;
            if (w_id == workers) return;
            amounts[w_id] += folders[f_id];
            go(folders, f_id+1, workers, w_id);
            amounts[w_id] -= folders[f_id];
            if (w_id+1 == workers) return;
            amounts[w_id+1] += folders[f_id];
            go(folders, f_id+1, workers, w_id+1);
            amounts[w_id+1] -= folders[f_id];
        }
};

Twain

| 19:36

問題文

問題文の通りに文字列を変換する。やるだけの問題だが、書く必要があるコード量が多い。一回目にサブミットしたプログラムはバグがあり、システムテストは通らなかった。

184.88/500 - 00:42:14 (failed)

class Twain {
    public:
        string getNewSpelling(int year, string phrase) {
            vector<char> exceptions;
            exceptions.push_back('a'); exceptions.push_back('e');
            exceptions.push_back('i'); exceptions.push_back('o');
            exceptions.push_back('u');
            for (int y = 1; y <= year; y++) {
                string tmpStr;
                int len;
                switch (y) {
                    case 1:
                        if (phrase[0] == 'x') phrase[0] = 'z';
                        phrase = replaceCharsOfWord(phrase, " x", " z");
                        phrase = replaceCharsOfWord(phrase, "x", "ks");
                        break;
                    case 2:
                        phrase = replaceCharsOfWord(phrase, "y", "i");
                        break;
                    case 3:
                        phrase = replaceCharsOfWord(phrase, "ce", "se");
                        phrase = replaceCharsOfWord(phrase, "ci", "si");
                        break;
                    case 4:
                        do {
                            tmpStr = phrase;
                            phrase = replaceCharsOfWord(phrase, "ck", "k");
                        } while (tmpStr != phrase);
                        break;
                    case 5:
                        if (phrase.substr(0,3) == "sch") 
                            phrase = "sk" + phrase.substr(3);
                        phrase = replaceCharsOfWord(phrase, " sch", " sk");
                        phrase = replaceCharsOfWord(phrase, "chr", "kr");
                        for (char c = 'a'; c <= 'z'; c++) {
                            if (c == 'h') continue;
                            string pattern("c"+string(1,c));
                            string placement("k"+string(1,c));
                            phrase = replaceCharsOfWord(phrase, pattern, placement);
                        }
                        phrase = replaceCharsOfWord(phrase, "c ", "k ");
                        len = phrase.length();
                        if (phrase[len-1] == 'c') phrase[len-1] = 'k';
                        break;
                    case 6:
                        if (phrase.substr(0,2) == "kn")
                            phrase = "n" + phrase.substr(2);
                        phrase = replaceCharsOfWord(phrase, " kn", " n");
                        break;
                    case 7:
                        do {
                            tmpStr = phrase;
                            for (char c = 'a'; c <= 'z'; c++) {
                                if (find(exceptions.begin(),exceptions.end(),c) == exceptions.end()) {
                                    string pattern(2,c);
                                    string placement(1,c);
                                    phrase = replaceCharsOfWord(phrase, pattern, placement);
                                }
                            }
                        } while (tmpStr != phrase);
                        break;
                }
            }
            return phrase;
        }
    private:
        string replaceCharsOfWord(const string& phrase, 
                const string pattern, const string placement) {
            string result;
            string::size_type pos = 0;
            string::size_type pre_pos = 0;
            string::size_type pat_len = pattern.length();
            while ((pos = phrase.find(pattern,pos)) != string::npos) {
                result.append(phrase, pre_pos, pos-pre_pos);
                result.append(placement);
                pos += pat_len;
                pre_pos = pos;
            }
            result.append(phrase, pre_pos, phrase.length()-pre_pos);
            return result;
        }
};

Swimmers

| 19:33

問題文

川を往復するのに必要な時間を求める。

224.03/250 - 00:10:06

class Swimmers {
    public:
        vector <int> getSwimTimes(vector <int> distances, vector <int> speeds, int current) {
            const int numSwimmers = distances.size();
            vector <int> result(numSwimmers);
            for (int i = 0; i < numSwimmers; i++) {
                if (distances[i] == 0) {
                    result[i] = 0;
                } else if (current >= speeds[i]) {
                    result[i] = -1;
                } else {
                    result[i] = static_cast<int>(
                            static_cast<double>(distances[i]) / (speeds[i]-current)
                            + static_cast<double>(distances[i]) / (speeds[i]+current)); 
                }
            }
            return result;
        }
};

OliviaOlivia2011/07/09 22:49Ppl like you get all the birans. I just get to say thanks for he answer.

cganpmvkaacganpmvkaa2011/07/10 00:21ozUmeq <a href="http://pjfcqeeeqmnr.com/">pjfcqeeeqmnr</a>

gkbfwfvcbgkbfwfvcb2011/07/10 21:09Bo1aDa , [url=http://xrkdnugczyzj.com/]xrkdnugczyzj[/url], [link=http://sbngsfqxhlpy.com/]sbngsfqxhlpy[/link], http://safjlfwoassi.com/

uxpnpunauxpnpuna2011/07/11 20:32crHIwv <a href="http://fodsgqzsvyim.com/">fodsgqzsvyim</a>

mhhaaumhhaau2011/07/12 21:58da56vU , [url=http://tqvvgrxdnlwt.com/]tqvvgrxdnlwt[/url], [link=http://ofcuaexemicz.com/]ofcuaexemicz[/link], http://shzifphpejdh.com/