Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-06

MedalTable

| 14:35

問題文, SRM 209

Algorithm Tutorials -- How to Find a Solutionから。

オリンピックで、国ごとのメダル獲得数が多い順に表示。単純な問題なのに、解くのに時間かかりすぎ。

193.53/300

struct Country {
    string name;
    const static int MEDAL_KINDS = 3;
    int medals[MEDAL_KINDS];
    Country() {}
    Country(const string& name) : name(name) {
        for (int i = 0; i < MEDAL_KINDS; i++) medals[i] = 0;
    }
    string getInfo() {
        ostringstream oss;
        oss << name;
        for (int i = 0; i < MEDAL_KINDS; i++) oss << " " << medals[i];
        return oss.str();
    }
};
bool operator< (const Country& a, const Country& b) {
    for (int i = 0; i < Country::MEDAL_KINDS; i++) {
        if (a.medals[i] > b.medals[i]) return true;
        else if (a.medals[i] < b.medals[i]) return false;
    }
    return a.name < b.name;
}

class MedalTable {
public:
    vector <string> generate(vector <string> results) {
        map<string,Country> countries;
        for (int i = 0; i < results.size(); i++) {
            istringstream iss(results[i]);
            for (int j = 0; j < Country::MEDAL_KINDS; j++) {
                string name;
                iss >> name;
                if (countries.find(name) == countries.end()) 
                    countries[name] = Country(name);
                countries[name].medals[j]++; 
            }
        }
        set<Country> countriesSet;
        for (map<string,Country>::const_iterator itr = countries.begin();
                itr != countries.end(); itr++)
            countriesSet.insert(itr->second);
        vector<string> result;
        for (set<Country>::iterator itr = countriesSet.begin();
                itr != countriesSet.end(); itr++) {
            Country c = *itr;
            result.push_back(c.getInfo());
        }
        return result;
    }
};