Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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>

2009-04-30

VendingMachine

| 17:49

問題文

392.74->891.38 / 1000

問題文の通りに実装するだけ。

struct PurchaseInfo {
public:
    int shelf, column, time;
    PurchaseInfo(const string& purchase) {
        istringstream iss(purchase);
        char pat;
        iss >> shelf >> pat >> column >> pat >> time;
    }
    PurchaseInfo() {}
};

class VendingMachine {
public:
    int motorUse(vector <string> prices, vector <string> purchases) {
        M = prices.size();
        vector<vector<int> > machine(M, vector<int>());
        for (int i = 0; i < M; i++) {
            istringstream iss(prices[i]);
            int tmp;
            while (iss >> tmp) {
                machine[i].push_back(tmp);
            }
        }
        N = machine[0].size();
        vector<int> colPrice(N, 0);
        for (int i = 0; i < N; i++) 
            for (int j = 0; j < M; j++)
                colPrice[i] += machine[j][i];

        L = purchases.size();
        vector<PurchaseInfo> pInfos;
        for (int i = 0; i < L; i++) {
            pInfos.push_back(PurchaseInfo(purchases[i]));
        }

        int pos = getHighestCol(colPrice);
        int motorRunning = getDistance(0, pos);
        int s = pInfos[0].shelf;
        int c = pInfos[0].column;
        if (machine[s][c] == 0) 
            return -1;
        motorRunning += getDistance(pos, c);
        colPrice[c] -= machine[s][c];
        machine[s][c] = 0;
        pos = c;
        for (int i = 1; i < L; i++) {
            if ((pInfos[i].time-pInfos[i-1].time) >= 5) {
                int highestPos = getHighestCol(colPrice);
                motorRunning += getDistance(pos, highestPos);
                pos = highestPos;
            }
            s = pInfos[i].shelf;
            c = pInfos[i].column;
            if (machine[s][c] == 0)
                return -1;
            motorRunning += getDistance(pos, c);
            colPrice[c] -= machine[s][c];
            machine[s][c] = 0;
            pos = c;
        }
        motorRunning += getDistance(pos, getHighestCol(colPrice));

        return motorRunning;
    }
private:
    int M, N, L;
    int getHighestCol(const vector<int>& colPrice) {
        int highest = -1;
        int pos = -1;
        for (int i = 0; i < N; i++) {
            if (highest < colPrice[i]) {
                highest = colPrice[i];
                pos = i;
            }
        }
        return pos;
    }
    int getDistance(const int src, const int dir) {
        if (src < dir) {
            return min(dir-src, src+(N-dir));
        } else {
            return min(src-dir, dir+(N-src));
        }
    }
};

ExerciseMachine

| 17:51

問題文

266.14->498.44 / 500

これも問題がわかりにくい。エクササイズの進捗率が小数点以下を含まない時、経過時間も小数点以下を含まない場合にしか、その進捗率を表示しないという、妙なエクササイズマシンの話。gcd(s,100)-1でも解を求められる。

class ExerciseMachine {
public:
    int getPercentages(string time) {
        int HH, MM, SS;
        char pat;
        istringstream iss(time);
        iss >> HH >> pat >> MM >> pat >> SS;
        int s = (HH*60 + MM)*60 + SS;

        int count = 0;
        for (int i = 1; i <= 99; i++)
            if ((i*s)%100 == 0)
                count++;
        return count;
    }
};

DitherCounter

| 21:36

問題文

207.35->249.12 / 250

問題文がわかりにくいなと思ったが、screen 中に dithered に含まれる文字が何個含まれているかを数えるだけの問題だった。

class ImageDithering {
public:
    int count(string dithered, vector <string> screen) {
        vector<bool> check(256, false);
        for (int i = 0; i < dithered.length(); i++)
            check[dithered[i]] = true;

        int counter = 0;
        for (int i = 0; i < screen.size(); i++)
            for (int j = 0; j < screen[0].length(); j++)
                if (check[screen[i][j]])
                    counter++;
        return counter;
    }
};