Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

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/