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>

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

SMBus

| 12:55

問題文

バスの調停のシミュレーション。

class SMBus {
    public:
        int transmitTime(vector <string> messages, vector <int> times) {
            const int size = messages.size();
            vector<bool> transmitted(size, false);
            int totalTime = 0;
            for (int i = 0; i < size; i++) {
                list<int> candidates;
                for (int j = 0; j < size; j++) {
                    if (!transmitted[j]) candidates.push_back(j);
                }
                int idx = 0;
                while (candidates.size() > 1) {
                    int slowest = INT_MIN;
                    char smallest = '9'+1;
                    for (list<int>::const_iterator itr = candidates.begin(); 
                            itr != candidates.end(); itr++) {
                        if (messages[*itr].length() > idx) {
                            slowest = max(slowest, times[*itr]);
                            smallest = min(smallest, messages[*itr][idx]);
                        }
                    }
                    for (list<int>::iterator itr = candidates.begin();
                            itr != candidates.end(); ) {
                        if (messages[*itr][idx] > smallest) {
                            itr = candidates.erase(itr);
                        } else {
                            itr++;
                        }
                    }
                    totalTime += slowest;
                    idx++;
                }
                const int winner = *candidates.begin();
                totalTime += (messages[winner].length()-idx) * times[winner];
                transmitted[winner] = true;
            }

            return totalTime;
        }
};

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/

2009-08-01

Quilting

| 11:24

問題文

キルト作り。自力で解けたが、解くのに一時間以上かかった。

class Quilting {
    public:
        string lastPatch(int length, int width, vector <string> colorList) {
            vector<vector<string> > quilt(200,vector<string>(200,string(".")));
            map<string,int> prevCount;
            int y=100, x=100, dir=0;
            quilt[y][x] = colorList[0];
            prevCount[colorList[0]]++;
            for (int i = 1; i < length*width; i++) {
                const static int NEIGHBORS = 8;
                const static int nd[NEIGHBORS][2] = {
                    {-1,-1}, {-1, 0}, {-1, 1},
                    { 0,-1},          { 0, 1},
                    { 1,-1}, { 1, 0}, { 1, 1} };
                const static int MOVE_KINDS = 4;
                const static int mvd[MOVE_KINDS][4] = {
                    {-1, 0, 0,-1}, { 0,-1, 1, 0},
                    { 1, 0, 0, 1}, { 0, 1,-1, 0} };
                y += mvd[dir][0];
                x += mvd[dir][1];
                map<string,int> neighorCount;
                for (int j = 0; j < NEIGHBORS; j++) {
                    const int dy = y + nd[j][0];
                    const int dx = x + nd[j][1];
                    if (quilt[dy][dx] != ".") {
                        neighorCount[quilt[dy][dx]]++;
                    }
                }
                string color;
                int minSameColor = INT_MAX;
                if (neighorCount.size() == colorList.size()) {
                    for (map<string,int>::const_iterator itr = neighorCount.begin();
                            itr != neighorCount.end(); itr++) {
                        if (itr->second < minSameColor) {
                            color = itr->first;
                            minSameColor = itr->second;
                        } else if (itr->second == minSameColor) {
                            if (prevCount[itr->first] < prevCount[color]) {
                                color = itr->first;
                            } else if (prevCount[itr->first] == prevCount[color]) {
                                if (find(colorList.begin(),colorList.end(),itr->first) 
                                        < find(colorList.begin(),colorList.end(),color)) {
                                    color = itr->first;
                                }
                            }
                        }
                    }
                } else {
                    for (int j = 0; j < colorList.size(); j++) {
                        if (neighorCount.find(colorList[j]) == neighorCount.end()) {
                            if (prevCount[colorList[j]] < minSameColor) {
                                minSameColor = prevCount[colorList[j]];
                                color = colorList[j];
                            }
                        }
                    }
                }
                quilt[y][x] = color;
                prevCount[color]++;
                if (quilt[y+mvd[dir][2]][x+mvd[dir][3]] == ".") {
                    dir = (dir+1) % MOVE_KINDS;
                }
            }
            return quilt[y][x];
        }
};

2009-07-28

ThePriceIsRight

| 08:46

問題文

Longest increasing sub sequence を求める問題。再帰を使って解く方法は思いついたが、それでは計算量が問題になるとわかり、結局やはりEditorialを見た。dynamic programming による方法で解ける。

class ThePriceIsRight {
public:
    vector <int> howManyReveals(vector <int> prices) {
        const int size = prices.size();
        vector<int> S(size,0), L(size,0);
        vector <int> result(2,0);
        for (int i = 0; i < size; i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                if (prices[j] < prices[i]) 
                    tmp = max(tmp, S[j]);
            }
            for (int j = 0; j < i; j++) {
                if (S[j] == tmp && prices[j] < prices[i])
                    L[i] += L[j];
            }
            if (L[i] == 0) L[i] = 1;
            S[i] = 1 + tmp;
        }
        result[0] = *max_element(S.begin(), S.end());
        for (int i = 0; i < size; i++) {
            if (S[i] == result[0])
                result[1] += L[i];
        }
        return result;
    }
};

2009-07-26

Gems

| 19:52

ボード中の2つの隣接する宝石を入れ替えた時に、3つ以上宝石が並ぶかどうか。自力で解けると思って実装したが、重複して数えてしまってうまくいかず、結局Editorialを見た。

class Gems {
public:
    int numMoves(vector <string> board) {
        int moves = 0;
        const static int d[DIR_KINDS][2] = {
            { 0, 1}, { 1, 0}, { 0,-1}, {-1, 0} };
        const int h=board.size(), w=board[0].length();
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                const char gem = board[y][x];
                for (int i = 0; i < DIR_KINDS/2; i++) {
                    const int dy = y + d[i][0];
                    const int dx = x + d[i][1];
                    if (!isInRage(dy,dx,h,w)) continue;
                    if (gem == board[dy][dx]) continue;
                    if (isAligned(gem,dy,dx,i,board,h,w) ||
                      isAligned(board[dy][dx],y,x,i+DIR_KINDS/2,board,h,w)) {
                        moves++;
                    }
                }
            }
        }
        return moves;
    }
private:
    const static int DIR_KINDS = 4;
    bool isInRage(const int y, const int x, const int h, const int w) {
        return 0<=y&&y<h && 0<=x&&x<w;
    }
    bool isAligned(const char gem, const int dy, const int dx, const int dir,
              const vector<string>& board, const int h, const int w) {
        const static int CHECK_KINDS = 4;
        const static int check[DIR_KINDS][CHECK_KINDS][2][2] = {
            { {{-1, 0},{ 1, 0}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}} },
            { {{-1, 0},{ 1, 0}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}} } };
        for (int j = 0; j < CHECK_KINDS; j++) {
            for (int k = 0; k < 2; k++) {
                const int cy = dy + check[dir][j][k][0];
                const int cx = dx + check[dir][j][k][1];
                if (!isInRage(cy,cx,h,w)) break;
                if (gem != board[cy][cx]) break;
                if (k == 2-1) return true;
            }
        }
        return false;
    }
};

HourGlass

| 11:16

問題文

2つの砂時計を使って測れる時間を求める。Brute-forceで解ける問題だけど、どういう状態を調べれば解けるのかがわからなかった。慣れるしかないか。

class HourGlass {
public:
    vector <int> measurable(int glass1, int glass2) {
        g1 = glass1;
        g2 = glass2;
        times.clear();
        memo = vector<vector<vector<bool> > >(MAX_POSSIBLE_TIME+1, 
                vector<vector<bool> >(g1+1, vector<bool>(g2+1,false)));
        go(0, 0, 0);
        const static int RETURN_VALUES = 10;
        vector <int> result(RETURN_VALUES);
        set<int>::const_iterator itr = times.begin();
        for (int i = 0; i < RETURN_VALUES; i++) {
            itr++;
            result[i] = *itr;
        }
        return result;
    }
private:
    set<int> times;
    int g1, g2;
    const static int MAX_POSSIBLE_TIME = 500;
    vector<vector<vector<bool> > > memo;
    void go(const int sand1, const int sand2, const int time) {
        if (time > MAX_POSSIBLE_TIME) return;
        if (memo[time][sand1][sand2]) return;
        memo[time][sand1][sand2] = true;
        times.insert(time);
        if (sand1==0 || sand2==0) {
            go(g1-sand1, sand2, time);
            go(sand1, g2-sand2, time);
            go(g1-sand1, g2-sand2, time);
        }
        if (sand1>0 && sand2==0) go(0, 0, time+sand1);
        if (sand2>0 && sand1==0) go(0, 0, time+sand2);
        if (sand1>0 && sand2>0) {
            int minSand = min(sand1, sand2);
            go(sand1-minSand, sand2-minSand, time+minSand);
        }
    }
};

2009-07-25

WordParts

| 09:31

問題文

問題文が短く、問題の意味は理解できたが、解法が思いつかず、Editorialを見た。メモ化か。慣れない。

class WordParts {
public:
    int partCount(string original, string compound) {
        const int ori_len = original.length();
        len = compound.length();
        dict.clear();
        dict.insert(original);
        for (int i = 1; i < ori_len; i++) {
            dict.insert(original.substr(0,ori_len-i));
            dict.insert(original.substr(ori_len-i));
        }
        memo = vector<int>(len, -1);
        const int parts = minParts(compound, 0);
        if (parts >= INFTY) return -1;
        else return parts;
    }
private:
    int len;
    set<string> dict;
    vector<int> memo;
    const static int INFTY = INT_MAX/2;
    int minParts(const string& compound, const int pos) {
        if (pos == len) return 0;
        if (memo[pos] != -1) return memo[pos];
        memo[pos] = INFTY;
        for (set<string>::const_iterator w = dict.begin();
                    w != dict.end(); w++) {
            const int w_len = (*w).length();
            if (*w == compound.substr(pos, w_len))
                memo[pos] = min(memo[pos], 1+minParts(compound,pos+w_len));
        }
        return memo[pos];
    }
};

2009-07-24

PaternityTest

| 08:29

問題文

子が母と父両方から半分ずつ遺伝情報を受けついでいるかを調べる。初めは母と子が半分一致するパターンを全パターン作るという、最悪の場合で計算量が2^20となる実装を行って提出するも、timeoutされた。それで結局、Editorialを見た。両方にマッチしなかったら除外してよいという事実には気付けなかった。

class PaternityTest {
public:
    vector <int> possibleFathers(string child, string mother, vector <string> men) {
        vector <int> result;
        for (int i = 0; i < men.size(); i++) {
            if (isFather(child, mother, men[i]))
                result.push_back(i);
        }
        return result;
    }
private:
    bool isFather(const string& child, const string& mother,
                  const string& man) {
        const int len = child.length();
        int matches = 0;
        for (int i = 0; i < len; i++) {
            if (child[i] == man[i]) matches++;
            else if (child[i] != mother[i]) return false;
        }
        return matches >= len/2;
    }
};

2009-07-23

ContestScore

| 07:50

問題文

合計ランクと合計スコアを計算して、結果をソートする。

bool compGroup(const string& a, const string& b)
{
    string aName, bName;
    int aRank, bRank;
    double aScore, bScore;
    istringstream isa(a), isb(b);
    isa >> aName >> aRank >> aScore;
    isb >> bName >> bRank >> bScore;
    if (aRank < bRank) {
        return true;
    } else if (aRank > bRank) {
        return false;
    } else {
        if (aScore > bScore) {
            return true;
        } else if (aScore < bScore) {
            return false;
        } else {
            return aName < bName;
        }
    }
}

class ContestScore {
public:
    vector <string> sortResults(vector <string> data) {
        const int numGroups = data.size();
        vector<vector<double> > scores(numGroups);
        vector<string> names(numGroups);
        vector<double> totalScores(numGroups);
        for (int i = 0; i < numGroups; i++) {
            istringstream iss(data[i]);
            iss >> names[i];
            double score;
            while (iss >> score) scores[i].push_back(score);
            totalScores[i] = accumulate(scores[i].begin(),scores[i].end(),0.0l);
        }

        int numScores = scores[0].size();
        vector<int> totalRanks(numGroups);
        for (int i = 0; i < numScores; i++) {
            double pre = 100.0;
            for (int rank = 1; rank <= numGroups; ) {
                double maxScore = -1.0;
                for (int j = 0; j < numGroups; j++) {
                    if (scores[j][i] < pre && scores[j][i] > maxScore) {
                        maxScore = scores[j][i];
                    }
                }
                int sameScores = 0;
                for (int j = 0; j < numGroups; j++) {
                    if (scores[j][i] == maxScore) {
                        totalRanks[j] += rank;
                        sameScores++;
                    }
                }
                rank += sameScores;
                pre = maxScore;
            }
        }

        vector<string> result(numGroups);
        for (int i = 0; i < numGroups; i++) {
            ostringstream oss;
            oss.setf(ios_base::fixed);
            oss.precision(1);
            oss << names[i] << " " << totalRanks[i] << " " << totalScores[i];
            result[i] = oss.str();
        }
        sort(result.begin(), result.end(), compGroup);
        return result;
    }
};