Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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/

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

IncredibleMachine

| 13:44

問題文, SRM 440

加速度を求める。二分探索法で解ける。以下はコード中の数式に関するメモ。

問題文から、

 d = v_0 t + 0.5at^2,

 v_1 = v_0 + at.

t を解の公式を用いて求めると、

 t = \frac{-v_0 + \sqrt{v_0^2+2ad} }{a}.

よって、

 v_1 = sqrt{v_0^2+2ad}.

地点(x_i,y_i)から地点(x_{i+1},y_{i+1})への移動距離d_iは三平方の定理により

 d_i = \sqrt{(x_i-x_{i+1})^2 + (y_i-y_{i+1})^2}.

この距離を移動するのに必要な時間 t_iは、この間の速度の平均が (v_0+v_1)/2なので、

 t_i = \frac{2d}{v_0+v_1}.

113.73/250 (cheated)

double squ(const double x) { return x*x; }

class IncredibleMachine {
public:
    double gravitationalAcceleration(vector <int> x, vector <int> y, int T) {
        double lg=0, hg=1e30;
        for (int step = 0; step < 3000; step++) {
            double g = (lg+hg) / 2;
            double v0=0, time=0;
            for (int i = 0; i < x.size()-1; i++) {
                double v1 = sqrt(squ(v0) + 2*g*(y[i]-y[i+1]));
                double d = sqrt(squ(x[i]-x[i+1]) + squ(y[i]-y[i+1]));
                time += 2*d / (v0+v1);
                v0 = v1;
            }
            if (time > T) lg = g;
            else hg = g;
        }
        return lg;
    }
};

MaguyMaguy2012/11/16 16:52Finally! This is just what I was looknig for.

zyjcemlzyjceml2012/11/18 07:41mKV8c4 , [url=http://osvnksruetrt.com/]osvnksruetrt[/url], [link=http://mgxdumvbmsag.com/]mgxdumvbmsag[/link], http://ninqkbvhlrwd.com/

bremwwuhxbremwwuhx2012/11/18 14:11IzzeKk <a href="http://bcfzmpdxhygr.com/">bcfzmpdxhygr</a>

2009-09-29

IncredibleMachineEasy

| 09:17

問題文, SRM 440

与えられたシステムの、重力の加速度を求めよ。

加速度を求める式を作って解かせるだけの問題だが、自力で解けなかった。

196.50/250 (cheated)

class IncredibleMachineEasy {
public:
    double gravitationalAcceleration(vector <int> height, int T) {
        double sum = 0.0;
        for (int i = 0; i < height.size(); i++)
            sum += sqrt(2*height[i]);
        return square(sum/T);
    }
private:
    double square(const double x) { return x*x; }
};

2009-09-25

TeamPhoto

| 20:54

問題文, SRM 167

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

写真を撮る際に、身長の差の合計が最も小さくなるような並び方を考える。

232.95/750 (cheated)

class TeamPhoto {
public:
    int minDiff(vector <int> height) {
        n = height.size();
        vector<int> mem(height.begin()+3, height.end());
        sort(mem.begin(), mem.end());
        m = mem.size();

        int minSum = calc(height, mem, m/2);
        if (n%2 == 0)
            minSum = min(minSum, calc(height, mem, m/2+1));
        return minSum;
    }
private:
    int n, m;
    int calc(vector<int>& ht, vector<int>& mem, int mid) {
        return min(diff(ht[1], mem[0], mem[mid-1], ht[0]) +
                     diff(ht[0], mem[mid], mem[m-1], ht[2]),
                   diff(ht[2], mem[0], mem[mid-1], ht[0]) +
                     diff(ht[0], mem[mid], mem[m-1], ht[1]));
    }
    int diff(int a, int l, int h, int b) {
        return h-l + min(abs(a-l)+abs(b-h), abs(a-h)+abs(b-l));
    }
}

JohnieJohnie2013/02/16 22:15Check that off the list of things I was cofnsued about.

lpzworxlpzworx2013/02/17 21:13EhdvUV <a href="http://lggmfstpruis.com/">lggmfstpruis</a>

kdwdegjekdwdegje2013/02/18 05:09QCIf4X , [url=http://nxklzrjfqokk.com/]nxklzrjfqokk[/url], [link=http://iopulhzspqez.com/]iopulhzspqez[/link], http://vwnoyqhqksel.com/

kfuflfxdkfuflfxd2013/02/19 19:10JRh8jp , [url=http://ybazmifswqhs.com/]ybazmifswqhs[/url], [link=http://ceackqdzvvcl.com/]ceackqdzvvcl[/link], http://smwogahevohi.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-17

LargestCircle

| 19:05

問題文, SRM 212

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

マークされたマスを通らない円を描くとき、描くことができる最大の円の半径を求める。円がマスを通るかどうかの判定をどのように実装すればいいのかわからなかった。

428.44/1000 (cheated)

int square(const int x) { return x * x; }

class LargestCircle {
public:
    int radius(vector <string> grid) {
        const int H = grid.size();
        const int W = grid[0].size();
        for (int rad = min(H/2,W/2); rad >= 1; rad--) {
            const int sr = square(rad);
            for (int cy = rad; cy <= H-rad; cy++)
                for (int cx = rad; cx <= W-rad; cx++) {
                    bool passed = true;
                    for (int y = 0; y < H; y++) {
                        for (int x = 0; x < W; x++) {
                            if (grid[y][x] != '#') continue;
                            const int dy = y - cy;
                            const int dx = x - cx;
                            const int p0 = square(dy)   + square(dx);
                            const int p1 = square(dy+1) + square(dx);
                            const int p2 = square(dy)   + square(dx+1);
                            const int p3 = square(dy+1) + square(dx+1);
                            if (p0<=sr && p1<=sr && p2<=sr && p3<=sr) continue;
                            if (p0>=sr && p1>=sr && p2>=sr && p3>=sr) continue;
                            passed = false;
                            break;
                        }
                        if (!passed) break;
                    }
                    if (passed) return rad;
                }
        }
        return 0;
    }
};

2009-09-05

Jumper

| 19:49

問題文, SRM 158

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

一番上までいくのに何ステップかかるか。BFSで解ける。問題を理解するのに1時間。そして、解法が浮かばなくてEditorialを見ながら解くのに2時間ぐらいかかった。

304.01/1000 (cheated)

struct State {
    int x, y, t;
    State() {}
    State(const int x, const int y, const int t) :
        x(x), y(y), t(t) {}
};
bool operator< (const State& a, const State& b) {
    if (a.t < b.t) {
        return true;
    } else if (a.t > b.t) {
        return false;
    } else {
        if (a.y > b.y) {
            return true;
        } else if (a.y < b.y) {
            return false;
        } else {
            return a.x < b.x;
        }
    }
}

class Jumper {
public:
    int minTime(vector <string> patterns, vector <int> speeds, string rows) {
        const int HEIGHT = rows.size()+1;
        const int WIDTH = 20;
        vector<string> grid(HEIGHT+1);
        grid[0] = grid[HEIGHT] = string(WIDTH, '#');
        for (int i = 0; i < rows.size(); i++) 
            for (int j = 0; j < 4; j++)
                grid[i+1] += patterns[rows[i]-'0'];
        queue<State> Q;
        Q.push(State(0,0,0));
        set<State> checked;
        while (!Q.empty()) {
            State s = Q.front(); Q.pop();
            if (s.t > 2100) break;
            if (s.y >= HEIGHT) return s.t;
            const static int MOVE_KINDS = 5;
            const static int d[MOVE_KINDS][2] = {
                {0,0},{1,0},{-1,0},{0,1},{0,-1} };
            for (int i = 0; i < MOVE_KINDS; i++) {
                const int dx = s.x + d[i][0];
                const int dy = s.y + d[i][1];
                if (0<=dx&&dx<WIDTH && 0<=dy) {
                    int offset = (dy==0||dy==HEIGHT) ? 0 : 
                        (((-s.t*speeds[rows[dy-1]-'0'])%5)+5)%5;
                    if (grid[dy][(dx+offset)%WIDTH] == '#') {
                        const int ddx = dx + ((dy==0||dy==HEIGHT)? 0 :
                                speeds[rows[dy-1]-'0']);
                        if (0<=ddx && ddx<WIDTH) {
                            State next(ddx, dy, s.t+1);
                            if (checked.find(next) == checked.end()) {
                                checked.insert(next);
                                Q.push(next);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
};

TickTick

| 13:04

問題文, SRM 177

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

何種類のイベントの組み合わせができるか。問題の意味がわからなかった。Editorialを読んでようやく理解できた。

122.36/300 (cheated)

class TickTick {
public:
    int count(vector <string> events) {
        vector<double> e; 
        e.push_back(0.0);
        for (int i = 0; i < events.size(); i++) 
            e.push_back(atof(events[i].c_str()));
        set<string> ret;
        for (int i = 0; i < e.size(); i++) {
            double tick = e[i] + 5e-8;
            double prev = DBL_MIN;
            string seq;
            for (int j = 0; j < e.size(); j++) {
                double tickIndex = floor(e[j]-tick);
                if (tickIndex == prev) seq += "S";
                else seq += "D";
                prev = tickIndex;
            }
            ret.insert(seq);
        }
        return ret.size();
    }
};

2009-08-28

Collision

| 13:32

問題文, SRM 153

2つの確率の差を求める。

178.38/450 (cheated)

class Collision {
public:
    double probability(vector <int> assignments, int ids) {
        double p1=1, p2=1;
        int d = ids;
        for (int i = 0; i < assignments.size(); i++) {
            if (assignments[i] > ids) return 0;
            int n = ids;
            for (int j = 0; j < assignments[i]; j++) {
                p1 *= (double) d / ids;
                p2 *= (double) d / n;
                d--; n--;
            }
        }
        return p2 - p1;
    }
};

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