Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2010-02-07

TheFansAndMeetingsDivTwo

| 19:32

問題文, SRM 460

JohnとBrusが同じ数のファンに会える確率を求める。苦手意識のある確率の問題だったが、全パターンを調べる方法であっさり解けた。以下の回答は3重ループだが、2重ループでも解けると思う。

439.61/500

class TheFansAndMeetingsDivTwo {
public:
    double find(vector <int> minJ, vector <int> maxJ, vector <int> minB, vector <int> maxB) {
        const int size = minJ.size();
        double result = 0.0;
        for (int i = 0; i < size; i++) {
            double pJ = 1.0 / size / (maxJ[i]-minJ[i]+1);
            for (int john = minJ[i]; john <= maxJ[i]; john++) {
                for (int j = 0; j < size; j++) {
                    if (minB[j] <= john && john <= maxB[j]) {
                        double pB = 1.0 / size / (maxB[j]-minB[j]+1);
                        result += pJ * pB;
                    }
                }
            }
        }
        return result;
    }
};

nbrrvlwonbrrvlwo2011/02/28 02:021t5XZT <a href="http://zfbmnqbofnfy.com/">zfbmnqbofnfy</a>, [url=http://ahgnwsctjvhh.com/]ahgnwsctjvhh[/url], [link=http://hyvrokviobof.com/]hyvrokviobof[/link], http://mtinuysnserr.com/

EriklesErikles2012/11/14 20:56Heck yeah this is exactly what I nedeed.

wbifcqahpfwbifcqahpf2012/11/15 12:17WIV2s4 <a href="http://fvdiwshhnhfy.com/">fvdiwshhnhfy</a>

bclurpjuqvcbclurpjuqvc2012/11/16 10:42j0qQxV , [url=http://xripkjekfhlk.com/]xripkjekfhlk[/url], [link=http://nqncovdmomdj.com/]nqncovdmomdj[/link], http://wgpfjbkvtjgo.com/

xjkekpxjkekp2012/11/17 11:23Aogh4X <a href="http://tpebktqqllbu.com/">tpebktqqllbu</a>

yxhqrnjctkryxhqrnjctkr2012/11/17 20:59SMxofJ , [url=http://lzrngezmevzk.com/]lzrngezmevzk[/url], [link=http://rqgcqejpucew.com/]rqgcqejpucew[/link], http://ccklhgmvvezl.com/

2010-01-31

OnLineRank

| 22:32

問題文, SRM 179

成績のランクを直前の k 人の成績の中でランクで計算するとき、そのランクの合計を求める。その通りに実装すればいい。Editorial を読んで気づいたが、rank 変数は作らずとも sum のインクリメントだけで充分だった。

235.88/250

class OnLineRank {
public:
    int calcRanks(int k, vector <int> scores) {
        int sum = 1;
        for (int i = 1; i < scores.size(); i++) {
            int rank = 1;
            for (int j = max(0,i-k); j < i; j++) {
                if (scores[j] > scores[i])
                    rank++;
            }
            sum += rank;
        }
        return sum;
    }
};

MateoMateo2013/02/17 22:51Inteillgence and simplicity - easy to understand how you think.

schgrzschgrz2013/02/19 00:42foexv7 <a href="http://krsawktetuoo.com/">krsawktetuoo</a>

ixdtrsrixdtrsr2013/02/21 12:375pdlI9 <a href="http://vmkqxxlmsxmu.com/">vmkqxxlmsxmu</a>

ixdtrsrixdtrsr2013/02/21 12:375pdlI9 <a href="http://vmkqxxlmsxmu.com/">vmkqxxlmsxmu</a>

oaxixvwpreuoaxixvwpreu2013/02/21 17:01OpAgB8 , [url=http://wexmtjdpiwje.com/]wexmtjdpiwje[/url], [link=http://loprselolouh.com/]loprselolouh[/link], http://eeikflgzlhwl.com/

2009-10-21

BoredPhilosophers

| 12:48

問題文, SRM 451

教室にN人の哲学者がいます。彼らはとても退屈なので、本から抜粋した適当なテキスト使ってゲームを始めました。1番目の哲学者はテキスト中の語の種類数を言います。2番目の哲学者は2個の連続する語からなるセンテンスの種類数を言います。同様にi番目の哲学者はi個の連続する語からなるセンテンスの種類数を言います。このゲームはN人全ての哲学者が発言した後に終了します。

テキストとして vector<string> が与えられます。このvectorの要素を結合(concatenate)し、テキストを完成させ、N個の要素からなる vector<int> を返しなさい(i番目の要素にはi人目の哲学者が言った数を入れる)。テキスト中の語はシングルスペースで区切られています。

問題文中のconcatenateの意味を理解するのに時間がかかった。意味が理解できれば実装は難しくない。

265.46/500

class BoredPhilosophers {
public:
    vector <int> simulate(vector <string> text, int N) {
        string T;
        for (int i = 0; i < text.size(); i++)
            T += text[i];
        vector<string> words;
        istringstream iss(T);
        string s;
        while (iss >> s) words.push_back(s);
        vector <int> result;
        for (int d = 1; d <= N; d++) {
            set<string> difWords;
            for (int i = 0; i < words.size()-d+1; i++) {
                string t(words[i]);
                for (int j = i+1; j < i+d; j++)
                    t += " " + words[j];
                difWords.insert(t);
            }
            result.push_back(difWords.size());
        }
        return result;
    }
};

ivcbmcaeivcbmcae2011/02/28 07:41NZm68y <a href="http://ilbauxmjluym.com/">ilbauxmjluym</a>, [url=http://xbddmcdppokz.com/]xbddmcdppokz[/url], [link=http://sjwaelhpgvzy.com/]sjwaelhpgvzy[/link], http://uddhrwxfjfig.com/

2009-09-24

OddDivisors

| 21:02

問題文, SRM 449

f(x)をxの最大の奇除数とする。正の整数Nが与えられたとき、f(1)+f(2)+f(3)+...+f(N)を求めよ。

独力で解けなかったので、Panteraさんの解答を参考にしました。f(x)の1からf(N)までの和をS(N)とすると、その漸化式は次の通りです:

 S(N) = \{\array{ll$0\quad & \mbox{if}\quad{} N \quad{} \mbox{is}\quad 0,\\N+S(N-1)\quad & \mbox{if}\quad{}  N \quad \mbox{is} \quad \mbox{odd},\\(N/2)^2+S(N/2)\quad & \mbox{if}\quad{} N \quad \mbox{is}\quad \mbox{even}.\.

偶数の場合がこのような式になるのは、(N/2)+1からNのf(x)の値として、1から2(N/2)-1(=N-1)の全ての奇数が現れるためだと思います。

class OddDivisors {
public:
    long long findSum(int N) {
        if (N == 0) return 0;
        if (N%2 == 1) return N + findSum(N-1);
        long long h = N / 2;
        return h*h + findSum(h);
    }
};

CoralynCoralyn2011/07/11 02:35Heck yeah this is exactly what I neeedd.

gnblerevzcgnblerevzc2011/07/11 17:56uYLsg6 <a href="http://xastizaaaprn.com/">xastizaaaprn</a>

caszabcaszab2011/07/11 21:55uZUOLK , [url=http://bkzlqlrxqsvd.com/]bkzlqlrxqsvd[/url], [link=http://xoibmkylinnn.com/]xoibmkylinnn[/link], http://yipaejjalqbl.com/

dipyiedipyie2011/07/13 18:34IdrEYp <a href="http://ofalwtjxbsqh.com/">ofalwtjxbsqh</a>

kaedxpshifkaedxpshif2011/07/13 23:313Uxab3 , [url=http://wtysquibqpuq.com/]wtysquibqpuq[/url], [link=http://qbzcfinwlbfk.com/]qbzcfinwlbfk[/link], http://tykaxlxiebyk.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-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-02

BettingMoney

| 16:55

問題文, SRM 191

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

229.00/250

class BettingMoney {
public:
    int moneyMade(vector <int> amounts, vector <int> centsPerDollar, int finalResult) {
        int result = 0;
        for (int i = 0; i < amounts.size(); i++) {
            if (i == finalResult) result -= amounts[i] * centsPerDollar[i];
            else result += 100 * amounts[i];
        }
        return result;
    }
};

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

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

2009-08-25

QuiningTopCoder

| 14:09

問題文, SRM 152

自分自身のソースを出力するプログラムかどうかを確認。

150.0/500 (1 failed)

class QuiningTopCoder {
public:
    string testCode(string source) {
        string output;
        const static int TIME_LIMIT = 80000;
        stack<int> stk;
        for (int i = 0; i < TIME_LIMIT; i++) stk.push(0);
        int IP=0, D=1, N=source.size();
        int cycle = 0;
        while (source[IP] != '@' && cycle < TIME_LIMIT) {
            const char c = source[IP];
            int DD = D;
            if (isdigit(c)) {
                stk.push(c-'0');
            } else if (c == '$') {
                stk.pop();
            } else if (c == ':') {
                int X = stk.top(); stk.pop();
                stk.push(X); stk.push(X);
            } else if (c == 'W') {
                int A = stk.top(); stk.pop();
                int B = stk.top(); stk.pop();
                stk.push(A); stk.push(B);
            } else if (c == ',') {
                int X = stk.top(); stk.pop();
                output += source[abs(X)%N];
                if (output == source ||
                        output != source.substr(0,output.length())) 
                    break;
            } else if (c == '+') {
                int A = stk.top(); stk.pop(); 
                int B = stk.top(); stk.pop();
                stk.push(A+B);
                if (abs(stk.top()) > 1000000000) break;
            } else if (c == '-') {
                int A = stk.top(); stk.pop(); 
                int B = stk.top(); stk.pop();
                stk.push(A-B);
                if (abs(stk.top()) > 1000000000) break;
            } else if (c == '#') {
                DD *= 2;
            } else if (c == 'R') {
                DD *= -1; D *= -1;
            } else if (c == 'S') {
                int X = stk.top(); stk.pop();
                if (X > 0) stk.push(1);
                else stk.push(-1);
            } else if (c == '_') {
                int X = stk.top(); stk.pop();
                D = DD = X % N;
            } else if (c == 'J') {
                int X = stk.top(); stk.pop();
                IP = abs(X) % N;
            } 
            if (c != 'J')
                IP = (3*N+IP+DD) % N;
            cycle++;
        }
      
        ostringstream res;
        if (source[IP] == '@') {
            res << "BADEND " << cycle;
        } else if (cycle == TIME_LIMIT) {
            res << "TIMEOUT";
        } else if (abs(stk.top()) > 1e+9) {
            res << "OVERFLOW " << cycle;
        } else if (source != output) {
            res << "MISMATCH " << cycle;
        } else {
            res << "QUINES " << cycle;
        }
        return res.str();
    }
};