Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-19

WordFind

| 10:10

問題文, SRM 232

Algorithm Tutorials -- How to Find a Solutionから。

worldListの単語は2次元配列gridのどこに隠れているのか。

171.37/250

class WordFind {
public:
    vector <string> findWords(vector <string> grid, vector <string> wordList) {
        const int H = grid.size();
        const int W = grid[0].size();
        vector <string> result(wordList.size(), "");
        for (int i = 0; i < wordList.size(); i++) {
            const int len = wordList[i].length();
            for (int r = 0; r < H; r++) {
                for (int c = 0; c < W; c++) {
                    const static int DIR_KINDS = 3;
                    const static int d[DIR_KINDS][2] = { {1,0}, {0,1}, {1,1} };
                    for (int j = 0; j < DIR_KINDS; j++) {
                        if (r+len*d[j][0] > H) continue;
                        if (c+len*d[j][1] > W) continue;
                        for (int k = 0; k < len; k++) {
                            if (wordList[i][k] != grid[r+k*d[j][0]][c+k*d[j][1]]) break;
                            if (k == len-1) {
                                ostringstream pos;
                                pos << r << " " << c;
                                result[i] = pos.str();
                                break;
                            }
                        }
                        if (result[i] != "") break;
                    }
                    if (result[i] != "") break;
                }
                if (result[i] != "") break;
            }
        }
        return result;
    }
};

YulyYuly2012/11/15 07:39You've hit the ball out the park! Incrieldbe!

ogjjxpbfedogjjxpbfed2012/11/16 05:36fSvQ3Y <a href="http://opkomgzlgoxs.com/">opkomgzlgoxs</a>

lllebwlllebw2012/11/17 05:07hx1oWF , [url=http://cdmmhpymcwvw.com/]cdmmhpymcwvw[/url], [link=http://zhernoocdpab.com/]zhernoocdpab[/link], http://pnimqosbodna.com/

fjpobhvgxctfjpobhvgxct2012/11/17 12:09CrZUBe <a href="http://gitnhbscrxca.com/">gitnhbscrxca</a>

wahfhgiylpwahfhgiylp2012/11/17 21:39wFLUSt , [url=http://eovjxcvzlscm.com/]eovjxcvzlscm[/url], [link=http://kpmczprsyijg.com/]kpmczprsyijg[/link], http://lqammhsdbqsp.com/

2009-09-18

Cafeteria

| 19:21

問題文, SRM 229

Algorithm Tutorials -- How to Find a Solutionから。

学食が閉まる前に大学に着くには遅くとも何時何分に家を出ればよいのか。ややこしく考えすぎた。素直にBrute forceな方法で解けばすぐに解けた問題。

113.94/250

class Cafeteria {
public:
    string latestTime(vector <int> offset, vector <int> walkingTime, vector <int> drivingTime) {
        const static int closeTime = 14*60 + 30;
        const static int interval = 10;
        const int n = offset.size();
        int latest = 0;
        for (int i = 0; i < n; i++) {
            for (int j = closeTime/interval; j >= 0; j--) {
                int time = interval*j + offset[i];
                if (time+drivingTime[i] <= closeTime) {
                    latest = max(latest, time-walkingTime[i]);
                    break;
                }
            }
        }
        char result[10];
        int hh = latest/60;
        if (hh > 12) hh -= 12;
        int mm = latest%60;
        sprintf(result, "%02d:%02d", hh, mm);
        return string(result);
    }
};

LaticiaLaticia2011/08/30 13:38AFAIC that's the best asnewr so far!

parpntparpnt2011/09/01 01:49bhJbxd <a href="http://zdrhotngocjb.com/">zdrhotngocjb</a>

xtmxmyqetycxtmxmyqetyc2011/09/01 16:48NJOJOQ , [url=http://wrzwsyjcsqsw.com/]wrzwsyjcsqsw[/url], [link=http://wfmzjrcnpugt.com/]wfmzjrcnpugt[/link], http://iipgxojwlgto.com/

xhxqwjfozxhxqwjfoz2011/09/03 18:07AyKuiE <a href="http://bcyztvxrbbno.com/">bcyztvxrbbno</a>

fgetygzmhsfgetygzmhs2011/09/04 01:21sWPIEu , [url=http://tsztjxihmrvp.com/]tsztjxihmrvp[/url], [link=http://leqihxtiuisd.com/]leqihxtiuisd[/link], http://mqdfcrmvtkyt.com/

2009-09-15

GeneralChess

| 18:47

問題文, SRM 197

Algorithm Tutorials -- How to Find a Solutionから。

全てのナイトから脅かされているマスの位置を探す。

219.34/250

class GeneralChess {
public:
    vector <string> attackPositions(vector <string> pieces) {
        const int n = pieces.size();
        map<pair<int,int>,int> count;
        for (int i = 0; i < n; i++) {
            int x, y;
            sscanf(pieces[i].c_str(), "%d,%d", &x, &y);
            for (int dx = -2; dx <= 2; dx++)
                for (int dy = -2; dy <= 2; dy++) {
                    if (dx*dx+dy*dy != 5) continue;
                    count[make_pair(x+dx,y+dy)]++;
                }
        }

        vector<string> result;
        for (map<pair<int,int>,int>::const_iterator itr = count.begin();
                itr != count.end(); itr++)
            if (itr->second == n) {
                ostringstream oss;
                oss << itr->first.first << ',' << itr->first.second;
                result.push_back(oss.str());
            }
        return result;
    }
};

2009-09-10

TheCardShufflingDivTwo

| 22:38

問題文, SRM 448

カードを並べ替えたときに、一番に上にくるのは何か。変換テーブルを作って求めた。もう少し考えて、法則性があるかどうかを検討した方が、提出までの時間を短縮できたと思う。

266.46/500

class TheCardShufflingDivTwo {
public:
    int shuffle(int n, int m) {
        vector<int> L((int)ceil((double)n/2));
        vector<int> R(n/2);
        for (int i = 0; i < n/2; i++) {
            L[i] = 2*i+1;
            R[i] = 2*i+2;
        }
        if (n%2 == 1) L[n/2] = n;
        vector<int> table(n+1);
        for (int i = L.size()-1; i >= 0; i--)
            table[R.size()+i+1] = L[i];
        for (int i = R.size()-1; i >= 0; i--)
            table[i+1] = R[i];

        int top = 1;
        for (int i = 0; i < m; i++)
            top = table[top];
        return top;
    }
};

2009-09-09

GravityBomb

| 16:40

問題文, SRM 200

テトリスの局面において、隙間をなくすとどうなるか。

421.30/500

class GravityBomb {
    public:
        vector <string> aftermath (vector <string> board) {
            const int H = board.size();
            const int W = board[0].size();
            const static char BLOCK = 'X';
            vector<int> counter(W, 0);
            for (int i = 0; i < H; i++)
                for (int j = 0; j < W; j++)
                    if (board[i][j] == BLOCK)
                        counter[j]++;
            int minBlocks = *min_element(counter.begin(), counter.end());

            vector <string> result(H, string(W, '.'));
            for (int j = 0; j < W; j++)
                for (int i = 0; i < counter[j]-minBlocks; i++)
                    result[H-1-i][j] = BLOCK;
            return result;
        }
};

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

BusinessTasks

| 09:12

問題文, SRM 236

Algorithm Tutorials -- How to Find a Solutionから。

円形に並べた仕事をn個飛ばしで選んで処理する。Joseph問題の一種。この問題サイズだったらvectorのeraseを使える。書き終わって気づいた。このプログラムにforループはいらなくて、whileループでいい。

238.23/250

class BusinessTasks {
public:
    string getTask(vector <string> list, int n) {
        int p = 0;
        for (int i = 0; list.size() > 1; i++) {
            p = (p + n-1) % list.size();
            p = list.erase(list.begin()+p) - list.begin();
        }
        return list[0];
    }
};

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

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