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

TheQuestionsAndAnswersDivTwo

| 07:31

たまには参加するかと思って、3ヶ月ぶりにSRMに参戦しました。結果は678.75点で、62位(Div2)。Level-1,-2ともあっさり解けた。Level-3は解けるかもと思って最後まで解こうとしていたが、結局答えが合わなかった。

Rating は 1187 から 1252 に上がり、苦難(?)の1年半を経てようやくDiv1に再昇格できた。Div1でやっていくには微妙な実力だが、また1回で降格してそのままずるずるというのは避けたいな。

-----

問題文, SRM 460

Yes/Noのみのインタビューで、想定された回答の組み合わせは全何種類か。

2のパターン乗で答えが求められる。

239.14/250

class TheQuestionsAndAnswersDivTwo {
public:
    int find(vector <string> questions) {
        set<string> s;
        for (int i = 0; i < questions.size(); i++)
            s.insert(questions[i]);
        return (int)pow(2.0, (double)s.size());
    }
}

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

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>

2010-01-29

SimpleCalculator

| 19:13

久しぶりに解いた。最近解いてなかったのは英語力の強化を重視していて、英語力が充分ついてから解くのを再開しようかと思っていたから。しかし、思ったよりも時間がかかりそうで(頑張っても1年はかかる)、問題を解く感覚が鈍りそうなので、1日1時間程度をアルゴリズム系の問題を解く時間かそのための勉強に当てようと思います。1時間だと難しめの問題を解くのは時間的に厳しいので、解く問題はDiv2のLevel-1,2とDiv1のLevel-1の問題を中心にします。

問題文, SRM 178

四則演算だけのシンプルな計算機。今度からはしっかり解説を付けたいなと思ったのに、何も語ることがない。この問題はどのように入力値を文字列から得るかだと思うが、それも istringstream か sscanf を使えば実現できるので、やはり語ることがない。

248.39/250

class SimpleCalculator {
public:
    int calculate(string input) {
        int a, b;
        char c;
        istringstream(input) >> a >> c >> b;
        if (c == '+') return a + b;
        else if (c == '-') return a - b;
        else if (c == '*') return a * b;
        else return a / b;
    }
};

MaheshMahesh2012/11/14 15:48Furrealz? That's marovelusly good to know.

mrmqezkqxwmrmqezkqxw2012/11/15 11:52s6bK06 <a href="http://gcchvukbnzox.com/">gcchvukbnzox</a>

spsrxxspsrxx2012/11/16 10:14TvaJTu , [url=http://eciyaqdchfxo.com/]eciyaqdchfxo[/url], [link=http://ttwirdzyever.com/]ttwirdzyever[/link], http://mnxmkjngbida.com/

lewoklxfgxlewoklxfgx2012/11/17 00:38yuecsC <a href="http://lqhnazvgbvem.com/">lqhnazvgbvem</a>

gflffsgflffs2012/11/17 10:45N1Z2Z1 , [url=http://vngcyqvvvmgl.com/]vngcyqvvvmgl[/url], [link=http://dkarqzmcxylp.com/]dkarqzmcxylp[/link], http://zzwhaounqels.com/

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

EggCartons

| 06:31

SRM 452 Div2は250,500を解けて、674.40点。Division rankは76位で、比較的よかった。1000の問題は30分以上あまっていたけど、解法が思いつかなかったので早々に諦めた。Ratingは 1120 から 1187 に上がった。Challenge phaseに真面目に参加して、Challengeを一回でも成功させていればDiv1に昇格できていたかもしれない。


問題文, SRM 452

卵が6個入ったパックと8個が入ったパックがあるとき、指定された数の卵を買うには最低何パック買えばいいのか。

問題を読んだときにナップサック問題みたいだなと思ったので、DPで解いた。他の方の回答を見ると 8i+6j=n を満たす i,j を調べている方が多かった。

238.04/250

class EggCartons {
public:
    int minCartons(int n) {
        if (n < 6) return -1;
        vector<int> v(n+1, -1);
        v[0] = 0;
        for (int w = 0; w <= n; w++) {
            if (w >= 8 && v[w-8] != -1) v[w] = 1 + v[w-8];
            else if (w >= 6 && v[w-6] != -1) v[w] = 1 + v[w-6];
        }
        return v[n];
    }
};

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

PizzaDelivery

| 07:29

問題文, SRM 451

2人の配達人を使って、ピザを配達し終えるのにかかる最短時間を求める。

解くのに2時間強かかった。しょうもないバグにより3回、時間制限により1回、システムテストで落とされた。解法はBFS+Brute Forceなので割と単純だが、異常に調子が良い時でないと本番の時間内にバグなしで解ける気がしない。

300.00/1000 (4-failed)

const static int INFTY = INT_MAX/2;

class PizzaDelivery {
    public:
        int deliverAll(vector <string> terrain) {
            const int H = terrain.size();
            const int W = terrain[0].size();
            vector<pair<int,int> > piza;
            pair<int,int> r;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (terrain[y][x] == 'X') {
                        r = make_pair(y, x);
                    } else if (terrain[y][x] == '$') {
                        piza.push_back(make_pair(y,x));
                    }
                }

            int D[100];
            int T[100][100];
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++)
                    T[y][x] = INFTY;
            T[r.first][r.second] = 0;
            queue<pair<int,int> > Q;
            Q.push(r);
            while (!Q.empty()) {
                pair<int,int> a = Q.front(); Q.pop();
                const int y = a.first, x = a.second;
                const static int d[4][2] = {
                    {0,1}, {0,-1}, {1,0}, {-1,0} };
                for (int i = 0; i < 4; i++) {
                    const int ny = y + d[i][0];
                    const int nx = x + d[i][1];
                    if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                        if (!isdigit(terrain[ny][nx]) || !isdigit(terrain[y][x])) {
                            if (T[y][x]+2 < T[ny][nx]) {
                                T[ny][nx] = T[y][x] + 2;
                                Q.push(make_pair(ny, nx));
                            }
                            continue;
                        }
                        if (abs(terrain[ny][nx]-terrain[y][x]) == 0 && 
                                T[y][x]+1 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 1;
                            Q.push(make_pair(ny, nx));
                        } else if (abs(terrain[ny][nx]-terrain[y][x]) == 1 && 
                                T[y][x]+3 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 3;
                            Q.push(make_pair(ny, nx));
                        }
                    }
                }
            }
            for (int i = 0; i < piza.size(); i++) {
                D[i] = T[piza[i].first][piza[i].second];
                if (D[i] == INFTY) return -1;
            }

            int minTime = INFTY;
            for (int i = 0; i < 1<<(piza.size()-1); i++) {
                bitset<20> pat(i);
                vector<int> vboy1, vboy2;
                for (int j = 0; j < piza.size(); j++) {
                    if (pat[j]) vboy1.push_back(D[j]);
                    else        vboy2.push_back(D[j]);
                }
                int boy1=0, boy2=0;
                if (vboy1.size() > 0)
                    boy1 = 2*accumulate(vboy1.begin(), vboy1.end(), 0) 
                        - *max_element(vboy1.begin(), vboy1.end());
                if (vboy2.size() > 0)
                    boy2 = 2*accumulate(vboy2.begin(), vboy2.end(), 0) 
                        - *max_element(vboy2.begin(), vboy2.end());
                //cout << pat << " " << boy1 << " " << boy2 << endl;
                minTime = min(minTime, max(boy1, boy2));
            }
            return minTime;
        }
};

nphuuejznphuuejz2011/02/28 17:01PX5gMr <a href="http://thxvtmuhvzkh.com/">thxvtmuhvzkh</a>, [url=http://aegsueyzfdwj.com/]aegsueyzfdwj[/url], [link=http://juwwqktqnkxe.com/]juwwqktqnkxe[/link], http://fuvdtrdrrxop.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;
    }
};

ReverseMagicalSource

| 12:48

SRM 451 Div2 は250と500を通せて、511.38(245.92+265.46)点だった。Ratingは 1074 から 1119 に上がった。

問題文, SRM 451

 x=10^0s+10^1s+10^2s+\cdots10^is > A \mbox{ } (i \ge 0)を満たす最小の xを求める。

245.92/250

class ReverseMagicalSource {
public:
    int find(int source, int A) {
        int x = source;
        while (x <= A) {
            source *= 10;
            x += source;
        }
        return x;
    }
};

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/