Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

InstantRunoff

| 17:56

問題文, SRM 175

選挙で、誰が過半数の票を獲得するか。

166.88/550 (1 failed)

class InstantRunoff {
public:
    string outcome(string candidates, vector <string> ballots) {
        const int numCandidates = candidates.size();
        const int numVoters = ballots.size();
        vector<int> idx(numVoters, 0);
        vector<char> failed;
        for (int i = 0; i < numCandidates; ) {
            map<char,int> votes;
            for (int k = 0; k < numCandidates; k++) 
                if (find(failed.begin(),failed.end(),candidates[k]) == failed.end())
                    votes[candidates[k]] = 0;
            for (int j = 0; j < numVoters; j++) {
                while (votes.find(ballots[j][idx[j]]) == votes.end()) idx[j]++;
                votes[ballots[j][idx[j]]]++;
            }
            int minimum = INT_MAX;
            for (map<char,int>::const_iterator v = votes.begin();
                    v != votes.end(); v++) {
                if (v->second > numVoters/2)
                    return string(1,v->first);
                if (v->second < minimum)
                    minimum = v->second;
            }
            for (map<char,int>::const_iterator v = votes.begin();
                    v != votes.end(); v++) {
                if (v->second == minimum) {
                    failed.push_back(v->first);
                    i++;
                    for (int j = 0; j < numVoters; j++) {
                        if (v->first == ballots[j][idx[j]])
                            idx[j]++;
                    }
                }
            }
        }
        return "";
    }
};

Matching

| 16:40

問題文, SRM 176

全て同じか、全て違う。

347.03/500

const static string memory[4][3] = {
    { "CIRCLE", "DIAMOND", "SQUIGGLE" },
    { "BLUE", "GREEN", "RED" },
    { "EMPTY", "SOLID", "STRIPED" },
    { "ONE", "THREE", "TWO" } };
    
class Matching {
public:
    vector <string> findMatch(vector <string> first, vector <string> second) {
        vector<string> third(4);
        for (int i = 0; i < 4; i++) 
            third[i] = getSymbol(first[i], second[i], i);
        return third;
    }
private:
    string getSymbol(string f, string s, const int kind) {
        if (f == s) return f;
        if (f > s) swap(f, s);
        if (f == memory[kind][0]) {
            if (s == memory[kind][1]) return memory[kind][2];
            else return memory[kind][1];
        } else {
            return memory[kind][0];
        }
    }
};

BadClock

| 15:23

問題文, SRM 172

何時間後に2つの時計が同時刻を指すか。

class BadClock {
public:
    double nextAgreement(string trueTime, string skewTime, int hourlyGain) {
        int X = getTime(trueTime);
        int Y = getTime(skewTime);
        if (hourlyGain < 0) {
            hourlyGain = -hourlyGain;
            swap(X, Y);
        }
        while (X < Y) X += 12*60*60;
        return (double) (X - Y) / hourlyGain;
    }
private:
    int getTime(const string& time) {
        int hh, mm, ss;
        sscanf(time.c_str(), "%d:%d:%d", &hh, &mm, &ss);
        return (hh*60 + mm)*60 + ss;
    }
};

MineField

| 11:43

問題文, SRM 169

マインスイーパ。

225.69/250

class MineField {
public:
    vector <string> getMineField(string mineLocations) {
        const static int SIZE = 9;
        vector <string> result(SIZE,string(SIZE,'0'));
        istringstream iss(mineLocations);
        char pad;
        int y, x;
        while (iss >> pad >> y >> pad >> x >> pad)
            result[y][x] = 'M';
        const static int d[8][2] = {
            {-1,-1}, {-1, 0}, {-1, 1},
            { 0,-1},          { 0, 1},
            { 1,-1}, { 1, 0}, { 1, 1} };
        for (y = 0; y < SIZE; y++)
            for (x = 0; x < SIZE; x++) {
                if (result[y][x] == 'M') continue;
                int counter = 0;
                for (int i = 0; i < 8; i++) {
                    int dy = y + d[i][0];
                    int dx = x + d[i][1];
                    if (0<=dy&&dy<SIZE && 0<=dx&&dx<SIZE 
                            && result[dy][dx] == 'M')
                        counter++;
                }
                result[y][x] += counter;
            }
        return result;
    }
};

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

Rochambo

| 17:09

問題文, SRM 163

じゃんけんの勝数。

157.83/250

class Rochambo {
public:
    int wins(string opponent) {
        int counter = 0;
        for (int i = 0; i < 2 && i < opponent.size(); i++)
            if (isWin('R', opponent[i]))
                counter++;
        for (int i = 2; i < opponent.size(); i++) {
            string pre2 = opponent.substr(i-2, 2);
            char move;
            if (pre2 == "RR") move = 'P';
            else if (pre2 == "SS") move = 'R';
            else if (pre2 == "PP") move = 'S';
            else if (pre2.find("R") == string::npos) move = 'P';
            else if (pre2.find("S") == string::npos) move = 'R';
            else move = 'S';
            if (isWin(move, opponent[i]))
                counter++;
        }
        return counter;
    }
private:
    bool isWin(const char a, const char b) {
        return (a=='R'&&b=='S') || (a=='S'&&b=='P') || (a=='P'&&b=='R');
    }
};

IsHomomorphism

| 16:05

問題文, SRM 161

同じ答えを返すかどうかを調べる。問題の意味がわかりにくいが、わかれば簡単な問題。

196.13/300

class IsHomomorphism {
public:
    vector <string> numBad(vector <string> source, vector <string> target, vector <int> mapping) {
        vector <string> result;
        for (int i = 0; i < source.size(); i++) {
            for (int j = 0; j < source[0].size(); j++) {
                if (mapping[source[i][j]-'0'] != target[mapping[i]][mapping[j]]-'0') {
                    ostringstream oss;
                    oss << "(" << i << "," << j << ")";
                    result.push_back(oss.str());
                }
            }
        }
        return result;
    }
};

Iditarod

| 10:30

問題文, SRM 160

所要時間の平均を求める。

212.31/250

class Iditarod {
public:
    int avgMinutes(vector <string> times) {
        int total = 0;
        for (int i = 0; i < times.size(); i++)
            total += getTime(times[i]);
        return (int)((double) total / times.size() + 0.5);
    }
private:
    int getTime(string& time) {
        int hh, mm, n;
        char apm;
        sscanf(time.c_str(), "%d:%d %cM, DAY %d", &hh, &mm, &apm, &n);
        if (hh == 12) hh = 0;
        if (apm == 'P') hh += 12;
        return 24*(n-1)*60 + hh*60 + mm - 8*60;
    }
};

2009-08-27

FryingHamburgers

| 11:29

問題文, SRM 159

すべてのハンバーガーを焼くのにかかる時間。解けなくて、さんざん悩んで、Editorialを見て、数学の問題だと気づいた。

75.0/250

class FryingHamburgers {
public:
    int howLong(int panSize, int hamburgers) {
        if (hamburgers == 0) return 0;
        if (hamburgers <= panSize) return 10;
        return 5*(int)ceil(2.0*hamburgers/panSize);
    }
};

2009-08-23

CheatCode

| 11:08

問題文, SRM 154

どの裏技コードを入力したかを判定。1回目に出したときは、しょうもないバグがあり、落とされた。

152.30/350

class CheatCode {
public:
    vector <int> matches(string keyPresses, vector <string> codes) {
        vector <int> result;
        const int keyLen = keyPresses.length();
        for (int i = 0; i < codes.size(); i++) {
            const int codeLen = codes[i].length();
            for (int j = 0; j < keyLen; j++) {
                if (codes[i][0] != keyPresses[j]) continue;
                int idx = 1;
                for (int k = j+1; idx < codeLen && k < keyLen; k++) {
                    if (codes[i][idx] == keyPresses[k])
                        idx++;
                    else if (keyPresses[k] != codes[i][idx-1])
                        break;
                }
                if (idx == codeLen) {
                    result.push_back(i);
                    break;
                }
            }
        }
        return result;
    }
};

2009-08-22

BirthdayOdds

| 16:29

問題文, SRM 174

同じ誕生日になる確率。

467.33/500

class BirthdayOdds {
public:
    int minPeople(int minOdds, int daysInYear) {
        double p = 1;
        for (int i = 1; i <= daysInYear; i++) {
            p *= static_cast<double>(daysInYear-i+1)/daysInYear;
            if ((1-p)*100 >= minOdds)
                return i;
        }
        return 0;
    }
};

2009-08-21

WordForm

| 17:15

問題文, SRM 173

与えられた文字列は、どのような母音と子音の組み合わせから成るのか。

468.65/500

class WordForm {
public:
    string getSequence(string word) {
        string sequence;
        bool isPreVowel = false;
        for (int i = 0; i < word.length(); i++) {
            const char c = toupper(word[i]);
            bool isVowel = (i!=0 && !isPreVowel && c=='Y') ||
                c=='A' || c=='E' || c=='I' || c=='O' || c=='U';
            if (i == 0 || isVowel != isPreVowel) {
                if (isVowel) sequence += "V";
                else sequence += "C";
                isPreVowel = isVowel;
            }
        }
        return sequence;
    }
};

2009-08-19

Archimedes

| 11:09

問題文, SRM 151

円周率の近似値を求める。どうすれば求められるのかは、すぐに分かった。

230.08/250

class Archimedes {
    public:
        double approximatePi(int numSides) {
            return numSides * sin(M_PI/numSides);
        }
};

RenaRena2011/07/22 11:40Articles like this really grease the shftas of knowledge.

mtosqkksxfnmtosqkksxfn2011/07/22 18:19nGge95 <a href="http://htbsbsjhateo.com/">htbsbsjhateo</a>

vouvotvouvot2011/07/24 22:10AbhEFB <a href="http://udtjnaqmvoon.com/">udtjnaqmvoon</a>

lraetvllraetvl2011/07/25 02:03Ueilew , [url=http://ofkchvqjbqph.com/]ofkchvqjbqph[/url], [link=http://mhzhqovckhxx.com/]mhzhqovckhxx[/link], http://kgxfqnawhoqk.com/

2009-08-18

CrossCountry

| 11:38

問題文, SRM 171

クロスカントリーの団体戦の順位決め。強引に解いた。

434.52/600

struct Team {
    char id;
    vector<int> ranks;
    int sum;
    Team() {}
    Team(const char id) : id(id), sum(0) {}
    void addMember(const int rank) {
        ranks.push_back(rank);
        if (ranks.size() <= 5)
            sum += rank;
    }
};

bool compTeam(const Team& a, const Team& b) {
    if (a.sum < b.sum) {
        return true;
    } else if (a.sum > b.sum) {
        return false;
    } else {
        if (a.ranks.size() >= 6 && b.ranks.size() >= 6) {
            return a.ranks[5] < b.ranks[5];
        } else if (a.ranks.size() >= 6) {
            return true;
        } else if (b.ranks.size() >= 6) {
            return false;
        } else {
            return a.id < b.id;
        }
    }
}

class CrossCountry {
    public:
        string scoreMeet(int numTeams, string finishOrder) {
            vector<Team> teams;
            for (int i = 0; i < finishOrder.size(); i++) {
                for (int j = 0; j < teams.size()+1; j++) {
                    if (j == teams.size()) {
                        teams.push_back(Team(finishOrder[i]));
                        teams.back().addMember(i+1);
                        break;
                    }
                    if (teams[j].id == finishOrder[i]) {
                        teams[j].addMember(i+1);
                        break;
                    } 
                }
            }
            sort(teams.begin(), teams.end(), compTeam);
            string result;
            for (int i = 0; i < teams.size(); i++) 
                if (teams[i].ranks.size() >= 5)
                    result += string(1, teams[i].id);
            return result;
        }
};

TravonTravon2011/07/22 13:02Thanky Thanky for all this good ifnomratoin!

gupcpicgupcpic2011/07/22 22:31kmdB9M <a href="http://cevhxxxwszda.com/">cevhxxxwszda</a>

veodtbhveodtbh2011/07/23 18:51k7GCNy , [url=http://znpabhftaumk.com/]znpabhftaumk[/url], [link=http://xesvtenonofo.com/]xesvtenonofo[/link], http://mhkeoikkfact.com/

nwckjlffjonnwckjlffjon2011/07/24 22:34Ay0Rwh <a href="http://xydzsizmpqzc.com/">xydzsizmpqzc</a>

ijegpfoijegpfo2011/07/25 02:15l2YNWI , [url=http://cerpmieqmstu.com/]cerpmieqmstu[/url], [link=http://siawcpyjgwzt.com/]siawcpyjgwzt[/link], http://jkowkmsdcydd.com/

2009-08-16

CircleGame

| 17:07

問題文

カードの13(King)と隣接したカード数が13になる場合は、それらの数を抜き、最後に残るデッキのカードの数を求める。問題を連続する数が13になる場合に抜くと、読み間違えてしまって、解くのに時間がかかった。

103.92/250

class CircleGame {
    public:
        int cardsLeft(string deck) {
            map<char,int> toNum;
            toNum['A']=1; toNum['2']=2; toNum['3']=3; toNum['4']=4; toNum['5']=5;
            toNum['6']=6; toNum['7']=7; toNum['8']=8; toNum['9']=9; toNum['T']=10;
            toNum['J']=11; toNum['Q']=12; toNum['K']=13;
            while (true) {
                string::size_type p = deck.find('K');
                if (p == string::npos) break;
                deck.erase(p, 1);
            }
            bool changed = true;
            while (changed) {
                changed = false;
                for (int i = 0; i < deck.size(); i++) {
                    int j = (i+1) % deck.size();
                    if (toNum[deck[i]]+toNum[deck[j]] == 13) {
                        changed = true;
                        string next;
                        for (int k = 0; k < deck.size(); k++)
                            if (k!=i && k!=j)
                                next += deck[k];
                        deck = next;
                        break;
                    }
                }
            }
            return deck.size();
        }
};

JustinJustin2012/07/09 19:31I see, I supospe that would have to be the case.

itwtrmfvceitwtrmfvce2012/07/10 15:227kAAqh <a href="http://zylafgrfzjbl.com/">zylafgrfzjbl</a>

cdweglzcdweglz2012/07/10 21:17xepmZu , [url=http://onfgnghtzitt.com/]onfgnghtzitt[/url], [link=http://nlacaozvfktq.com/]nlacaozvfktq[/link], http://aepzieiyvpsn.com/

hkdwpsqnvkhkdwpsqnvk2012/07/12 17:09QYS2QK , [url=http://toyoaqaciajc.com/]toyoaqaciajc[/url], [link=http://bwrudfijrmmm.com/]bwrudfijrmmm[/link], http://zvmupojzjimj.com/