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-02-03

Packhorses

| 06:13

問題文, SRM 179

自力で解けなかった。以下は Editorial で述べられている Brute force な解答。

165.0/550 (cheated)

class Packhorses {
public:
    int horses(int p, int x, int y) {
        int result = INT_MAX;
        for (int i = 0; i <= p; i++) {
            int xx = max(0, x-2*i);
            int yy = max(0, y-(p-i));
            result = min(result, p + (xx+2)/3 + (yy+1)/2);
        }
        return result;
    }
};

それと一定時間で解く方法が以下。最初の if (y%2 != 0) { ... } は、こうしないと (x,y) = (3a, 2b+1) (a,bは任意の自然数)の場合に対応出来ないから必要。

class Packhorses {
public:
    int horses(int p, int x, int y) {
        int rem = p;
        if (y%2 == 1) {
            y--;
            rem--;
        }
        if ((x+1)/2 < rem) {
            rem -= (x+1) / 2;
            x = 0;
            y -= rem;
            y = (y < 0) ? 0 : y;
        } else {
            x -= 2 * rem;
        }
        return p + (x+2)/3 + (y+1)/2;
    }
};

NelleNelle2011/07/10 03:50Shoot, who would have touhght that it was that easy?

eucmwztyzkeucmwztyzk2011/07/10 16:56z0NxqO <a href="http://hsgtzyqhmovt.com/">hsgtzyqhmovt</a>

wsahgnbbybpwsahgnbbybp2011/07/11 18:47rSe9kY , [url=http://eabtqfkuruwb.com/]eabtqfkuruwb[/url], [link=http://uzoqnjdenqul.com/]uzoqnjdenqul[/link], http://eulnzbieqxug.com/

fahoslsfahosls2011/07/12 18:23znpKbM <a href="http://lmfoqmdfvcpr.com/">lmfoqmdfvcpr</a>

dspfvndspfvn2011/07/12 22:56I7LUvz , [url=http://dqdjjrbohqdj.com/]dqdjjrbohqdj[/url], [link=http://mhsjmpzjdfmi.com/]mhsjmpzjdfmi[/link], http://uyelavyaiohl.com/

IceIce2013/02/18 17:06A million thnkas for posting this information.

ezbdugvezbdugv2013/02/19 02:06uJLKpj <a href="http://gtvcccrcfhuh.com/">gtvcccrcfhuh</a>

ezbdugvezbdugv2013/02/19 02:06uJLKpj <a href="http://gtvcccrcfhuh.com/">gtvcccrcfhuh</a>

ezbdugvezbdugv2013/02/19 02:06uJLKpj <a href="http://gtvcccrcfhuh.com/">gtvcccrcfhuh</a>

qnsmprqnsmpr2013/02/19 02:06IDXBp6 <a href="http://tdiutlvrhsqr.com/">tdiutlvrhsqr</a>

ldlhvtldlhvt2013/02/21 14:11jqHKkH <a href="http://ihumrmpkwbiu.com/">ihumrmpkwbiu</a>

rexpxqrexpxq2013/02/21 18:34FMdzWL , [url=http://fvgkmkrgfoyd.com/]fvgkmkrgfoyd[/url], [link=http://dfkwhpnoefiw.com/]dfkwhpnoefiw[/link], http://elpxctkydvad.com/

2010-01-30

TeXLeX

| 22:45

問題文, SRM 178

'^' のみが特別な入力である入力文字列のASCII値を返せ、という問題。この '^' をどのように処理するかが問題の肝。

この問題を解くには適宜文字列を変換ルールにしたがって1文字目から変換していく必要がある。基本的には変換ルールのとおりに機能を実装すればいい。注意する点としてはルール1を適用すると、値がchar型ではオーバーフローする場合があるので、それ対応する必要がある(僕は気づけなかったために、システムテストで落とされた。

238.78/600 (1 failed)

class TeXLeX {
public:
    vector <int> getTokens(string input) {
        vector <int> result;
        const int len = input.length();
        for (int i = 0; i < len; i++) {
            if (input[i] == '^') {
                if (i >= len-2) {
                    result.push_back('^');
                } else if (input[i+1] != '^') {
                    result.push_back('^');
                } else if (i < len-3 && isHex(input[i+2]) && isHex(input[i+3])) {
                    unsigned int c;
                    sscanf(input.substr(i+2,2).c_str(), "%x", &c);
                    if (c >= 128) {
                        result.push_back(c);
                        i += 3;
                    } else {
                        input[i+3] = (char) c;
                        i += 2;
                    }
                } else if (input[i+2] > 63) {
                    input[i+2] -= 64;
                    i += 1;
                } else {
                    input[i+2] += 64;
                    i += 1;
                }
            } else {
                result.push_back(input[i]);
            }
        }
        return result;
    }
private:
    bool isHex(const char c) {
        return ('0'<=c && c<='9') || ('a'<=c && c<='f');
    }
};

CamiCami2011/08/31 01:54Hey hey hey, take a gaednr at what' you've done

ifhwgxmyifhwgxmy2011/09/01 01:26IyxF2c <a href="http://zzvvdkadzyzw.com/">zzvvdkadzyzw</a>

vsyaesivsyaesi2011/09/03 20:20bbeGDx <a href="http://xqcimzgfyxjv.com/">xqcimzgfyxjv</a>

2009-11-06

NotTwo

| 06:54

問題文, SRM 452

石と石のユークリッド距離が2とならないように石を置いていくとき、最大で石を何個置けるか。

少し考えたけど、どのように並べれば最大になるのかわからなかったので、とりあえず(0,0)から貪欲に置けるだけ置くアルゴリズムを実装。そして、例題は通ったので、自信はないが提出。そしたら、システムテストも通ってしまった。これでいいのか。どう証明すればいいんだろう。

436.36/500

class NotTwo {
public:
    int maxStones(int w, int h) {
        vector<vector<int> > b(h, vector<int>(w, '_'));
        int count = 0;
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                for (int i = 0; i < 4; i++) {
                    // 追記: 左と上に石が置いてあるかどうかを調べるだけでよくて、 
                    //       右と下を調べる必要はなかった。
                    const static int d[4][2] = {
                        {2,0}, {-2,0}, {0,2}, {0,-2} };
                    const int ny = y + d[i][0];
                    const int nx = x + d[i][1];
                    if (0<=ny&&ny<h && 0<=nx&&nx<w && b[ny][nx] == '*')
                        break;
                    if (i == 3) {
                        b[y][x] = '*';
                        count++;
                    }
                }
            }
        }
        return count;
    }
};

mimanamimana2009/12/30 09:25NotTwoで
if (i == 3) {
としている理由を教えていただけませんか?

caliguecaligue2010/01/30 23:04しばらくの間、このブログのチェックをしていなくて、コメントに気づきませんでした。

NotTwo で
if (i == 3) {
としているのは、この方法ではi=0,1,2,3とそれぞれの干渉する場所に石が置かれていないかを確認していて、i=3 までbreakされずにこのif文まで来たときには干渉する場所に石が置かれていないと判断でき、位置(x,y)に石を置けます。なので、if (i==3) のブロック内ではその位置(x,y)に石を置いて、置けた石の数(count)を増やす処理を実行させてます。

2009-11-03

MazeWanderingEasy

| 19:01

問題文, SRM 440

ねずみが最短でチーズに到達するために必要な決断の回数を求める。BFS。

387.83/500

struct State {
    int y, x, dec;
    State() {}
    State(int y, int x, int dec) : y(y), x(x), dec(dec) {}
};

class MazeWanderingEasy {
public:
    int decisions(vector <string> maze) {
        const int H = maze.size();
        const int W = maze[0].size();
        queue<State> Q;
        for (int y = 0; y < H; y++)
            for (int x = 0; x < W; x++) {
                if (maze[y][x] == 'M') {
                    Q.push(State(y,x,0));
                    maze[y][x] = 'X';
                    break;
                }
                if (!Q.empty()) break;
            }
        while (!Q.empty()) {
            State s(Q.front()); Q.pop();
            vector<State> candid;
            for (int i = 0; i < 4; i++) {
                const static int d[4][2] = {
                    {0,1}, {0,-1}, {1,0}, {-1,0} };
                const int ny = s.y + d[i][0];
                const int nx = s.x + d[i][1];
                if (0<=ny&&ny<H && 0<=nx&&nx<W && maze[ny][nx] != 'X') {
                    candid.push_back(State(ny,nx,s.dec));
                }
            }
            if (candid.size() >= 2)
                for (int i = 0; i < candid.size(); i++)
                    candid[i].dec++;
            for (int i = 0; i < candid.size(); i++) {
                const int y = candid[i].y;
                const int x = candid[i].x;
                if (maze[y][x] == '*')
                    return candid[i].dec;
                maze[y][x] = 'X';
                Q.push(candid[i]);
            }
        }
        return 0;
    }
};

2009-10-26

OldestOne

| 05:33

問題文, SRM 177

最年長の人の名前を答える。

380.52/500

class OldestOne {
public:
    string oldest(vector <string> data) {
        string oldestName;
        int oldestAge = -1;
        for (int i = 0; i < data.size(); i++) {
            for (int j = 1; j < data[i].length(); j++) {
                if (isdigit(data[i][j])) {
                    int age;
                    sscanf(data[i].substr(j).c_str(), "%d", &age);
                    if (oldestAge < age) {
                        oldestAge = age;
                        oldestName = data[i].substr(0, j);
                    }
                    break;
                }
            }
        }
        string result;
        for (int i = 0; i < oldestName.length(); i++)
            if (isalpha(oldestName[i])) {
                result = oldestName.substr(i);
                break;
            }
        for (int i = result.length()-1; i >= 0; i--)
            if (isalpha(result[i])) {
                result = result.substr(0, i+1);
                break;
            }
        return result;
    }
};

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-10-14

OmahaLow

| 14:30

問題文, SRM 206

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

あるトランプゲームにおいて、最善の手を求める。

121.31/250 (cheated)

class OmahaLow {
public:
    string low(string sharedCards, string playersCards) {
        string ret = "";
        sort(sharedCards.rbegin(), sharedCards.rend());
        sort(playersCards.rbegin(), playersCards.rend());
        do {
            do {
                string s = sharedCards.substr(0,3) + playersCards.substr(0,2);
                sort(s.rbegin(), s.rend());
                if (s[0] >= '9') continue;
                int i;
                for (i = 0; i < 4; i++) if (s[i] == s[i+1]) break;
                if (i < 4) continue;
                if (ret == "" || s < ret) ret = s;
            } while (next_permutation(playersCards.rbegin(), playersCards.rend()));
        } while (next_permutation(sharedCards.rbegin(), sharedCards.rend()));
        return ret;
    }
};

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

FanFailure

| 20:26

問題文, SRM 195

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

プロセッサを充分に冷やすために、壊れても大丈夫かもしれない最大のファンの数と、壊れても絶対に大丈夫なファンの数を求める。問題文がわかりにくいが、解法は単純。

170.53/250

class FanFailure {
public:
    vector <int> getRange(vector <int> capacities, int minCooling) {
        vector <int> result(2, 0);
        sort(capacities.begin(), capacities.end());
        int sum = accumulate(capacities.begin(), capacities.end(), 0);
        for (int i = 0; i < capacities.size(); i++) {
            sum -= capacities[i];
            if (sum < minCooling) break;
            result[0]++;
        }
        sum = accumulate(capacities.begin(), capacities.end(), 0);
        for (int i = capacities.size()-1; i >= 0; i--) {
            sum -= capacities[i];
            if (sum < minCooling) break;
            result[1]++;
        }
        return result;
    }
};