Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-19

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

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

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

RecurrenceRelation

| 12:51

問題文

与えられた漸化式のN番目の値を求める。システムテストで1回落とされた。

298.29/500 - 00:20:58

class RecurrenceRelation {
    public:
        int moduloTen(vector <int> coefficients, vector <int> initial, int N) {
            const int k = coefficients.size();
            for (int i = 0; i < k; i++) 
                initial[i] = myMod(initial[i]);
            cout << endl;
            for (int i = k; i <= N; i++) {
                int x = 0;
                for (int j = i-1; j >= i-k; j--) 
                    x += coefficients[k-(i-j)] * initial[j];
                cout << i << " " << x << endl;
                x = myMod(x);
                initial.push_back(x);
            }
            return initial[N];
        }
    private:
        int myMod(const int x) {
            if (x >= 0) return x % 10;
            else return (10 - ((-x)%10)) % 10;
        }
};

JusticeJustice2011/07/09 15:18Created the greatest artclies, you have.

dhumgkuquyrdhumgkuquyr2011/07/10 00:44RBBBkV <a href="http://hjbppmyhkpug.com/">hjbppmyhkpug</a>

oipwdeoipwde2011/07/11 20:03vO7rh7 <a href="http://ampmjgepjkgf.com/">ampmjgepjkgf</a>

2009-08-10

NumberGuesser

| 19:34

問題文

数字を推測。自力で解けなかった。総当たりで解いたが、数学的な解法もある。

190.54/500 - 01:06:07 (cheated)

class NumberGuesser {
    public:
        int guess(string leftOver) {
            int candidate = 0;
            for (int d = 1; d <= 9; d++) {
                int found = 0;
                for (int i = 0; i < 4; i++) {
                    ostringstream oss;
                    oss << leftOver.substr(0,i) << d << leftOver.substr(i);
                    int z;
                    istringstream(oss.str()) >> z;
                    for (int x = 1; x+z <= 9998; x++) {
                        int y = x + z;
                        if (isDigitMatch(x, y)) {
                            candidate = d;
                            found++;
                            break;
                        }
                    }
                }
                if (found == 4) return d;
            }
            return candidate;
        }
    private:
        bool isDigitMatch(int x, int y) {
            vector<int> ndigits(10, 0);
            while (x > 0) {
                if (x%10 != 0) ndigits[x%10]++;
                x /= 10;
            }
            while (y > 0) {
                if (y%10 != 0) ndigits[y%10]--;
                y /= 10;
            }
            for (int i = 0; i < ndigits.size(); i++) {
                if (ndigits[i] != 0)
                    return false;
            }
            return true;
        }
};

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

PartySeats

| 19:16

問題文 PartySeats

席順決め。

class PartySeats {
    public:
        vector <string> seating (vector <string> attendees) {
            multiset<string> boys, girls;
            for (int i = 0; i < attendees.size(); i++) {
                string name, gender;
                istringstream iss(attendees[i]);
                iss >> name >> gender;
                if (gender[0] == 'b') boys.insert(name);
                else girls.insert(name);
            }
            vector<string> result;
            if (boys.size() != girls.size() || boys.size()%2 == 1)
                return result;
            multiset<string>::const_iterator bItr = boys.begin();
            multiset<string>::const_iterator gItr = girls.begin();
            result.push_back("HOST");
            for (int i = 0; i < attendees.size()/2; i += 2) {
                result.push_back(*gItr); gItr++;
                result.push_back(*bItr); bItr++;
            }
            result.push_back("HOSTESS");
            for (int i = attendees.size()/2; i < attendees.size(); i += 2) {
                result.push_back(*bItr); bItr++;
                result.push_back(*gItr); gItr++;
            }
            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-05

Inchworm

| 18:52

問題文

虫が食べた葉っぱの枚数を数える。

class Inchworm {
    public:
        int lunchtime(int branch, int rest, int leaf) {
            int consumed = 0;
            for (int p = 0; p <= branch; p += leaf) {
                if (p%rest == 0) 
                    consumed++;
            }
            return consumed;
        }
};

2009-08-04

SMBus

| 12:55

問題文

バスの調停のシミュレーション。

class SMBus {
    public:
        int transmitTime(vector <string> messages, vector <int> times) {
            const int size = messages.size();
            vector<bool> transmitted(size, false);
            int totalTime = 0;
            for (int i = 0; i < size; i++) {
                list<int> candidates;
                for (int j = 0; j < size; j++) {
                    if (!transmitted[j]) candidates.push_back(j);
                }
                int idx = 0;
                while (candidates.size() > 1) {
                    int slowest = INT_MIN;
                    char smallest = '9'+1;
                    for (list<int>::const_iterator itr = candidates.begin(); 
                            itr != candidates.end(); itr++) {
                        if (messages[*itr].length() > idx) {
                            slowest = max(slowest, times[*itr]);
                            smallest = min(smallest, messages[*itr][idx]);
                        }
                    }
                    for (list<int>::iterator itr = candidates.begin();
                            itr != candidates.end(); ) {
                        if (messages[*itr][idx] > smallest) {
                            itr = candidates.erase(itr);
                        } else {
                            itr++;
                        }
                    }
                    totalTime += slowest;
                    idx++;
                }
                const int winner = *candidates.begin();
                totalTime += (messages[winner].length()-idx) * times[winner];
                transmitted[winner] = true;
            }

            return totalTime;
        }
};