Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-13

Lottery

| 15:42

問題文

DIV1の問題を解き始めることにした。この問題から、1問につき1エントリを書く。過去のエントリも近いうちに1問1エントリに変える。

数字を使ったギャンブルで、勝率が高い順に並べる。組み合わせの問題で、解けそうと思いコードを書き始めたが、結局わからなくなり、Editorialを見た。

181.27 / 500 - 01:53:07

bool compValidTicketsNum(const pair<string,long long>& a,
        const pair<string,long long>& b) {
    if (a.second < b.second) {
        return true;
    } else if (a.second > b.second) {
        return false;
    } else {
        return a.first < b.first;
    }
}

class Lottery {
    public:
        vector <string> sortByOdds(vector <string> rules) {
            const int size = rules.size();
            vector <string> result(size);
            if (size == 0) return result;
            vector <pair<string,long long> > name(size);
            vector<int> choices(size), blanks(size);
            for (int i = 0; i < size; i++) {
                int p = find(rules[i].begin(),rules[i].end(),':') - rules[i].begin();
                name[i].first = rules[i].substr(0, p);
                istringstream iss(rules[i].substr(p+1));
                int choices, blanks;
                string sorted, unique;
                iss >> choices >> blanks >> sorted >> unique;
                if (sorted == "F" && unique == "F") {
                    name[i].second = power(choices, blanks);
                } else if (sorted == "T" && unique == "F") {
                    name[i].second = combination(choices+blanks-1, blanks);
                } else if (sorted == "F" && unique == "T") {
                    name[i].second = combination(choices, blanks) * factorial(blanks);
                } else if (sorted == "T" && unique == "T") {
                    name[i].second = combination(choices, blanks);
                }
            }
            stable_sort(name.begin(), name.end(), compValidTicketsNum);
            for (int i = 0; i < size; i++)
                result[i] = name[i].first;
            return result;
        }
    private:
        long long power(const long long x, long long y) {
            long long ret = 1;
            while (y-- > 0) ret *= x;
            return ret;
        }
        long long factorial(long long x) {
            long long ret = 1;
            while (x > 0) {
                ret *= x;
                x--;
            }
            return ret;
        }
        long long combination(long long x, long long y) {
            long long ret = 1;
            for (int i = 0; i < y; i++) {
                ret *= x;
                x--;
            }
            while (y > 1) {
                ret /= y;
                y--;
            }
            return ret;
        }
};

2009-08-12

RecurrenceRelation

| 12:51

問題文

与えられた漸化式のN番目の値を求める。システムテストで1回落とされた。

298.29/500 - 00:20:58

class RecurrenceRelation {
    public:
        int moduloTen(vector <int> coefficients, vector <int> initial, int N) {
            const int k = coefficients.size();
            for (int i = 0; i < k; i++) 
                initial[i] = myMod(initial[i]);
            cout << endl;
            for (int i = k; i <= N; i++) {
                int x = 0;
                for (int j = i-1; j >= i-k; j--) 
                    x += coefficients[k-(i-j)] * initial[j];
                cout << i << " " << x << endl;
                x = myMod(x);
                initial.push_back(x);
            }
            return initial[N];
        }
    private:
        int myMod(const int x) {
            if (x >= 0) return x % 10;
            else return (10 - ((-x)%10)) % 10;
        }
};

JusticeJustice2011/07/09 15:18Created the greatest artclies, you have.

dhumgkuquyrdhumgkuquyr2011/07/10 00:44RBBBkV <a href="http://hjbppmyhkpug.com/">hjbppmyhkpug</a>

oipwdeoipwde2011/07/11 20:03vO7rh7 <a href="http://ampmjgepjkgf.com/">ampmjgepjkgf</a>

2009-08-11

FairWorkload

| 13:17

問題文

仕事をなるべく均等になるように割り振る。良問。Level-2の問題より解きやすかった。

532.87/1000 - 00:32:37

class FairWorkload {
    public:
        int getMostWork(vector <int> folders, int workers) {
            amounts = vector<int>(workers, 0);
            maxOptimalAmount = INT_MAX;
            go(folders, 0, workers, 0);
            return maxOptimalAmount;
        }
    private:
        int maxOptimalAmount;
        vector<int> amounts;
        void go(const vector<int>& folders, const int f_id, 
                const int workers, const int w_id) {
            if (f_id == folders.size()) {
                for (int i = 0; i < workers; i++)
                    if (amounts[i] == 0)
                        return;
                maxOptimalAmount = min(maxOptimalAmount, 
                        *max_element(amounts.begin(),amounts.end()));
                return;
            }
            if (maxOptimalAmount <= amounts[w_id]) return;
            if (w_id == workers) return;
            amounts[w_id] += folders[f_id];
            go(folders, f_id+1, workers, w_id);
            amounts[w_id] -= folders[f_id];
            if (w_id+1 == workers) return;
            amounts[w_id+1] += folders[f_id];
            go(folders, f_id+1, workers, w_id+1);
            amounts[w_id+1] -= folders[f_id];
        }
};

OliviaOlivia2011/07/09 22:49Ppl like you get all the birans. I just get to say thanks for he answer.

cganpmvkaacganpmvkaa2011/07/10 00:21ozUmeq <a href="http://pjfcqeeeqmnr.com/">pjfcqeeeqmnr</a>

gkbfwfvcbgkbfwfvcb2011/07/10 21:09Bo1aDa , [url=http://xrkdnugczyzj.com/]xrkdnugczyzj[/url], [link=http://sbngsfqxhlpy.com/]sbngsfqxhlpy[/link], http://safjlfwoassi.com/

uxpnpunauxpnpuna2011/07/11 20:32crHIwv <a href="http://fodsgqzsvyim.com/">fodsgqzsvyim</a>

mhhaaumhhaau2011/07/12 21:58da56vU , [url=http://tqvvgrxdnlwt.com/]tqvvgrxdnlwt[/url], [link=http://ofcuaexemicz.com/]ofcuaexemicz[/link], http://shzifphpejdh.com/

2009-08-10

NumberGuesser

| 19:34

問題文

数字を推測。自力で解けなかった。総当たりで解いたが、数学的な解法もある。

190.54/500 - 01:06:07 (cheated)

class NumberGuesser {
    public:
        int guess(string leftOver) {
            int candidate = 0;
            for (int d = 1; d <= 9; d++) {
                int found = 0;
                for (int i = 0; i < 4; i++) {
                    ostringstream oss;
                    oss << leftOver.substr(0,i) << d << leftOver.substr(i);
                    int z;
                    istringstream(oss.str()) >> z;
                    for (int x = 1; x+z <= 9998; x++) {
                        int y = x + z;
                        if (isDigitMatch(x, y)) {
                            candidate = d;
                            found++;
                            break;
                        }
                    }
                }
                if (found == 4) return d;
            }
            return candidate;
        }
    private:
        bool isDigitMatch(int x, int y) {
            vector<int> ndigits(10, 0);
            while (x > 0) {
                if (x%10 != 0) ndigits[x%10]++;
                x /= 10;
            }
            while (y > 0) {
                if (y%10 != 0) ndigits[y%10]--;
                y /= 10;
            }
            for (int i = 0; i < ndigits.size(); i++) {
                if (ndigits[i] != 0)
                    return false;
            }
            return true;
        }
};

2009-08-08

Animation

| 19:40

問題文

粒子の動き。強引に解きすぎて、バグが増え、時間がかかった。

150.00/500 - 00:57:22

class Animation {
    public:
        vector <string> animate(int speed, string init) {
            const int len = init.length();
            const static char RIGHT = '1';
            const static char LEFT = '2';
            string pre(init);
            for (int i = 0; i < len; i++) {
                if (pre[i] == 'R') pre[i] = RIGHT;
                else if (pre[i] == 'L') pre[i] = LEFT;
                else pre[i] = 0;
            }
            vector <string> result;
            while (true) {
                string s(toX(pre));
                result.push_back(s);
                if (find(s.begin(),s.end(),'X') == s.end())
                    break;
                s = string(len, 0);
                for (int i = 0; i < len; i++) {
                    int d;
                    switch (pre[i]) {
                    case RIGHT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        break;
                    case LEFT:
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    case RIGHT+LEFT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    }
                }
                pre = s;
            }
            return result;
        }
    private:
        string toX(const string& s) {
            string ret(s.length(), '.');
            for (int i = 0; i < s.length(); i++)
                if (s[i] != 0)
                    ret[i] = 'X';
            return ret;
        }
};

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

ParallelSpeedup

| 19:21

問題文

何基のコンピュータを使って、並列処理させた場合が一番速いのかを求める。

388.73/500 - 00:16:33

class ParallelSpeedup {
    public:
        int numProcessors(int k, int overhead) {
            long long minTime = k;
            for (int p = 2; p <= k; p++) {
                const long long time = overhead*calcCommCount(p) 
                    + static_cast<long long>(ceil(static_cast<double>(k)/p));
                if (time >= minTime) 
                    return p-1;
                minTime = time;
            }
            return k;
        }
    private:
        long long calcCommCount(const int p) {
            return static_cast<long long>(p) * (p-1) / 2;
        }
};

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

PaperFold

| 18:43

問題文

8回以下の回数だけ紙を折ることで、箱にその紙を納められるか。

class PaperFold {
    public:
        int numFolds(vector <int> paper, vector <int> box) {
            box.push_back(0);
            queue<vector<int> > Q;
            Q.push(box);
            while (!Q.empty()) {
                vector<int> b = Q.front(); Q.pop();
                if (b[2] > 8) continue;
                if (isFit(paper, b)) return b[2];
                b[2]++;
                b[0] *= 2; Q.push(b);
                b[0] /= 2; b[1] *= 2; Q.push(b);
            }
            return -1;
        }
    private:
        bool isFit(const vector<int>& paper, const vector<int>& box) {
            return (paper[0] <= box[0] && paper[1] <= box[1]) ||
                (paper[0] <= box[1] && paper[1] <= box[0]);
        }
};

2009-08-03

TennisRallies

| 13:00

このDIV2の問題セットは、初めて時間内に全問を解くことができた。合計1255.1点で、overviewによると部門2位に当たる成績。

問題文

禁止されたショットの連続を含まないラリーを何種類作れるか。最悪のケースが2の18乗(=262144)なので、Brute-forceな方法でも終わる。

class TennisRallies {
    public:
        int howMany(int numLength, vector <string> forbidden, int allowed) {
            count = 0;
            string raly(numLength, ' ');
            go(raly, 0, 0, numLength, forbidden, allowed);
            return count;
        }
    private:
        int count;
        void go(string& raly, int p, int fCount, const int numLength,
                const vector<string>& forbidden, const int allowed) {
            for (int i = 0; i < forbidden.size(); i++) {
                const int fLen = forbidden[i].length();
                if (p >= fLen && raly.substr(p-fLen,fLen) == forbidden[i])
                    fCount++;
            }
            if (fCount >= allowed) return;
            if (p == numLength) {
                count++;
                return;
            }
            raly[p] = 'c';
            go(raly, p+1, fCount, numLength, forbidden, allowed);
            raly[p] = 'd';
            go(raly, p+1, fCount, numLength, forbidden, allowed);
        }
};

DennysDennys2012/07/10 08:54There's a trefriic amount of knowledge in this article!

ptkxkwfiufxptkxkwfiufx2012/07/11 08:32rW3Q5y <a href="http://lvoddmvsamev.com/">lvoddmvsamev</a>

ssurmbuvpsmssurmbuvpsm2012/07/11 21:20GnFEME , [url=http://jcvsaeuskkgr.com/]jcvsaeuskkgr[/url], [link=http://iseogblgtggc.com/]iseogblgtggc[/link], http://nsaattulsfhk.com/

xtmpsysmfgnxtmpsysmfgn2012/07/12 13:058VKorp <a href="http://qspzckisagzz.com/">qspzckisagzz</a>

ueblizedjueblizedj2012/07/12 18:376GmZzo , [url=http://rtmucgtfbosq.com/]rtmucgtfbosq[/url], [link=http://dzmpwnhervlx.com/]dzmpwnhervlx[/link], http://trmherritlub.com/