Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-30

UserId

| 11:21

問題文, SRM 164

ユーザIDを決める。

207.86/300

class UserId {
public:
    string id(vector <string> inUse, string first, string middle, string last) {
        first = truncate(first);
        middle = truncate(middle);
        last = truncate(last);
        if ((first == "BAD DATA" || middle == "BAD DATA" || last == "BAD DATA") ||
                first.length() < 2 || last.length() < 2)
            return "BAD DATA";

        string candidate = first[0] + last;
        if (candidate.length() > 8) candidate = candidate.substr(0,8);
        if (find(inUse.begin(),inUse.end(),candidate) == inUse.end())
            return candidate;
        if (middle.length() >= 1) {
            candidate = first[0] + string(1,middle[0]) + last;
            if (candidate.length() > 8) candidate = candidate.substr(0,8);
            if (find(inUse.begin(),inUse.end(),candidate) == inUse.end())
                return candidate;
        }
        for (int i = 1; i <= 99; i++) {
            candidate = first[0] + last;
            if (candidate.length() > 6) candidate = candidate.substr(0,6);
            ostringstream oss;
            oss << candidate << setw(2) << setfill('0') << i;
            candidate = oss.str();
            if (find(inUse.begin(),inUse.end(),candidate) == inUse.end())
                return candidate;
        }
        return "BAD DATA";
    }
private:
    string truncate(const string& s) {
        string ret;
        for (int i = 0; i < s.length(); i++) {
            if (isalpha(s[i])) ret += tolower(s[i]);
            else if (s[i] != '\'' && s[i] != ' ') return "BAD DATA";
        }
        return ret;
    }
};

2009-08-06

WhatSort

| 13:34

問題文

引数で与えられたデータは、どんなソート方法を使って並べたものかを求める。もっとコード量が少なくて済む書き方もあるとは思ったが、愚直に6つぶんの比較関数を書いた。

struct Person {
    public:
        string name;
        int age, wt;
        Person() {}
        Person(const string& name, const int age, const int wt) :
            name(name), age(age), wt(wt) {}
        Person& operator=(const Person& p) {
            name = p.name;
            age = p.age;
            wt = p.wt;
            return *this;
        }
};

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

bool operator!=(const Person& a, const Person& b) {
    return !(a == b);
}

bool NAW(const Person& a, const Person& b)
{
    if (a.name < b.name) {
        return true;
    } else if (a.name > b.name) {
        return false;
    } else {
        if (a.age < b.age) {
            return true;
        } else if (a.age > b.age) {
            return false;
        } else {
            return a.wt > b.wt;
        }
    }
}

bool NWA(const Person& a, const Person& b)
{
    if (a.name < b.name) {
        return true;
    } else if (a.name > b.name) {
        return false;
    } else {
        if (a.wt > b.wt) {
            return true;
        } else if (a.wt < b.wt) {
            return false;
        } else {
            return a.age < b.age;
        }
    }
}

bool ANW(const Person& a, const Person& b)
{
    if (a.age < b.age) {
        return true;
    } else if (a.age > b.age) {
        return false;
    } else {
        if (a.name < b.name) {
            return true;
        } else if (a.name > b.name) {
            return false;
        } else {
            return a.wt > b.wt;
        }
    }
}

bool AWN(const Person& a, const Person& b)
{
    if (a.age < b.age) {
        return true;
    } else if (a.age > b.age) {
        return false;
    } else {
        if (a.wt > b.wt) {
            return true;
        } else if (a.wt < b.wt) {
            return false;
        } else {
            return a.name < a.name;
        }
    }
}

bool WAN(const Person& a, const Person& b)
{
    if (a.wt > b.wt) {
        return true;
    } else if (a.wt < b.wt) {
        return false;
    } else {
        if (a.age < b.age) {
            return true;
        } else if (a.age > b.age) {
            return false;
        } else {
            return a.name < a.name;
        }
    }
}

bool WNA(const Person& a, const Person& b)
{
    if (a.wt > b.wt) {
        return true;
    } else if (a.wt < b.wt) {
        return false;
    } else {
        if (a.name < b.name) {
            return true;
        } else if (a.name > b.name) {
            return false;
        } else {
            return a.age < b.age;
        }
    }
}

class WhatSort {
    public:
        string sortType(vector <string> name, vector <int> age, vector <int> wt) {
            const int numPeople = name.size();
            vector<Person> people(numPeople);
            for (int i = 0; i < numPeople; i++) 
                people[i] = Person(name[i], age[i], wt[i]);

            const static int NUM_SORT_KINDS = 6;
            bool (*compFunc[NUM_SORT_KINDS])(const Person&, const Person&) = { 
                NAW, NWA, ANW, AWN, WAN, WNA };
            const string nameOfSorts[NUM_SORT_KINDS] = {
                "NAW", "NWA", "ANW", "AWN", "WAN", "WNA" };
            string answer = "NOT";
            for (int i = 0; i < NUM_SORT_KINDS; i++) {
                vector<Person> sorted(people);
                sort(sorted.begin(), sorted.end(), compFunc[i]);
                if (isSameOrder(sorted, people)) {
                    if (answer == "NOT") {
                        answer = nameOfSorts[i];
                    } else {
                        answer = "IND";
                        break;
                    }
                }
            }
            return answer;
        }
    private:
        bool isSameOrder(const vector<Person>& a, const vector<Person>& b) {
            for (int i = 0; i < a.size(); i++) {
                if (a[i] != b[i]) 
                    return false;
            }
            return true;
        }
};

PartySeats

| 19:16

問題文 PartySeats

席順決め。

class PartySeats {
    public:
        vector <string> seating (vector <string> attendees) {
            multiset<string> boys, girls;
            for (int i = 0; i < attendees.size(); i++) {
                string name, gender;
                istringstream iss(attendees[i]);
                iss >> name >> gender;
                if (gender[0] == 'b') boys.insert(name);
                else girls.insert(name);
            }
            vector<string> result;
            if (boys.size() != girls.size() || boys.size()%2 == 1)
                return result;
            multiset<string>::const_iterator bItr = boys.begin();
            multiset<string>::const_iterator gItr = girls.begin();
            result.push_back("HOST");
            for (int i = 0; i < attendees.size()/2; i += 2) {
                result.push_back(*gItr); gItr++;
                result.push_back(*bItr); bItr++;
            }
            result.push_back("HOSTESS");
            for (int i = attendees.size()/2; i < attendees.size(); i += 2) {
                result.push_back(*bItr); bItr++;
                result.push_back(*gItr); gItr++;
            }
            return result;
        }
};

Justifier

| 19:16

問題文

一番長い文字列に文字列の長さを合わせる。

class Justifier {
    public:
        vector <string> justify (vector <string> textIn) {
            int longest = INT_MIN;
            for (int i = 0; i < textIn.size(); i++)
                longest = max(longest, (int)textIn[i].length());
            vector <string> result(textIn.size());
            for (int i = 0; i < textIn.size(); i++)
                result[i] = string(longest-textIn[i].length(),' ') + textIn[i];
            return result;
        }
};

NathalieadsonNathalieadson2012/07/10 00:48Unparaellled accuracy, unequivocal clarity, and undeniable importance!

qumvofqumvof2012/07/10 15:55k9l8Kn <a href="http://ffbnrpylucxq.com/">ffbnrpylucxq</a>

kxvfpogrvtkxvfpogrvt2012/07/10 21:52DUrnSr , [url=http://odqnuvepnfcs.com/]odqnuvepnfcs[/url], [link=http://gllexsagvhok.com/]gllexsagvhok[/link], http://ctntvviqpnwt.com/

ahphkwegfjvahphkwegfjv2012/07/12 12:12jHPHB5 <a href="http://wujnvnxoozdt.com/">wujnvnxoozdt</a>