Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

TopographicalImage

| 19:19

問題文, SRM 210

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

各頂上から上らずに到達することができる地点の数を数える。ただし、同じ地点は数えない。

390.67/1000

class TopographicalImage {
public:
    vector <int> calcPeakAreas(vector <string> topoData) {
        H = topoData.size();
        W = topoData[0].size();
        result.clear();
        while (true) {
            int mx=0, my=0;
            char mh=0;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (topoData[y][x] != VISITED && topoData[y][x] > mh) {
                        my = y;
                        mx = x;
                        mh = topoData[y][x];
                    }
                }
            if (mh == 0) break;
            result.push_back(0);
            visit(my, mx, mh, topoData);
        }
        return result;
    }
private:
    const static char VISITED = 127;
    int H, W;
    vector <int> result;
    void visit(const int py, const int px, const char ph, 
            vector<string>& topoData) {
        result.back()++;
        topoData[py][px] = VISITED;
        for (int dy = -1; dy <= 1; dy++)
            for (int dx = -1; dx <= 1; dx++) {
                if (dy == 0 && dx == 0) continue;
                const int ny = py + dy;
                const int nx = px + dx;
                if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                    const int nh = topoData[ny][nx];
                    if (nh <= ph)
                        visit(ny, nx, nh, topoData);
                }
            }
    }
};

2009-10-06

Rounder

| 19:38

問題文, SRM 195

整数 n と b が与えられたとき、n を b の倍数の中で最も近い数に丸めよ。

244.95/250

class Rounder {
public:
    int round(int n, int b) {
        int r = n / b;
        int l = r * b;
        int h = (r+1) * b;
        if (h-n <= n-l) return h;
        else return l;
    }
};

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

MassiveNumbers

| 20:07

SRM 236, 問題文

どっちの数が大きいか。

227.54/250

class MassiveNumbers {
public:
    string getLargest(string numberA, string numberB) {
        double m = getNum(numberA);
        double n = getNum(numberB);
        return (m > n) ? numberA : numberB;
    }
private:
    double getNum(const string& num) {
        double x, y;
        sscanf(num.c_str(), "%lf^%lf", &x, &y);
        return y * log10(x);
    }
};

CindyCindy2011/08/30 03:53This airtlce went ahead and made my day.

mdemxwxbqmdemxwxbq2011/08/30 17:43Zd89Ez <a href="http://fqdhttbozbbl.com/">fqdhttbozbbl</a>

cdffsucdffsu2011/09/01 16:14krcrX4 , [url=http://wlwbmerglolk.com/]wlwbmerglolk[/url], [link=http://ifpjtmfiwmtu.com/]ifpjtmfiwmtu[/link], http://naygcnbbnajf.com/

glfkghywcuglfkghywcu2011/09/04 01:35tQqNlZ , [url=http://gdtojpngtbre.com/]gdtojpngtbre[/url], [link=http://imxqbkfrlcqs.com/]imxqbkfrlcqs[/link], http://skhdkbgwnwib.com/

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

SoldierLabeling

| 11:03

問題文, SRM 446

lowerBound から upperBound の間の桁数の数がラベルされている軍人だけを数えるき、数えるであろう兵隊の数を返せ。

この問題は以前にも解いた問題で、その時は187.99点だった。今回はというと、少し手間取ったが、前回よりは高い点を獲得できた。

200.03/250

class SoldierLabeling {
public:
    int count(int n, int lowerBound, int upperBound) {
        int count = n;
        int lower = (int)pow(10.0, lowerBound-1) - 1;
        int upper = (int)pow(10.0, upperBound) - 1;
        count -= lower;
        if (count < 0) return 0;
        if (upper <= n) count -= n - upper;
        return count;
    }
};

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

MountainRoad

| 07:16

SRM 449 Div2は一問も解けず。操作ミスで500の問題から開いてしまったので、500の問題から解き始めたが、45分考えても、解法が浮かばなかった。250も単純な問題なのに、焦りと眠気からか解けなかった。どちらも若干苦手な数学の問題だった。Mathカテゴリの問題でもまとめて解こうかな。Ratingは1158から1074へと下がった。

問題文, SRM 449

左端と右端だけが重要な問題だった。時間内には解けなかったが、寝て起きたら解法が思いついた。

class MountainRoad {
public:
    double findDistance(vector <int> start, vector <int> finish) {
        double l = *min_element(start.begin(), start.end());
        double r = *max_element(finish.begin(), finish.end());
        return (r-l) * sqrt(2);
    }
};

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

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