Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-13

Lottery

| 15:42

問題文

DIV1の問題を解き始めることにした。この問題から、1問につき1エントリを書く。過去のエントリも近いうちに1問1エントリに変える。

数字を使ったギャンブルで、勝率が高い順に並べる。組み合わせの問題で、解けそうと思いコードを書き始めたが、結局わからなくなり、Editorialを見た。

181.27 / 500 - 01:53:07

bool compValidTicketsNum(const pair<string,long long>& a,
        const pair<string,long long>& b) {
    if (a.second < b.second) {
        return true;
    } else if (a.second > b.second) {
        return false;
    } else {
        return a.first < b.first;
    }
}

class Lottery {
    public:
        vector <string> sortByOdds(vector <string> rules) {
            const int size = rules.size();
            vector <string> result(size);
            if (size == 0) return result;
            vector <pair<string,long long> > name(size);
            vector<int> choices(size), blanks(size);
            for (int i = 0; i < size; i++) {
                int p = find(rules[i].begin(),rules[i].end(),':') - rules[i].begin();
                name[i].first = rules[i].substr(0, p);
                istringstream iss(rules[i].substr(p+1));
                int choices, blanks;
                string sorted, unique;
                iss >> choices >> blanks >> sorted >> unique;
                if (sorted == "F" && unique == "F") {
                    name[i].second = power(choices, blanks);
                } else if (sorted == "T" && unique == "F") {
                    name[i].second = combination(choices+blanks-1, blanks);
                } else if (sorted == "F" && unique == "T") {
                    name[i].second = combination(choices, blanks) * factorial(blanks);
                } else if (sorted == "T" && unique == "T") {
                    name[i].second = combination(choices, blanks);
                }
            }
            stable_sort(name.begin(), name.end(), compValidTicketsNum);
            for (int i = 0; i < size; i++)
                result[i] = name[i].first;
            return result;
        }
    private:
        long long power(const long long x, long long y) {
            long long ret = 1;
            while (y-- > 0) ret *= x;
            return ret;
        }
        long long factorial(long long x) {
            long long ret = 1;
            while (x > 0) {
                ret *= x;
                x--;
            }
            return ret;
        }
        long long combination(long long x, long long y) {
            long long ret = 1;
            for (int i = 0; i < y; i++) {
                ret *= x;
                x--;
            }
            while (y > 1) {
                ret /= y;
                y--;
            }
            return ret;
        }
};

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