Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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