Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

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

Swimmers

| 19:33

問題文

川を往復するのに必要な時間を求める。

224.03/250 - 00:10:06

class Swimmers {
    public:
        vector <int> getSwimTimes(vector <int> distances, vector <int> speeds, int current) {
            const int numSwimmers = distances.size();
            vector <int> result(numSwimmers);
            for (int i = 0; i < numSwimmers; i++) {
                if (distances[i] == 0) {
                    result[i] = 0;
                } else if (current >= speeds[i]) {
                    result[i] = -1;
                } else {
                    result[i] = static_cast<int>(
                            static_cast<double>(distances[i]) / (speeds[i]-current)
                            + static_cast<double>(distances[i]) / (speeds[i]+current)); 
                }
            }
            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-10

StairClimb

| 19:34

問題文

階段登り。

248.03/250

class StairClimb {
    public:
        int stridesTaken(vector <int> flights, int stairsPerStride) {
            int steps = 0;
            const static int TURN_STEPS = 2;
            for (int i = 0; i < flights.size(); i++) {
                steps += TURN_STEPS;
                steps += flights[i] / stairsPerStride;
                if (flights[i]%stairsPerStride != 0) steps++;
            }
            steps -= TURN_STEPS;
            return steps;
        }
};

2009-08-08

Orchard

| 20:44

SRM447 (DIV2)の結果は、300と500を通すことができ、Ratingは 1063 -> 1099 と上がった。両問題とももう少し速くサブミットできたのだが、コードを何度も確認していたため、しょぼいポイントになった。慎重になりすぎた。

問題文

幅優先探索(BFS)で解ける問題。実装に手間取った。

328.06/900 - 01:03:38

enum INDEX { Y_IDX=0, X_IDX=1, DIS_IDX=2};

class Orchard {
    public:
        vector <int> nextTree(vector <string> orchard) {
            const int size = orchard.size();
            vector<int> best = vector<int>(2);
            int longest = -1;
            for (int y = 0; y < size; y++) 
                for (int x = 0; x < size; x++)
                    if (orchard[y][x] == '-') {
                        set<vector<int> > visited;
                        queue<vector<int> > Q;
                        vector<int> tmp(3);
                        tmp[Y_IDX]=y; tmp[X_IDX]=x; tmp[DIS_IDX] = 0;
                        Q.push(tmp);
                        while (!Q.empty()) {
                            vector<int> v = Q.front(); Q.pop();
                            if (v[Y_IDX] < 0 || v[Y_IDX] >= size ||
                                    v[X_IDX] < 0 || v[X_IDX] >= size ||
                                    orchard[v[Y_IDX]][v[X_IDX]] == 'T') {
                                if (v[DIS_IDX] > longest) {
                                    longest = v[DIS_IDX];
                                    best[Y_IDX] = y + 1;
                                    best[X_IDX] = x + 1;
                                }
                                break;
                            }
                            tmp = vector<int>(v.begin(), v.begin()+2);
                            if (visited.find(tmp) != visited.end()) continue;
                            visited.insert(tmp);
                            vector<int> newV(3); 
                            newV[DIS_IDX] = v[DIS_IDX] + 1;
                            newV[Y_IDX]=v[Y_IDX]+1; newV[X_IDX]=v[X_IDX]; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]-1; newV[X_IDX]=v[X_IDX]; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]; newV[X_IDX]=v[X_IDX]+1; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]; newV[X_IDX]=v[X_IDX]-1; Q.push(newV);
                        }
                    }
            return best;
        }
};

BinaryCardinality

| 19:29

問題文

立っているビット数が少ない順にソート。300の問題よりこっちの方が解きやすかった。提出した後に気づいたことだけど、比較関数の中でbitsetを使えば、余計なvector配列を使う必要がないな。

453.99/500 - 00:09:18

bool compBinary(const bitset<32>& a, const bitset<32>& b)
{
    if (a.count() < b.count()) {
        return true;
    } else if (a.count() > b.count()) {
        return false;
    } else {
        return a.to_ulong() < b.to_ulong();
    }
}

class BinaryCardinality {
    public:
        vector <int> arrange(vector <int> numbers) {
            const int size = numbers.size();
            vector<bitset<32> > binaries(size);
            for (int i = 0; i < size; i++)
                binaries[i] = numbers[i];
            sort(binaries.begin(), binaries.end(), compBinary);
            vector <int> result(size);
            for (int i = 0; i < size; i++)
                result[i] = static_cast<int>(binaries[i].to_ulong());
            return result;
        }
};

Workshop

| 19:29

問題文

作れる三角形の数を数える。

267.09/300 - 00:10:38

class Workshop {
    public:
        int pictureFrames(vector <int> pieces) {
            int result = 0;
            sort(pieces.begin(), pieces.end());
            const int size = pieces.size();
            for (int i = 0; i < size-2; i++) {
                for (int j = i+1; j < size-1; j++) {
                    for (int k = j+1; k < size; k++) {
                        if (pieces[i]<pieces[j]+pieces[k] &&
                                pieces[j]<pieces[i]+pieces[k] &&
                                pieces[k]<pieces[i]+pieces[j])
                            result++;
                    }
                }
            }
            return result;
        }
};

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

BritishCoins

| 19:21

問題文

コインの数。

242.83/250 - 00:05:05

class BritishCoins {
    public:
        vector <int> coins(int pence) {
            const static int SHILLING = 12;
            const static int POUND = 20 * SHILLING;
            vector <int> result(3);
            result[0] = pence / POUND;
            pence %= POUND;
            result[1] = pence / SHILLING;
            pence %= SHILLING;
            result[2] = pence;
            return result;
        }
};

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

PaperFold

| 18:43

問題文

8回以下の回数だけ紙を折ることで、箱にその紙を納められるか。

class PaperFold {
    public:
        int numFolds(vector <int> paper, vector <int> box) {
            box.push_back(0);
            queue<vector<int> > Q;
            Q.push(box);
            while (!Q.empty()) {
                vector<int> b = Q.front(); Q.pop();
                if (b[2] > 8) continue;
                if (isFit(paper, b)) return b[2];
                b[2]++;
                b[0] *= 2; Q.push(b);
                b[0] /= 2; b[1] *= 2; Q.push(b);
            }
            return -1;
        }
    private:
        bool isFit(const vector<int>& paper, const vector<int>& box) {
            return (paper[0] <= box[0] && paper[1] <= box[1]) ||
                (paper[0] <= box[1] && paper[1] <= box[0]);
        }
};

2009-07-25

BombSweeper

| 05:47

問題文

ゲームの勝率を求める。

class BombSweeper {
public:
    double winPercentage(vector <string> board) {
        const int height = board.size();
        const int width = board[0].length();
        const static int DIR_KINDS = 8;
        const int d[DIR_KINDS][2] = {
            {-1,-1}, {-1, 0}, {-1, 1},
            { 0,-1},          { 0, 1},
            { 1,-1}, { 1, 0}, { 1, 1} };

        int wins=0, loses=0;
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (board[y][x] == 'B') {
                    loses++;
                    continue;
                }
                for (int i = 0; i < DIR_KINDS; i++) {
                    const int dy = y + d[i][0];
                    const int dx = x + d[i][1];
                    if (0<=dy&&dy<height && 0<=dx&&dx<width) {
                        if (board[dy][dx] == 'B') break;
                    }
                    if (i == DIR_KINDS-1) wins++;
                }
            }
        }
        const double percentage = 100.0l * wins / (wins+loses); 
        return percentage;
    }
};

DiskSpace

| 05:47

問題文

使うハードディスクの数を最小限にする。

class DiskSpace {
public:
    int minDrives(vector <int> used, vector <int> total) {
        int totalUsed = accumulate(used.begin(),used.end(),0);
        sort(total.rbegin(), total.rend());
        for (int i = 0; i < total.size(); i++) {
            if (totalUsed <= total[i]) return i+1;
            else totalUsed -= total[i];
        }
        return total.size();
    }
};