Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-04-04

PowerOutage

| 15:52

問題文

333.10->1010.51

minMinutes = 2*total - farthestDistance

const static int MAX_ELEMENT = 50;
const static int INFTY = 9999999;

class PowerOutage {
public:
    int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength) {
        vector<vector<int> > J(MAX_ELEMENT, vector<int>(MAX_ELEMENT,INFTY));
        int elements = fromJunction.size();
        for (int i = 0; i < elements; i++) {
            J[fromJunction[i]][toJunction[i]] 
                = J[toJunction[i]][fromJunction[i]] = ductLength[i];
        }

        int farthestDis = dijkstra(J);
        int total = accumulate(ductLength.begin(), ductLength.end(), 0);
        int minMinutes = 2*total - farthestDis;
        return minMinutes;
    }

private:
    int dijkstra(const vector<vector<int> >& J) {
        vector<int> D(MAX_ELEMENT);
        for (int i = 1; i < MAX_ELEMENT; i++) {
            D[i] = J[0][i];
        }

        vector<bool> visited(MAX_ELEMENT, false);
        while (true) {
            int minDis = INFTY;
            int minIdx = -1;
            for (int j = 1; j < MAX_ELEMENT; j++) {
                if (!visited[j] && D[j] < minDis) {
                    minDis = D[j];
                    minIdx = j;
                }
            }
            if (minIdx == -1) 
                break;
            visited[minIdx] = true;

            for (int j = 1; j < MAX_ELEMENT; j++) {
                D[j] = min(D[j], minDis+J[minIdx][j]);
            }
        }

        int maxDis = 0;
        for (int i = 0; i < MAX_ELEMENT; i++) {
            if (D[i] != INFTY && D[i] > maxDis)
                maxDis = D[i];
        }
        return maxDis;
    }
};

BinaryCode

| 15:56

問題文

221.33->540.49 / 550

最後の数が 0 かどうかを確認する必要がある。

class BinaryCode {
public:
    vector <string> decode(string message) {
        const int len = message.length();
        vector <string> result;
        for (int i = 0; i <= 1; i++) {
            vector<int> p(len+2, 0);
            p[1] = i;
            for (int j = 0; ; j++) {
                int q = (message[j]-'0')-p[j]-p[j+1];
                if (q == 0 || q == 1) {
                    p[j+2] = q;
                    if (j == len-1) {
                        if (q == 0) {
                            result.push_back(string(len,'0'));
                            for (int k = 0; k < len; k++)
                                result.back()[k] += p[k+1];
                        } else
                            result.push_back("NONE");
                        break;
                    }
                } else {
                    result.push_back("NONE");
                    break;
                }
            }
        }
        return result;
    }
};

Time

| 12:05

問題文

189.48 -> 199.52

seconds を H:M:S の形に直すだけという単純な問題。

class Time {
public:
    string whatTime(int seconds) {
        ostringstream os;
        os << (seconds/3600) << ":" 
            << (seconds%3600/60) << ":"
            << (seconds%60);
        return os.str();
    }
};