Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-02

MatchMaking

| 13:52

問題文, SRM 203

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

相性のよい組み合わせを作る。

462.48/600

struct Person {
    string name, answer;
    Person() {}
    Person(const string& name, const string& answer) :
        name(name), answer(answer) {}
};

bool operator< (const Person& a, const Person& b) {
    return a.name < b.name;
}

class MatchMaking {
public:
    string makeMatch(vector <string> namesWomen, vector <string> answersWomen, vector <string> namesMen, vector <string> answersMen, string queryWoman) {
        const int numPersons = namesWomen.size();
        const int numAnswers = answersWomen[0].size();
        vector<Person> women, men;
        for (int i = 0; i < numPersons; i++) {
            women.push_back(Person(namesWomen[i], answersWomen[i]));
            men.push_back(Person(namesMen[i], answersMen[i]));
        }
        sort(women.begin(), women.end());
        sort(men.begin(), men.end());

        vector<bool> selected(numPersons, false);
        for (int i = 0; i < numPersons; i++) {
            int maxIdx=0, maxCount=INT_MIN;
            for (int j = 0; j < numPersons; j++) {
                if (selected[j]) continue;
                int count = 0;
                for (int k = 0; k < numAnswers; k++)
                    if (women[i].answer[k] == men[j].answer[k])
                        count++;
                if (count > maxCount) {
                    maxCount = count;
                    maxIdx = j;
                }
            }
            if (women[i].name == queryWoman)
                return men[maxIdx].name;
            selected[maxIdx] = true;
        }
        return "";
    }
};

2009-09-01

| 17:45

問題文, SRM 203

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

使用可能なユーザ名を返す。

242.00/250

class UserName {
public:
    string newMember(vector <string> existingNames, string newName) {
        if (find(existingNames.begin(),existingNames.end(),newName) 
                == existingNames.end())
            return newName;
        for (int i = 1; ; i++) {
            ostringstream nameoss;
            nameoss << newName << i;
            if (find(existingNames.begin(),existingNames.end(),nameoss.str())
                    == existingNames.end())
                return nameoss.str();
        }
        return "";
    }
};

MitchellMitchell2011/07/11 00:05Big help, big help. And superlative news of crouse.

veiutvcwcveiutvcwc2011/07/11 02:29TlCswI <a href="http://vjnggvexbwuu.com/">vjnggvexbwuu</a>

zoksriviopzoksriviop2011/07/11 21:51epdS5v , [url=http://gqqjyfaqwssc.com/]gqqjyfaqwssc[/url], [link=http://mbceaafjqxom.com/]mbceaafjqxom[/link], http://qzkaecclvamc.com/

ntetzpntetzp2011/07/13 18:23bYD1yS <a href="http://bgyraruehckt.com/">bgyraruehckt</a>

mxixglmxixgl2011/07/14 00:35GtzmkZ , [url=http://mxgzmwjlggpm.com/]mxgzmwjlggpm[/url], [link=http://xraideylozrg.com/]xraideylozrg[/link], http://jcutzvphyqwn.com/