Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

Fifteen

| 07:35

問題文, SRM 172

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

言った数の内、3つの数の合計が15になったら勝ちのゲームにおいて、挑戦者(patron)が勝てるかどうか。TutorialにTick-Tack-Toeの変装だと書かれていたので、どのように解くか考えたが、少し強引な方法しか考えつかなかった。

204.31/500

class Fifteen {
public:
    string outcome(vector <int> moves) {
        for (int n = 1; n <= 9; n++) {
            if (find(moves.begin(),moves.end(),n) == moves.end()) {
                vector<int> newMoves(moves);
                newMoves.push_back(n);
                if (isWin(newMoves, true)) {
                    char res[10];
                    sprintf(res, "WIN %d", n);
                    return string(res);
                }
            }
        }
        return "LOSE";
    }
private:
    bool isWin(const vector<int>& moves, const bool isPatron) {
        for (int i = isPatron? 1:0; i < moves.size(); i += 2)
            for (int j = i+2; j < moves.size(); j += 2)
                for (int k = j+2; k < moves.size(); k += 2)
                    if (moves[i]+moves[j]+moves[k] == 15)
                        return true;
        for (int n = 1; n <= 9; n++)
            if (find(moves.begin(),moves.end(),n) == moves.end()) {
                vector<int> newMoves(moves);
                newMoves.push_back(n);
                if (isWin(newMoves, !isPatron))
                    return false;
            }
        return true;
    }
};

2009-09-06

CaptureThemAll

| 19:09

問題文, SRM 207

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

Knightだけで、RookとQueenをとるのに最低何ステップかかるか。BFSで解ける。どのように実装すればよいのかで迷った。1回目と2回目に出したときは、setを使って同じ条件の時にはもう調べないようにしなかったために、queueの許容量を超えてしまい、例外が発生して落ちた(例外が発生しなくても時間制限に引っかかったと思うが)。

300.00/1000 (2 failed)

struct State {
    const static int ROOK_VAL = 1;
    const static int QUEEN_VAL = 10;
    const static int BOTH_VAL = ROOK_VAL+QUEEN_VAL;
    pair<int,int> p;
    int step, val;
    State() {}
    State(const pair<int,int> p) : p(p) {
        step = 0;
        val = 0;
    }
    State(const pair<int,int> p, const int step) : p(p), step(step) {
        val = 0;
    }
};
bool operator< (const State& a, const State& b) {
    if (a.step < b.step) {
        return true;
    } else if (a.step > b.step) {
        return false;
    } else {
        if (a.val > b.val) {
            return true;
        } else if (a.val < b.val) {
            return false;
        } else {
            return a.p < b.p;
        }
    }
}

class CaptureThemAll {
public:
    int fastKnight(string knight, string rook, string queen) {
        const pair<int,int> rPos = getPos(rook);
        const pair<int,int> qPos = getPos(queen);
        queue<State> Q;
        Q.push(State(getPos(knight)));
        set<State> checked;
        checked.insert(Q.front());
        while (!Q.empty()) {
            State k = Q.front(); Q.pop();
            if (k.val == State::BOTH_VAL) return k.step;
            for (int dy = -2; dy <= 2; dy++) {
                for (int dx = -2; dx <= 2; dx++) {
                    if (dy*dy+dx*dx != 5) continue;
                    const int ny = k.p.first + dy;
                    const int nx = k.p.second + dx;
                    if (0<=ny&&ny<BOARD_SZ && 0<=nx&&nx<BOARD_SZ) {
                        State next(make_pair(ny,nx), k.step+1);
                        if (k.val%10 == 1 || next.p == rPos) 
                            next.val += State::ROOK_VAL;
                        if (k.val/10 == 1 || next.p == qPos)
                            next.val += State::QUEEN_VAL;
                        if (checked.find(next) == checked.end()) {
                            Q.push(next);
                            checked.insert(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
private:
    const static int BOARD_SZ = 8;
    pair<int,int> getPos(const string& s) {
        return make_pair(s[1]-'1', s[0]-'a');
    }
};

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-07-26

HourGlass

| 11:16

問題文

2つの砂時計を使って測れる時間を求める。Brute-forceで解ける問題だけど、どういう状態を調べれば解けるのかがわからなかった。慣れるしかないか。

class HourGlass {
public:
    vector <int> measurable(int glass1, int glass2) {
        g1 = glass1;
        g2 = glass2;
        times.clear();
        memo = vector<vector<vector<bool> > >(MAX_POSSIBLE_TIME+1, 
                vector<vector<bool> >(g1+1, vector<bool>(g2+1,false)));
        go(0, 0, 0);
        const static int RETURN_VALUES = 10;
        vector <int> result(RETURN_VALUES);
        set<int>::const_iterator itr = times.begin();
        for (int i = 0; i < RETURN_VALUES; i++) {
            itr++;
            result[i] = *itr;
        }
        return result;
    }
private:
    set<int> times;
    int g1, g2;
    const static int MAX_POSSIBLE_TIME = 500;
    vector<vector<vector<bool> > > memo;
    void go(const int sand1, const int sand2, const int time) {
        if (time > MAX_POSSIBLE_TIME) return;
        if (memo[time][sand1][sand2]) return;
        memo[time][sand1][sand2] = true;
        times.insert(time);
        if (sand1==0 || sand2==0) {
            go(g1-sand1, sand2, time);
            go(sand1, g2-sand2, time);
            go(g1-sand1, g2-sand2, time);
        }
        if (sand1>0 && sand2==0) go(0, 0, time+sand1);
        if (sand2>0 && sand1==0) go(0, 0, time+sand2);
        if (sand1>0 && sand2>0) {
            int minSand = min(sand1, sand2);
            go(sand1-minSand, sand2-minSand, time+minSand);
        }
    }
};

GuessTheNumber

| 09:09

問題文

数字を推測。問題文の疑似コードを実装するだけ。

class GuessTheNumber {
public:
    int noGuesses(int upper, int answer) {
        int no = 1;
        int lower = 1;
        while (true) {
            int guess = (lower+upper) / 2;
            if (guess == answer) return no;
            else if (guess < answer) lower = guess+1;
            else if (guess > answer) upper = guess-1; 
            no++;
        }
        return -1;
    }
};

2009-05-04

MNS

| 06:13

問題文

541.75->986.47 / 1000

全ケースを試す方法で解けた。

class MNS {
public:
    int combos(vector <int> numbers) {
        sort(numbers.begin(), numbers.end());
        int counter = 0;
        do {
            const static int d[6][3] = {
                { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 },
                { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 } };
            const int sum = numbers[0] + numbers[1] + numbers[2];
            for (int i = 1; i < 6; i++) {
                if (sum != (numbers[d[i][0]]+numbers[d[i][1]]+numbers[d[i][2]])) {
                    break;
                } else if (i == 5) {
                    counter++;
                    break;
                }
            }
        } while (next_permutation(numbers.begin(), numbers.end()));
        return counter;
    }
};

2009-05-02

BridgeCrossing

| 18:09

問題文

456.12->950.72->985.42 / 1000

わからなくて Editorial を見た。Brute force な方法で解ける。

class BridgeCrossing {
public:
    int minTime(vector <int> times) {
        n = times.size();
        if (n == 1)
            return times[0];
        int best = 9999999;
        vector<bool> side(n, false);
        go(times, 0, n, side, best);
        return best;
    }
private:
    int n;
    void go(const vector<int>& times, const int tm, const int left,
            vector<bool>& side, int& best) {
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!side[i] && !side[j]) {
                    side[i] = side[j] = true;
                    int new_tm = tm + max(times[i],times[j]);
                    if (left == 2) {
                        best = min(best, new_tm);
                    } else {
                        for (int k = 0; k < n; k++) {
                            if (side[k]) {
                                side[k] = false;
                                go(times, new_tm+times[k], left-1,
                                        side, best);
                                side[k] = true;
                            }
                        }
                    }
                    side[i] = side[j] = false;
                }
            }
        }
    }
};