Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-24

ClockWalk

| 17:39

問題文, SRM 175

時計を動かし終わった後は、何時か。テストをしないで出したら、tailの場合の計算で、馬鹿なバグがあり、落とされた。

214.27/250

class ClockWalk {
public:
    int finalPosition(string flips) {
        int hour = 0;
        for (int i = 0; i < flips.size(); i++) {
            if (flips[i] == 'h') hour = (hour + i+1) % 12;
            else  hour = (hour - (i+1) + 120) % 12;
        }
        if (hour == 0) hour = 12;
        return hour;
    }
};

2009-08-23

CheatCode

| 11:08

問題文, SRM 154

どの裏技コードを入力したかを判定。1回目に出したときは、しょうもないバグがあり、落とされた。

152.30/350

class CheatCode {
public:
    vector <int> matches(string keyPresses, vector <string> codes) {
        vector <int> result;
        const int keyLen = keyPresses.length();
        for (int i = 0; i < codes.size(); i++) {
            const int codeLen = codes[i].length();
            for (int j = 0; j < keyLen; j++) {
                if (codes[i][0] != keyPresses[j]) continue;
                int idx = 1;
                for (int k = j+1; idx < codeLen && k < keyLen; k++) {
                    if (codes[i][idx] == keyPresses[k])
                        idx++;
                    else if (keyPresses[k] != codes[i][idx-1])
                        break;
                }
                if (idx == codeLen) {
                    result.push_back(i);
                    break;
                }
            }
        }
        return result;
    }
};

2009-08-19

| 14:30

問題文, http://www.topcoder.com/stat?c=round_overview&rd=4550:titel=SRM 149]

Dictionaryに含まれる単語だけで、messageを作れるかどうか。DPで解ける問題だが、見落としが発生しやすい問題。4回もシステムテストで落とされた。

150.0/500

class MessageMess {
    public:
        string restore(vector <string> dictionary, string message) {
            const int len = message.size();
            vector<string> memo(len, "");
            vector<bool> isAmbiguous(len, false);
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < dictionary.size(); j++) {
                    const int wlen = dictionary[j].length();
                    if (i+1 < wlen) continue;
                    if (i-wlen >= 0 && memo[i-wlen] == "") continue;
                    if (message.substr(i-wlen+1,wlen) != dictionary[j]) continue;
                    if (memo[i] != "") isAmbiguous[i] = true;
                    if (i-wlen >= 0) {
                        if (toNospace(memo[i-wlen]) != message.substr(0,i-wlen+1)) continue;
                        if (isAmbiguous[i-wlen]) isAmbiguous[i] = true;
                        memo[i] = memo[i-wlen] + " " + dictionary[j];
                    } else {
                        memo[i] = dictionary[j];
                    }
                }
            }
            if (memo[len-1] == "") return "IMPOSSIBLE!";
            else if (isAmbiguous[len-1]) return "AMBIGUOUS!";
            else return memo[len-1];
        }
    private:
        string toNospace(const string& s) {
            string nospace;
            const int slen = s.length();
            int idx=0, pre=idx;
            while ((idx = s.find(" ", pre)) != string::npos) {
                nospace += s.substr(pre, idx-pre);
                pre = idx+1;
            }
            nospace += s.substr(pre, slen-pre);
            return nospace;
        }
};

RenaRena2011/07/22 11:40Articles like this really grease the shftas of knowledge.

mtosqkksxfnmtosqkksxfn2011/07/22 18:19nGge95 <a href="http://htbsbsjhateo.com/">htbsbsjhateo</a>

vouvotvouvot2011/07/24 22:10AbhEFB <a href="http://udtjnaqmvoon.com/">udtjnaqmvoon</a>

lraetvllraetvl2011/07/25 02:03Ueilew , [url=http://ofkchvqjbqph.com/]ofkchvqjbqph[/url], [link=http://mhzhqovckhxx.com/]mhzhqovckhxx[/link], http://kgxfqnawhoqk.com/

2009-08-17

Dragons

| 13:52

問題文, SRM 147

餌の奪い合いをした後に、ボスドラゴンはどれぐらいの餌をもっているのかを求める。1回目に出したときは、結果が0になる場合の処理を実装していなかったため、システムテストで落とされた。

150.0/500

typedef long long int64;

class Dragons {
    public:
        string snaug(vector <int> initialFood, int rounds) {
            const static int NUM_SIDES = 6;
            const static bool d[NUM_SIDES][NUM_SIDES] = {
                { false, false,  true,  true,  true,  true },
                { false, false,  true,  true,  true,  true },
                {  true,  true, false, false,  true,  true },
                {  true,  true, false, false,  true,  true },
                {  true,  true,  true,  true, false, false },
                {  true,  true,  true,  true, false, false } };
            vector<pair<int64,int64> > food(NUM_SIDES);
            for (int i = 0; i < NUM_SIDES; i++)
                food[i] = make_pair(initialFood[i], 1);

            while (rounds-- > 0) {
                vector<pair<int64,int64> > oneFourth(food);
                for (int i = 0; i < NUM_SIDES; i++) {
                    oneFourth[i].second *= 4;
                    oneFourth[i] = reduction(oneFourth[i]);
                }
                food = vector<pair<int64,int64> >(NUM_SIDES, make_pair(0,1));
                for (int i = 0; i < NUM_SIDES; i++) {
                    for (int j = 0; j < NUM_SIDES; j++) {
                        if (d[i][j]) 
                            food[i] = addFrac(food[i], oneFourth[j]);
                    }
                }
            }

            ostringstream res;
            const static int BOSS = 2;
            if (food[BOSS].first == 0) {
                res << 0;
            } else if (food[BOSS].second == 1) {
                res << food[BOSS].first;
            } else {
                res << food[BOSS].first << "/" << food[BOSS].second;
            }
            return res.str();
        }
    private:
        int64 gcd(int64 c, int64 d) {
            if (c==0 || d==0) return 1;
            int64 v = c;
            while (v > 0) {
                v = c % d;
                c = d;
                d = v;
            }
            return c;
        }
        int64 lcm(int64 c, int64 d) {
            return c / gcd(c,d) * d;
        }
        pair<int64,int64> reduction(const pair<int64,int64> a) {
            int64 g = gcd(a.first, a.second);
            return make_pair(a.first/g, a.second/g);
        }
        pair<int64,int64> addFrac(const pair<int64,int64> a, const pair<int64,int64> b) {
            pair<int64,int64> ret;
            int64 l = lcm(a.second, b.second);
            ret.second = l;
            ret.first = a.first*(l/a.second) + b.first*(l/b.second);
            return reduction(ret);
        }
};

2009-08-15

Bonuses

| 10:50

昨日はSolved Problemsの表を作るためのスクリプトを書いていたので、問題を解く時間がなかった。

問題文

従業員のボーナスの割り当て率を計算する。

134.03/250

bool compBonus(const pair<int,int>& a, const pair<int,int>& b)
{
    if (a.first > b.first) {
        return true;
    } else if (a.first < b.first) {
        return false;
    } else {
        return a.first < b.first;
    }
}

class Bonuses {
public:
    vector <int> getDivision(vector <int> points) {
        const int numEmployees = points.size();
        int total = accumulate(points.begin(), points.end(), 0);
        vector <int> percent(numEmployees);
        for (int i = 0; i < numEmployees; i++) 
            percent[i] = static_cast<int>(100.0l*points[i]/total);
        int percentSum = accumulate(percent.begin(), percent.end(), 0);
        vector<pair<int,int> > sorted(numEmployees);
        for (int i = 0; i < numEmployees; i++) 
            sorted[i] = make_pair(points[i], i);
        sort(sorted.begin(), sorted.end(), compBonus);
        int idx = 0;
        while (percentSum < 100) {
            percent[sorted[idx].second]++;
            idx = (idx+1) % numEmployees;
            percentSum++;
        }
        return percent;
    }
};

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-07-26

BaseMystery

| 09:14

問題文

n進数を採用したとき、等式を満たすかどうか。見落としが多く、2回システムテストで落とされ、3回目で通った。

class BaseMystery {
public:
    vector <int> getBase(string equation) {
        vector <int> result;
        vector<string> nums(3); 
        nums[0] = string(equation.begin(), 
                find(equation.begin(),equation.end(),'+'));
        nums[1] = string(equation.begin()+nums[0].length()+1, 
            find(equation.begin()+nums[0].length()+1,equation.end(),'='));
        nums[2] = string(equation.begin()+nums[0].length()+nums[1].length()+2,
                equation.end());
        int maxDigit = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < nums[i].length(); j++) {
                maxDigit = max(maxDigit, getIntDigit(nums[i][j]));
            }
        }
        for (int p = max(2,maxDigit+1); p <= 20; p++) {
            if (toBase10(nums[0],p)+toBase10(nums[1],p)
                                    == toBase10(nums[2],p))
                result.push_back(p);
        }
        return result;
    }
private:
    int getIntDigit(const char c) {
        if (isdigit(c)) return c - '0';
        else return 10 + c - 'A';
    }
    int toBase10(const string& s, const int p) {
        int d = 0;
        for (int i = 0; i < s.length(); i++) {
            d *= p;
            d += getIntDigit(s[i]);
        }
        return d;
    }
};

2009-05-05

FormatAmt

| 18:41

問題文

75.0->246.97->248.61 / 250

DIV2 の easy にしては難しい問題。右側から作って、最後にリバースする。

class FormatAmt {
public:
    string amount(int dollars, int cents) {
        ostringstream os, os2;
        os << cents%10 << cents/10 << ".";
        os2 << dollars;
        string dStr(os2.str());
        for (int i = dStr.length(); i >= 1; i -= 3) {
            if (i <= 3) {
                string t(dStr.substr(0, i));
                reverse(t.begin(), t.end());
                os << t;
            } else {
                string t(dStr.substr(i-3, 3));
                reverse(t.begin(), t.end());
                os << t << ",";
            }
        }
        os << "$";
        string result(os.str());
        reverse(result.begin(), result.end());
        return result;
    }
};

EthanaelEthanael2011/07/22 23:14Ppl like you get all the brains. I just get to say thanks for he asewnr.

nwuzwsnwuzws2011/07/23 17:24hyvJcw <a href="http://snkjtvdtsudq.com/">snkjtvdtsudq</a>

tumzkdcbtumzkdcb2011/07/23 22:087LifN6 , [url=http://qcpqtmgyqoyx.com/]qcpqtmgyqoyx[/url], [link=http://aubgoopyvcjc.com/]aubgoopyvcjc[/link], http://wsyiiftrtiox.com/

jijaysgrhiqjijaysgrhiq2011/07/25 21:508QsglD <a href="http://gpbtdukulkdq.com/">gpbtdukulkdq</a>