Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-28

Collision

| 13:32

問題文, SRM 153

2つの確率の差を求める。

178.38/450 (cheated)

class Collision {
public:
    double probability(vector <int> assignments, int ids) {
        double p1=1, p2=1;
        int d = ids;
        for (int i = 0; i < assignments.size(); i++) {
            if (assignments[i] > ids) return 0;
            int n = ids;
            for (int j = 0; j < assignments[i]; j++) {
                p1 *= (double) d / ids;
                p2 *= (double) d / n;
                d--; n--;
            }
        }
        return p2 - p1;
    }
};

2009-07-22

PickTeam

| 13:32

問題文

相性が最高なチームを作る。なにか特別な方法があるのかと思ったけど、総当たりで解ける問題だった。

class PickTeam {
public:
    vector <string> pickPeople(int teamSize, vector <string> people) {
        const int n = people.size();
        vector<vector<int> > g(n, vector<int>(n));
        vector<string> names(n);
        for (int i = 0; i < n; i++) {
            istringstream iss(people[i]);
            iss >> names[i];
            for (int j = 0; j < n; j++) {
                iss >> g[i][j];
            }
        }

        maxScore = INT_MIN;
        findMaxScore(bitset<32>(0), 0, 0, teamSize, n, g);
        vector <string> result;
        for (int i = 0; i < n; i++) {
            if (maxSet[i] == 1) {
                result.push_back(names[i]);
            }
        }
        sort(result.begin(), result.end());
        return result;
    }
private:
    int maxScore;
    bitset<32> maxSet;
    void findMaxScore(bitset<32> subset, const int ptr, const int onBits,
            const int teamSize, const int n, const vector<vector<int> >& g) {
        if (onBits == teamSize) {
            int score = 0;
            for (int i = 0; i < n; i++) {
                if (subset[i] != 1) continue;
                for (int j = i+1; j < n; j++) {
                    if (subset[j] != 1) continue;
                    score += g[i][j];
                }
            }
            if (score > maxScore) {
                maxScore = score;
                maxSet = subset;
            }
            return;
        }
        if (ptr == n) return;
        findMaxScore(subset, ptr+1, onBits, teamSize, n, g);
        subset[ptr] = 1;
        findMaxScore(subset, ptr+1, onBits+1, teamSize, n, g);
    }
};

Inventory

| 19:55

問題文

30日間換算で1商品当たりいくつ売れるのかを計算。

const static double EPS = 1.0e-9;

class Inventory {
public:
    int monthlyOrder(vector <int> sales, vector <int> daysAvailable) {
        const static int DAYS_OF_MONTH = 30;
        double sum = 0;
        int availableItems = 0;
        for (int i = 0; i < sales.size(); i++) {
            if (daysAvailable[i] != 0) {
                sum += (static_cast<double>(sales[i])/daysAvailable[i])
                                                        * DAYS_OF_MONTH;
                availableItems++;
            }
        }
        return static_cast<int>(ceil(sum/availableItems-EPS));
    }
};

MostProfitable

| 19:53

問題文

最大の利益を上げる商品を返す。利益を上げられる商品がなかったら空文字列を返す。

class MostProfitable {
public:
    string bestItem(vector <int> costs, vector <int> prices, vector <int> sales, vector <string> items) {
        int mostProfit = INT_MIN;
        int mostIdx = 0;
        for (int i = 0; i < costs.size(); i++) {
            int profit = (prices[i]-costs[i]) * sales[i];
            if (profit > mostProfit) {
                mostProfit = profit;
                mostIdx = i;
            }
        }
        if (mostProfit > 0) return items[mostIdx];
        else return "";
    }
};