Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-15

RPG

| 16:56

問題文

サイコロの出目の合計値として考えられる、最低値、最高値、平均値を計算する。

236.38/250

class RPG {
    public:
        vector <int> dieRolls(vector <string> dice) {
            vector <int> result(3, 0);
            double average = 0.0;
            for (int i = 0; i < dice.size(); i++) {
                int n, x;
                sscanf(dice[i].c_str(), "%dd%d", &n, &x);
                result[0] += n;
                result[1] += n * x;
                average += n*(x+1)/2.0l;
            }
            result[2] = static_cast<int>(average);
            return result;
        }
};

TrevonTrevon2011/07/22 14:31What a joy to find such clear thikinng. Thanks for posting!

jknzrlrnojknzrlrno2011/07/22 23:00AjjYSE <a href="http://ixlymfbzzugw.com/">ixlymfbzzugw</a>

yvzbbdyvzbbd2011/07/23 22:15ye8QTD , [url=http://uxgtugxylomn.com/]uxgtugxylomn[/url], [link=http://kqcpcalkwsod.com/]kqcpcalkwsod[/link], http://qqpqjszskcfr.com/

zjjbnlaeddzzjjbnlaeddz2011/07/24 22:34EkvlNg <a href="http://ziovfuvshgpt.com/">ziovfuvshgpt</a>

kredwoskredwos2011/07/26 01:32v3mrNH , [url=http://zmgqozacpuiq.com/]zmgqozacpuiq[/url], [link=http://vvwzqzdemmen.com/]vvwzqzdemmen[/link], http://hmhrbmsipkkf.com/

CamiloCamilo2012/11/16 17:32It's wondeurfl to have you on our side, haha!

amnquhsamnquhs2012/11/16 22:35OOQfVh <a href="http://wykjstupxxmy.com/">wykjstupxxmy</a>

etogorusetogorus2019/05/05 21:25http://mewkid.net/buy-amoxicillin/ - Amoxicillin 500mg Capsules <a href="http://mewkid.net/buy-amoxicillin/">Online Amoxicillin</a> wgo.cyyp.topcoder.g.hatena.ne.jp.sog.xx http://mewkid.net/buy-amoxicillin/

2009-08-11

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

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/

2009-08-08

Animation

| 19:40

問題文

粒子の動き。強引に解きすぎて、バグが増え、時間がかかった。

150.00/500 - 00:57:22

class Animation {
    public:
        vector <string> animate(int speed, string init) {
            const int len = init.length();
            const static char RIGHT = '1';
            const static char LEFT = '2';
            string pre(init);
            for (int i = 0; i < len; i++) {
                if (pre[i] == 'R') pre[i] = RIGHT;
                else if (pre[i] == 'L') pre[i] = LEFT;
                else pre[i] = 0;
            }
            vector <string> result;
            while (true) {
                string s(toX(pre));
                result.push_back(s);
                if (find(s.begin(),s.end(),'X') == s.end())
                    break;
                s = string(len, 0);
                for (int i = 0; i < len; i++) {
                    int d;
                    switch (pre[i]) {
                    case RIGHT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        break;
                    case LEFT:
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    case RIGHT+LEFT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    }
                }
                pre = s;
            }
            return result;
        }
    private:
        string toX(const string& s) {
            string ret(s.length(), '.');
            for (int i = 0; i < s.length(); i++)
                if (s[i] != 0)
                    ret[i] = 'X';
            return ret;
        }
};

ewnfzgewnfzg2011/02/28 00:358HHlV6 <a href="http://nfypkepkeych.com/">nfypkepkeych</a>, [url=http://azgnisbcmhab.com/]azgnisbcmhab[/url], [link=http://jedmlehhrowo.com/]jedmlehhrowo[/link], http://pqvizwthqdkq.com/

2009-08-06

Justifier

| 19:16

問題文

一番長い文字列に文字列の長さを合わせる。

class Justifier {
    public:
        vector <string> justify (vector <string> textIn) {
            int longest = INT_MIN;
            for (int i = 0; i < textIn.size(); i++)
                longest = max(longest, (int)textIn[i].length());
            vector <string> result(textIn.size());
            for (int i = 0; i < textIn.size(); i++)
                result[i] = string(longest-textIn[i].length(),' ') + textIn[i];
            return result;
        }
};

NathalieadsonNathalieadson2012/07/10 00:48Unparaellled accuracy, unequivocal clarity, and undeniable importance!

qumvofqumvof2012/07/10 15:55k9l8Kn <a href="http://ffbnrpylucxq.com/">ffbnrpylucxq</a>

kxvfpogrvtkxvfpogrvt2012/07/10 21:52DUrnSr , [url=http://odqnuvepnfcs.com/]odqnuvepnfcs[/url], [link=http://gllexsagvhok.com/]gllexsagvhok[/link], http://ctntvviqpnwt.com/

ahphkwegfjvahphkwegfjv2012/07/12 12:12jHPHB5 <a href="http://wujnvnxoozdt.com/">wujnvnxoozdt</a>

2009-08-03

StringTrain

| 18:38

問題文

電車の連結。PrefixとSuffixの問題。

class StringTrain {
    public:
        string buildTrain(vector <string> cars) {
            string train = cars[0];
            for (int i = 1; i < cars.size(); i++) {
                const int len_train = train.length();
                const int len_car = cars[i].length();
                for (int j = len_car-1; j >= 1; j--) {
                    if (len_train <= j) continue;
                    if (train.substr(len_train-j,j) == cars[i].substr(0,j)) {
                        train = train + cars[i].substr(j);
                        break;
                    } 
                }
            }
            set<char> appeared;
            ostringstream oss;
            for (int i = train.length()-1; i >= 0; i--) {
                if (appeared.find(train[i]) == appeared.end()) {
                    oss << train[i];
                    appeared.insert(train[i]);
                }
            }
            string strAfterRemv(oss.str());
            reverse(strAfterRemv.begin(), strAfterRemv.end());
            ostringstream resoss;
            resoss << train.length() << " " << strAfterRemv;
            return resoss.str();
        }
};

CardCount

| 18:38

問題文

カード配り。

class CardCount {
    public:
        vector <string> dealHands(int numPlayers, string deck) {
            vector <string> result(numPlayers);
            for (int i = 0; i < deck.size()/numPlayers; i++) {
                for (int j = 0; j < numPlayers; j++) {
                    result[j] += string(1, deck[i*numPlayers+j]);
                }
            }
            return result;
        }
};

DennysDennys2012/07/10 08:54There's a trefriic amount of knowledge in this article!

ptkxkwfiufxptkxkwfiufx2012/07/11 08:32rW3Q5y <a href="http://lvoddmvsamev.com/">lvoddmvsamev</a>

ssurmbuvpsmssurmbuvpsm2012/07/11 21:20GnFEME , [url=http://jcvsaeuskkgr.com/]jcvsaeuskkgr[/url], [link=http://iseogblgtggc.com/]iseogblgtggc[/link], http://nsaattulsfhk.com/

xtmpsysmfgnxtmpsysmfgn2012/07/12 13:058VKorp <a href="http://qspzckisagzz.com/">qspzckisagzz</a>

ueblizedjueblizedj2012/07/12 18:376GmZzo , [url=http://rtmucgtfbosq.com/]rtmucgtfbosq[/url], [link=http://dzmpwnhervlx.com/]dzmpwnhervlx[/link], http://trmherritlub.com/

2009-08-01

Substitute

| 18:34

コードがはみ出るので、ブログのデザインを横幅が広いデザインに変更した。

問題文

1文字ごとの復号。

class Substitute {
public:
    int getValue(string key, string code) {
        map<char,int> decoder;
        for (int i = 0; i < key.length(); i++) {
            if (i == key.length()-1) decoder[key[i]] = 0;
            else decoder[key[i]] = i+1;
        }
        int value = 0;
        for (int i = 0; i < code.length(); i++) {
            if (decoder.find(code[i]) != decoder.end()) {
                value *= 10;
                value += decoder[code[i]];
            }
        }
        return value;
    }
};

2009-07-28

StreetParking

| 18:25

問題文

道に駐車できるかどうか。

class StreetParking {
public:
    int freeParks(string street) {
        const int len = street.length();
        int total = 0;
        for (int i = 0; i < len; i++) {
            if (street[i] != '-') continue;
            if (i+2 < len && street[i+2]=='B') continue;
            if (i+1 < len && 
                (street[i+1]=='B'||street[i+1]=='S')) continue;
            if (i-1 >= 0 && street[i-1]=='S') continue;
            total++;
        }
        return total;
    }
};

2009-07-26

Gems

| 19:52

ボード中の2つの隣接する宝石を入れ替えた時に、3つ以上宝石が並ぶかどうか。自力で解けると思って実装したが、重複して数えてしまってうまくいかず、結局Editorialを見た。

class Gems {
public:
    int numMoves(vector <string> board) {
        int moves = 0;
        const static int d[DIR_KINDS][2] = {
            { 0, 1}, { 1, 0}, { 0,-1}, {-1, 0} };
        const int h=board.size(), w=board[0].length();
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                const char gem = board[y][x];
                for (int i = 0; i < DIR_KINDS/2; i++) {
                    const int dy = y + d[i][0];
                    const int dx = x + d[i][1];
                    if (!isInRage(dy,dx,h,w)) continue;
                    if (gem == board[dy][dx]) continue;
                    if (isAligned(gem,dy,dx,i,board,h,w) ||
                      isAligned(board[dy][dx],y,x,i+DIR_KINDS/2,board,h,w)) {
                        moves++;
                    }
                }
            }
        }
        return moves;
    }
private:
    const static int DIR_KINDS = 4;
    bool isInRage(const int y, const int x, const int h, const int w) {
        return 0<=y&&y<h && 0<=x&&x<w;
    }
    bool isAligned(const char gem, const int dy, const int dx, const int dir,
              const vector<string>& board, const int h, const int w) {
        const static int CHECK_KINDS = 4;
        const static int check[DIR_KINDS][CHECK_KINDS][2][2] = {
            { {{-1, 0},{ 1, 0}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}} },
            { {{-1, 0},{ 1, 0}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}} } };
        for (int j = 0; j < CHECK_KINDS; j++) {
            for (int k = 0; k < 2; k++) {
                const int cy = dy + check[dir][j][k][0];
                const int cx = dx + check[dir][j][k][1];
                if (!isInRage(cy,cx,h,w)) break;
                if (gem != board[cy][cx]) break;
                if (k == 2-1) return true;
            }
        }
        return false;
    }
};

TireRotation

| 09:14

問題文

タイヤを長持ちさせるために、タイヤをローテートするときの法則にcurrentが従っているかどうか。問題文の書き出しに難しそうな印象を受けたが、問題はタイヤが4つの場合だけなので簡単だった。

class TireRotation {
public:
    int getCycle(string initial, string current) {
        const static int CHAR_LONG = 4;
        const static int rot[CHAR_LONG] = { 2, 3, 1, 0 };
        vector<string> pattern(CHAR_LONG, initial);
        for (int cycle = 1; cycle < CHAR_LONG; cycle++) {
            if (current == pattern[cycle-1]) return cycle;
            for (int i = 0; i < CHAR_LONG; i++) {
                pattern[cycle][rot[i]] = pattern[cycle-1][i];
            }
        }
        if (current == pattern[CHAR_LONG-1]) return CHAR_LONG;
        else return -1;
    }
};

2009-07-23

SuperRot

| 05:33

問題文

暗号化された文字列を復号。

class SuperRot {
public:
    string decoder(string message) {
        setToTable('A', 'M', 'N');
        setToTable('N', 'Z', 'A');
        setToTable('a', 'm', 'n');
        setToTable('n', 'z', 'a');
        setToTable('0', '4', '5');
        setToTable('5', '9', '0');
        for (int i = 0; i < message.length(); i++) {
            if (isalnum(message[i]))
                message[i] = table[message[i]];
        }
        return message;
    }
private:
    char table[256];
    void setToTable(const char l, const char h, const char s) {
        for (int i = l; i <= h; i++) table[i] = s+(i-l);
    }
};

2009-05-23

PrefixCode

| 19:40

問題文

232.80->249.10/250

words に含まれる各文字列が他の文字列の prefix code (前方一致している)かどうかを調べる。

class PrefixCode {
public:
    string isOne(vector <string> words) {
        for (int i = 0; i < words.size(); i++) {
            int len = words[i].length();
            for (int j = 0; j < words.size(); j++) {
                if (i == j || len > words[j].length()) continue;
                if (words[i] == words[j].substr(0,len)) {
                    ostringstream os;
                    os << "No, " << i;
                    return os.str();
                }
            }
        }
        return "Yes";
    }
};