Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-10-14

OmahaLow

| 14:30

問題文, SRM 206

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

あるトランプゲームにおいて、最善の手を求める。

121.31/250 (cheated)

class OmahaLow {
public:
    string low(string sharedCards, string playersCards) {
        string ret = "";
        sort(sharedCards.rbegin(), sharedCards.rend());
        sort(playersCards.rbegin(), playersCards.rend());
        do {
            do {
                string s = sharedCards.substr(0,3) + playersCards.substr(0,2);
                sort(s.rbegin(), s.rend());
                if (s[0] >= '9') continue;
                int i;
                for (i = 0; i < 4; i++) if (s[i] == s[i+1]) break;
                if (i < 4) continue;
                if (ret == "" || s < ret) ret = s;
            } while (next_permutation(playersCards.rbegin(), playersCards.rend()));
        } while (next_permutation(sharedCards.rbegin(), sharedCards.rend()));
        return ret;
    }
};

2009-10-12

TopographicalImage

| 19:19

問題文, SRM 210

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

各頂上から上らずに到達することができる地点の数を数える。ただし、同じ地点は数えない。

390.67/1000

class TopographicalImage {
public:
    vector <int> calcPeakAreas(vector <string> topoData) {
        H = topoData.size();
        W = topoData[0].size();
        result.clear();
        while (true) {
            int mx=0, my=0;
            char mh=0;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (topoData[y][x] != VISITED && topoData[y][x] > mh) {
                        my = y;
                        mx = x;
                        mh = topoData[y][x];
                    }
                }
            if (mh == 0) break;
            result.push_back(0);
            visit(my, mx, mh, topoData);
        }
        return result;
    }
private:
    const static char VISITED = 127;
    int H, W;
    vector <int> result;
    void visit(const int py, const int px, const char ph, 
            vector<string>& topoData) {
        result.back()++;
        topoData[py][px] = VISITED;
        for (int dy = -1; dy <= 1; dy++)
            for (int dx = -1; dx <= 1; dx++) {
                if (dy == 0 && dx == 0) continue;
                const int ny = py + dy;
                const int nx = px + dx;
                if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                    const int nh = topoData[ny][nx];
                    if (nh <= ph)
                        visit(ny, nx, nh, topoData);
                }
            }
    }
};

2009-09-25

TeamPhoto

| 20:54

問題文, SRM 167

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

写真を撮る際に、身長の差の合計が最も小さくなるような並び方を考える。

232.95/750 (cheated)

class TeamPhoto {
public:
    int minDiff(vector <int> height) {
        n = height.size();
        vector<int> mem(height.begin()+3, height.end());
        sort(mem.begin(), mem.end());
        m = mem.size();

        int minSum = calc(height, mem, m/2);
        if (n%2 == 0)
            minSum = min(minSum, calc(height, mem, m/2+1));
        return minSum;
    }
private:
    int n, m;
    int calc(vector<int>& ht, vector<int>& mem, int mid) {
        return min(diff(ht[1], mem[0], mem[mid-1], ht[0]) +
                     diff(ht[0], mem[mid], mem[m-1], ht[2]),
                   diff(ht[2], mem[0], mem[mid-1], ht[0]) +
                     diff(ht[0], mem[mid], mem[m-1], ht[1]));
    }
    int diff(int a, int l, int h, int b) {
        return h-l + min(abs(a-l)+abs(b-h), abs(a-h)+abs(b-l));
    }
}

JohnieJohnie2013/02/16 22:15Check that off the list of things I was cofnsued about.

lpzworxlpzworx2013/02/17 21:13EhdvUV <a href="http://lggmfstpruis.com/">lggmfstpruis</a>

kdwdegjekdwdegje2013/02/18 05:09QCIf4X , [url=http://nxklzrjfqokk.com/]nxklzrjfqokk[/url], [link=http://iopulhzspqez.com/]iopulhzspqez[/link], http://vwnoyqhqksel.com/

kfuflfxdkfuflfxd2013/02/19 19:10JRh8jp , [url=http://ybazmifswqhs.com/]ybazmifswqhs[/url], [link=http://ceackqdzvvcl.com/]ceackqdzvvcl[/link], http://smwogahevohi.com/

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

2009-09-05

TallPeople

| 10:33

問題文, SRM 208

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

一番小さい人の中から一番大きい人を選び、一番大きい人の中から一番小さい人を選ぶ。

210.68/250

class TallPeople {
public:
    vector <int> getPeople(vector <string> people) {
        R = people.size();
        ppl = vector<vector<int> >(R);
        for (int i = 0; i < R; i++) {
            istringstream iss(people[i]);
            int t;
            while (iss >> t) ppl[i].push_back(t);
        }
        C = ppl[0].size();

        vector <int> result(2);
        result[0] = tallestOfShortest();
        result[1] = shortestOfTallest();
        return result;
    }
private:
    int R, C;
    vector<vector<int> > ppl;
    int tallestOfShortest() {
        int tallest = INT_MIN;
        for (int i = 0; i < R; i++)
            tallest = max(tallest, 
                    *min_element(ppl[i].begin(),ppl[i].end()));
        return tallest;
    }
    int shortestOfTallest() {
        int shortest = INT_MAX;
        for (int i = 0; i < C; i++) {
            int tallest = INT_MIN;
            for (int j = 0; j < R; j++)
                tallest = max(tallest, ppl[j][i]);
            shortest = min(shortest, tallest);
        }
        return shortest;
    }
};

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-08-08

BinaryCardinality

| 19:29

問題文

立っているビット数が少ない順にソート。300の問題よりこっちの方が解きやすかった。提出した後に気づいたことだけど、比較関数の中でbitsetを使えば、余計なvector配列を使う必要がないな。

453.99/500 - 00:09:18

bool compBinary(const bitset<32>& a, const bitset<32>& b)
{
    if (a.count() < b.count()) {
        return true;
    } else if (a.count() > b.count()) {
        return false;
    } else {
        return a.to_ulong() < b.to_ulong();
    }
}

class BinaryCardinality {
    public:
        vector <int> arrange(vector <int> numbers) {
            const int size = numbers.size();
            vector<bitset<32> > binaries(size);
            for (int i = 0; i < size; i++)
                binaries[i] = numbers[i];
            sort(binaries.begin(), binaries.end(), compBinary);
            vector <int> result(size);
            for (int i = 0; i < size; i++)
                result[i] = static_cast<int>(binaries[i].to_ulong());
            return result;
        }
};

ewnfzgewnfzg2011/02/28 00:358HHlV6 <a href="http://nfypkepkeych.com/">nfypkepkeych</a>, [url=http://azgnisbcmhab.com/]azgnisbcmhab[/url], [link=http://jedmlehhrowo.com/]jedmlehhrowo[/link], http://pqvizwthqdkq.com/

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>

2009-08-05

Pool

| 13:05

問題文

特定のボールの積み方にするには何回ボールを交換すればいいのかを求める。

class Pool {
    public:
        int rackMoves(vector <int> triangle) {
            const static int NUM_BALLS = 15;
            const static string PATTERN = "XOOX8XOXOXXOXOO";
            int ans = 0;
            if (triangle[4] != 8) {
                swap(triangle[4], *find(triangle.begin(),triangle.end(),8));
                ans++;
            }
            int a=0, b=0;
            for (int i = 0; i < NUM_BALLS; i++) {
                if (triangle[i] <= 7) {
                    if (PATTERN[i] == 'X') a++;
                    else                   b++;
                }
            }
            ans += min(a, b);
            return ans;
        }
};

2009-07-25

DiskSpace

| 05:47

問題文

使うハードディスクの数を最小限にする。

class DiskSpace {
public:
    int minDrives(vector <int> used, vector <int> total) {
        int totalUsed = accumulate(used.begin(),used.end(),0);
        sort(total.rbegin(), total.rend());
        for (int i = 0; i < total.size(); i++) {
            if (totalUsed <= total[i]) return i+1;
            else totalUsed -= total[i];
        }
        return total.size();
    }
};