Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-25

QuiningTopCoder

| 14:09

問題文, SRM 152

自分自身のソースを出力するプログラムかどうかを確認。

150.0/500 (1 failed)

class QuiningTopCoder {
public:
    string testCode(string source) {
        string output;
        const static int TIME_LIMIT = 80000;
        stack<int> stk;
        for (int i = 0; i < TIME_LIMIT; i++) stk.push(0);
        int IP=0, D=1, N=source.size();
        int cycle = 0;
        while (source[IP] != '@' && cycle < TIME_LIMIT) {
            const char c = source[IP];
            int DD = D;
            if (isdigit(c)) {
                stk.push(c-'0');
            } else if (c == '$') {
                stk.pop();
            } else if (c == ':') {
                int X = stk.top(); stk.pop();
                stk.push(X); stk.push(X);
            } else if (c == 'W') {
                int A = stk.top(); stk.pop();
                int B = stk.top(); stk.pop();
                stk.push(A); stk.push(B);
            } else if (c == ',') {
                int X = stk.top(); stk.pop();
                output += source[abs(X)%N];
                if (output == source ||
                        output != source.substr(0,output.length())) 
                    break;
            } else if (c == '+') {
                int A = stk.top(); stk.pop(); 
                int B = stk.top(); stk.pop();
                stk.push(A+B);
                if (abs(stk.top()) > 1000000000) break;
            } else if (c == '-') {
                int A = stk.top(); stk.pop(); 
                int B = stk.top(); stk.pop();
                stk.push(A-B);
                if (abs(stk.top()) > 1000000000) break;
            } else if (c == '#') {
                DD *= 2;
            } else if (c == 'R') {
                DD *= -1; D *= -1;
            } else if (c == 'S') {
                int X = stk.top(); stk.pop();
                if (X > 0) stk.push(1);
                else stk.push(-1);
            } else if (c == '_') {
                int X = stk.top(); stk.pop();
                D = DD = X % N;
            } else if (c == 'J') {
                int X = stk.top(); stk.pop();
                IP = abs(X) % N;
            } 
            if (c != 'J')
                IP = (3*N+IP+DD) % N;
            cycle++;
        }
      
        ostringstream res;
        if (source[IP] == '@') {
            res << "BADEND " << cycle;
        } else if (cycle == TIME_LIMIT) {
            res << "TIMEOUT";
        } else if (abs(stk.top()) > 1e+9) {
            res << "OVERFLOW " << cycle;
        } else if (source != output) {
            res << "MISMATCH " << cycle;
        } else {
            res << "QUINES " << cycle;
        }
        return res.str();
    }
};

2009-08-24

StripePainter

| 13:03

問題文, SRM 150

最低何回ペンキを塗りつける必要があるか。DP+メモ化で解ける問題。

224.12/500

class StripePainter {
public:
    int minStrokes(string stripes) {
        const int size = stripes.size();
        memo = vector<vector<vector<int> > >(size,vector<vector<int> >(size+1,vector<int>(128,-1)));
        return go(stripes, 0, size, '?');
    }
private:
    vector<vector<vector<int> > > memo;
    int go(const string& stripes, 
            const int left, const int size, const char color) {
        if (size <= 0) return 0;
        if (memo[left][size][color] >= 0) return memo[left][size][color];
        int best = INT_MAX;
        if (stripes[left] == color) {
            best = go(stripes, left+1, size-1, color);
        } else {
            for (int i = 1; i <= size; i++) 
                best = min(best, 1
                        + go(stripes,left+1,i-1,stripes[left])
                        + go(stripes,left+i,size-i,color));
        }
        memo[left][size][color] = best;
        return best;
    }
};

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-22

BirthdayOdds

| 16:29

問題文, SRM 174

同じ誕生日になる確率。

467.33/500

class BirthdayOdds {
public:
    int minPeople(int minOdds, int daysInYear) {
        double p = 1;
        for (int i = 1; i <= daysInYear; i++) {
            p *= static_cast<double>(daysInYear-i+1)/daysInYear;
            if ((1-p)*100 >= minOdds)
                return i;
        }
        return 0;
    }
};

2009-08-21

WordForm

| 17:15

問題文, SRM 173

与えられた文字列は、どのような母音と子音の組み合わせから成るのか。

468.65/500

class WordForm {
public:
    string getSequence(string word) {
        string sequence;
        bool isPreVowel = false;
        for (int i = 0; i < word.length(); i++) {
            const char c = toupper(word[i]);
            bool isVowel = (i!=0 && !isPreVowel && c=='Y') ||
                c=='A' || c=='E' || c=='I' || c=='O' || c=='U';
            if (i == 0 || isVowel != isPreVowel) {
                if (isVowel) sequence += "V";
                else sequence += "C";
                isPreVowel = isVowel;
            }
        }
        return sequence;
    }
};

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

Archimedes

| 11:09

問題文, SRM 151

円周率の近似値を求める。どうすれば求められるのかは、すぐに分かった。

230.08/250

class Archimedes {
    public:
        double approximatePi(int numSides) {
            return numSides * sin(M_PI/numSides);
        }
};

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-18

CrossCountry

| 11:38

問題文, SRM 171

クロスカントリーの団体戦の順位決め。強引に解いた。

434.52/600

struct Team {
    char id;
    vector<int> ranks;
    int sum;
    Team() {}
    Team(const char id) : id(id), sum(0) {}
    void addMember(const int rank) {
        ranks.push_back(rank);
        if (ranks.size() <= 5)
            sum += rank;
    }
};

bool compTeam(const Team& a, const Team& b) {
    if (a.sum < b.sum) {
        return true;
    } else if (a.sum > b.sum) {
        return false;
    } else {
        if (a.ranks.size() >= 6 && b.ranks.size() >= 6) {
            return a.ranks[5] < b.ranks[5];
        } else if (a.ranks.size() >= 6) {
            return true;
        } else if (b.ranks.size() >= 6) {
            return false;
        } else {
            return a.id < b.id;
        }
    }
}

class CrossCountry {
    public:
        string scoreMeet(int numTeams, string finishOrder) {
            vector<Team> teams;
            for (int i = 0; i < finishOrder.size(); i++) {
                for (int j = 0; j < teams.size()+1; j++) {
                    if (j == teams.size()) {
                        teams.push_back(Team(finishOrder[i]));
                        teams.back().addMember(i+1);
                        break;
                    }
                    if (teams[j].id == finishOrder[i]) {
                        teams[j].addMember(i+1);
                        break;
                    } 
                }
            }
            sort(teams.begin(), teams.end(), compTeam);
            string result;
            for (int i = 0; i < teams.size(); i++) 
                if (teams[i].ranks.size() >= 5)
                    result += string(1, teams[i].id);
            return result;
        }
};

TravonTravon2011/07/22 13:02Thanky Thanky for all this good ifnomratoin!

gupcpicgupcpic2011/07/22 22:31kmdB9M <a href="http://cevhxxxwszda.com/">cevhxxxwszda</a>

veodtbhveodtbh2011/07/23 18:51k7GCNy , [url=http://znpabhftaumk.com/]znpabhftaumk[/url], [link=http://xesvtenonofo.com/]xesvtenonofo[/link], http://mhkeoikkfact.com/

nwckjlffjonnwckjlffjon2011/07/24 22:34Ay0Rwh <a href="http://xydzsizmpqzc.com/">xydzsizmpqzc</a>

ijegpfoijegpfo2011/07/25 02:15l2YNWI , [url=http://cerpmieqmstu.com/]cerpmieqmstu[/url], [link=http://siawcpyjgwzt.com/]siawcpyjgwzt[/link], http://jkowkmsdcydd.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-16

CircleGame

| 17:07

問題文

カードの13(King)と隣接したカード数が13になる場合は、それらの数を抜き、最後に残るデッキのカードの数を求める。問題を連続する数が13になる場合に抜くと、読み間違えてしまって、解くのに時間がかかった。

103.92/250

class CircleGame {
    public:
        int cardsLeft(string deck) {
            map<char,int> toNum;
            toNum['A']=1; toNum['2']=2; toNum['3']=3; toNum['4']=4; toNum['5']=5;
            toNum['6']=6; toNum['7']=7; toNum['8']=8; toNum['9']=9; toNum['T']=10;
            toNum['J']=11; toNum['Q']=12; toNum['K']=13;
            while (true) {
                string::size_type p = deck.find('K');
                if (p == string::npos) break;
                deck.erase(p, 1);
            }
            bool changed = true;
            while (changed) {
                changed = false;
                for (int i = 0; i < deck.size(); i++) {
                    int j = (i+1) % deck.size();
                    if (toNum[deck[i]]+toNum[deck[j]] == 13) {
                        changed = true;
                        string next;
                        for (int k = 0; k < deck.size(); k++)
                            if (k!=i && k!=j)
                                next += deck[k];
                        deck = next;
                        break;
                    }
                }
            }
            return deck.size();
        }
};

Masterbrain

| 12:25

問題文

一回だけ嘘をついていいというルールがある数字当てゲーム

203.27/600

class Masterbrain {
    public:
        int possibleSecrets(vector <string> guesses, vector <string> results) {
            const int numGuesses = guesses.size();
            vector<int> blacks(numGuesses), whites(numGuesses);
            for (int i = 0; i < numGuesses; i++)
                sscanf(results[i].c_str(), "%db %dw", &blacks[i], &whites[i]);
            codes.clear();
            string code(4, ' ');
            make_codes(code, 0);
            set<string> possibleCodes;
            for (vector<string>::const_iterator cd = codes.begin(); 
                    cd != codes.end(); cd++) {
                vector<bool> judges(numGuesses);
                for (int i = 0; i < numGuesses; i++)
                    judges[i] = checkCode(*cd, guesses[i], blacks[i], whites[i]);
                if (find(judges.begin(),judges.end(),false) == judges.end())
                    continue;

                for (int f = 0; f < numGuesses; f++) {
                    for (int i = 0; i < numGuesses+1; i++) {
                        if (i == f) {
                            if (judges[i]) break;
                            else continue;
                        }
                        if (i == numGuesses) {
                            possibleCodes.insert(*cd);
                            break;
                        }
                        if (!judges[i]) break;
                    }
                }
            }
            return possibleCodes.size();
        }
    private:
        vector<string> codes;
        const static int CODE_LENGTH = 4;
        const static int MAX_DIGIT = 7;
        void make_codes(string& code, const int p) {
            if (p == CODE_LENGTH) {
                codes.push_back(code);
                return;
            }
            for (char c = '1'; c < '1'+MAX_DIGIT; c++) {
                code[p] = c;
                make_codes(code, p+1);
            }
        }
        bool checkCode(const string& code, 
                const string& guess, int black, int white) {
            vector<int> cgn(MAX_DIGIT, 0); // counter for guessed number
            vector<int> crw(MAX_DIGIT, 0); // counter for remaining whites
            for (int i = 0; i < CODE_LENGTH; i++) {
                if (code[i] == guess[i]) {
                    black--;
                } else {
                    cgn[guess[i]-'1']++;
                    crw[code[i]-'1']++;
                }
            }
            if (black != 0) return false;
            for (int i = 0; i < MAX_DIGIT; i++)
                white -= min(cgn[i], crw[i]);
            return white == 0;
        }
};

JustinJustin2012/07/09 19:31I see, I supospe that would have to be the case.

itwtrmfvceitwtrmfvce2012/07/10 15:227kAAqh <a href="http://zylafgrfzjbl.com/">zylafgrfzjbl</a>

cdweglzcdweglz2012/07/10 21:17xepmZu , [url=http://onfgnghtzitt.com/]onfgnghtzitt[/url], [link=http://nlacaozvfktq.com/]nlacaozvfktq[/link], http://aepzieiyvpsn.com/

hkdwpsqnvkhkdwpsqnvk2012/07/12 17:09QYS2QK , [url=http://toyoaqaciajc.com/]toyoaqaciajc[/url], [link=http://bwrudfijrmmm.com/]bwrudfijrmmm[/link], http://zvmupojzjimj.com/

2009-08-15

HillHike

| 14:33

問題文

採りえる山の形の数を求める。問題は理解できたが、解法が全然思いつかなかった。

470.68/1000

class HillHike {
    public:
        long long numPaths(int distance, int maxHeight, vector <int> landmarks) {
            long long memory[2][52][51];
            memset(memory, 0, sizeof(memory));
            memory[0][0][0] = 1;
            landmarks.push_back(-1);
            for (int i = 1; i < distance; i++) {
                long long cache[2][52][51];
                memset(cache, 0, sizeof(memory));
                for (int h = 1; h <= maxHeight; h++) {
                    int mh = (h == maxHeight) ? 1 : 0;
                    for (int j = 0; j < landmarks.size(); j++)
                        for (int d = -1; d <= 1; d++) {
                            int lm = (h == landmarks[j]) ? j+1 : j;
                            cache[mh][h][lm] += memory[0][h+d][j];
                            cache[ 1][h][lm] += memory[1][h+d][j];
                        }
                }
                memcpy(memory, cache, sizeof(memory));
            }
            return memory[1][1][landmarks.size()-1];
        }
};

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/