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

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

Lottery

| 15:42

問題文

DIV1の問題を解き始めることにした。この問題から、1問につき1エントリを書く。過去のエントリも近いうちに1問1エントリに変える。

数字を使ったギャンブルで、勝率が高い順に並べる。組み合わせの問題で、解けそうと思いコードを書き始めたが、結局わからなくなり、Editorialを見た。

181.27 / 500 - 01:53:07

bool compValidTicketsNum(const pair<string,long long>& a,
        const pair<string,long long>& b) {
    if (a.second < b.second) {
        return true;
    } else if (a.second > b.second) {
        return false;
    } else {
        return a.first < b.first;
    }
}

class Lottery {
    public:
        vector <string> sortByOdds(vector <string> rules) {
            const int size = rules.size();
            vector <string> result(size);
            if (size == 0) return result;
            vector <pair<string,long long> > name(size);
            vector<int> choices(size), blanks(size);
            for (int i = 0; i < size; i++) {
                int p = find(rules[i].begin(),rules[i].end(),':') - rules[i].begin();
                name[i].first = rules[i].substr(0, p);
                istringstream iss(rules[i].substr(p+1));
                int choices, blanks;
                string sorted, unique;
                iss >> choices >> blanks >> sorted >> unique;
                if (sorted == "F" && unique == "F") {
                    name[i].second = power(choices, blanks);
                } else if (sorted == "T" && unique == "F") {
                    name[i].second = combination(choices+blanks-1, blanks);
                } else if (sorted == "F" && unique == "T") {
                    name[i].second = combination(choices, blanks) * factorial(blanks);
                } else if (sorted == "T" && unique == "T") {
                    name[i].second = combination(choices, blanks);
                }
            }
            stable_sort(name.begin(), name.end(), compValidTicketsNum);
            for (int i = 0; i < size; i++)
                result[i] = name[i].first;
            return result;
        }
    private:
        long long power(const long long x, long long y) {
            long long ret = 1;
            while (y-- > 0) ret *= x;
            return ret;
        }
        long long factorial(long long x) {
            long long ret = 1;
            while (x > 0) {
                ret *= x;
                x--;
            }
            return ret;
        }
        long long combination(long long x, long long y) {
            long long ret = 1;
            for (int i = 0; i < y; i++) {
                ret *= x;
                x--;
            }
            while (y > 1) {
                ret /= y;
                y--;
            }
            return ret;
        }
};

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

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

WhatSort

| 13:34

問題文

引数で与えられたデータは、どんなソート方法を使って並べたものかを求める。もっとコード量が少なくて済む書き方もあるとは思ったが、愚直に6つぶんの比較関数を書いた。

struct Person {
    public:
        string name;
        int age, wt;
        Person() {}
        Person(const string& name, const int age, const int wt) :
            name(name), age(age), wt(wt) {}
        Person& operator=(const Person& p) {
            name = p.name;
            age = p.age;
            wt = p.wt;
            return *this;
        }
};

bool operator==(const Person& a, const Person& b) {
    return a.name==b.name && a.age==b.age && a.wt==b.wt;
}

bool operator!=(const Person& a, const Person& b) {
    return !(a == b);
}

bool NAW(const Person& a, const Person& b)
{
    if (a.name < b.name) {
        return true;
    } else if (a.name > b.name) {
        return false;
    } else {
        if (a.age < b.age) {
            return true;
        } else if (a.age > b.age) {
            return false;
        } else {
            return a.wt > b.wt;
        }
    }
}

bool NWA(const Person& a, const Person& b)
{
    if (a.name < b.name) {
        return true;
    } else if (a.name > b.name) {
        return false;
    } else {
        if (a.wt > b.wt) {
            return true;
        } else if (a.wt < b.wt) {
            return false;
        } else {
            return a.age < b.age;
        }
    }
}

bool ANW(const Person& a, const Person& b)
{
    if (a.age < b.age) {
        return true;
    } else if (a.age > b.age) {
        return false;
    } else {
        if (a.name < b.name) {
            return true;
        } else if (a.name > b.name) {
            return false;
        } else {
            return a.wt > b.wt;
        }
    }
}

bool AWN(const Person& a, const Person& b)
{
    if (a.age < b.age) {
        return true;
    } else if (a.age > b.age) {
        return false;
    } else {
        if (a.wt > b.wt) {
            return true;
        } else if (a.wt < b.wt) {
            return false;
        } else {
            return a.name < a.name;
        }
    }
}

bool WAN(const Person& a, const Person& b)
{
    if (a.wt > b.wt) {
        return true;
    } else if (a.wt < b.wt) {
        return false;
    } else {
        if (a.age < b.age) {
            return true;
        } else if (a.age > b.age) {
            return false;
        } else {
            return a.name < a.name;
        }
    }
}

bool WNA(const Person& a, const Person& b)
{
    if (a.wt > b.wt) {
        return true;
    } else if (a.wt < b.wt) {
        return false;
    } else {
        if (a.name < b.name) {
            return true;
        } else if (a.name > b.name) {
            return false;
        } else {
            return a.age < b.age;
        }
    }
}

class WhatSort {
    public:
        string sortType(vector <string> name, vector <int> age, vector <int> wt) {
            const int numPeople = name.size();
            vector<Person> people(numPeople);
            for (int i = 0; i < numPeople; i++) 
                people[i] = Person(name[i], age[i], wt[i]);

            const static int NUM_SORT_KINDS = 6;
            bool (*compFunc[NUM_SORT_KINDS])(const Person&, const Person&) = { 
                NAW, NWA, ANW, AWN, WAN, WNA };
            const string nameOfSorts[NUM_SORT_KINDS] = {
                "NAW", "NWA", "ANW", "AWN", "WAN", "WNA" };
            string answer = "NOT";
            for (int i = 0; i < NUM_SORT_KINDS; i++) {
                vector<Person> sorted(people);
                sort(sorted.begin(), sorted.end(), compFunc[i]);
                if (isSameOrder(sorted, people)) {
                    if (answer == "NOT") {
                        answer = nameOfSorts[i];
                    } else {
                        answer = "IND";
                        break;
                    }
                }
            }
            return answer;
        }
    private:
        bool isSameOrder(const vector<Person>& a, const vector<Person>& b) {
            for (int i = 0; i < a.size(); i++) {
                if (a[i] != b[i]) 
                    return false;
            }
            return true;
        }
};

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

Pool

| 13:05

問題文

特定のボールの積み方にするには何回ボールを交換すればいいのかを求める。

class Pool {
    public:
        int rackMoves(vector <int> triangle) {
            const static int NUM_BALLS = 15;
            const static string PATTERN = "XOOX8XOXOXXOXOO";
            int ans = 0;
            if (triangle[4] != 8) {
                swap(triangle[4], *find(triangle.begin(),triangle.end(),8));
                ans++;
            }
            int a=0, b=0;
            for (int i = 0; i < NUM_BALLS; i++) {
                if (triangle[i] <= 7) {
                    if (PATTERN[i] == 'X') a++;
                    else                   b++;
                }
            }
            ans += min(a, b);
            return ans;
        }
};