Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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