Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

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>