Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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