Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

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

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/

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

MatArith

| 21:03

問題文, TCI '02 Round 2

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

行列同士の足し算と掛け算。

169.75/500 (1 failed)

typedef long long int64;

class MatArith {
public:
    vector <string> calculate(vector <string> A, vector <string> B, vector <string> C, string equation) {
        return print(calc(parse(A),parse(B),parse(C),equation));
    }
private:
    vector<string> print(vector<vector<int64> > M) {
        const int R = M.size();
        if (R == 0) return vector<string>();
        const int C = M[0].size();
        vector<string> ret(R);
        for (int r = 0; r < R; r++) {
            ostringstream oss;
            for (int c = 0; c < C; c++) {
                if (c >= 1) oss << " ";
                oss << M[r][c];
            }
            ret[r] = oss.str();
        }
        return ret;
    }
    vector<vector<int64> > parse(vector<string>& M) {
        const int R = M.size();
        vector<vector<int64> > ret(R);
        for (int r = 0; r < R; r++) {
            istringstream iss(M[r]);
            int t;
            while (iss >> t) ret[r].push_back(t);
        }
        return ret;
    }
    vector<vector<int64> > calc(const vector<vector<int64> > A,
            const vector<vector<int64> > B, const vector<vector<int64> > C,
            const string& equation) {
        stack<vector<vector<int64> > > matStack;
        int opStack = 0;
        for (int i = 0; i < equation.size(); i++) {
            if (equation[i] == '+') {
                opStack++;
            } else if (equation[i] == '*') {
                vector<vector<int64> > T1 = matStack.top(); matStack.pop();
                i++;
                vector<vector<int64> > T2;
                if (equation[i] == 'A') T2 = A;
                else if (equation[i] == 'B') T2 = B;
                else  T2 = C;
                vector<vector<int64> > M = matmul(T1, T2);
                if (M.size() == 0) return M;
                matStack.push(M);
            } else if (equation[i] == 'A') {
                matStack.push(A);
            } else if (equation[i] == 'B') {
                matStack.push(B);
            } else {
                matStack.push(C);
            }
        }
        while (opStack-- > 0) {
            vector<vector<int64> > T1 = matStack.top(); matStack.pop();
            vector<vector<int64> > T2 = matStack.top(); matStack.pop();
            vector<vector<int64> > M = matadd(T1, T2);
            if (M.size() == 0) return M;
            matStack.push(M);
        }
        return matStack.top();
    }
    vector<vector<int64> > matmul(const vector<vector<int64> >& A,
            const vector<vector<int64> >& B) {
        const int RA = A.size(), CA = A[0].size();
        const int RB = B.size(), CB = B[0].size();
        if (CA != RB) return vector<vector<int64> >();
        vector<vector<int64> > M(RA, vector<int64>(CB,0));
        for (int i = 0; i < RA; i++) {
            for (int j = 0; j < CB; j++) {
                for (int k = 0; k < CA; k++) {
                    M[i][j] += A[i][k] * B[k][j];
                }
                if (M[i][j] > 2147483647ll || M[i][j] < -2147483648ll)
                    return vector<vector<int64> >();
            }
        }
        return M;
    }
    vector<vector<int64> > matadd(const vector<vector<int64> >& A,
            const vector<vector<int64> >& B) {
        const int RA = A.size(), CA = A[0].size();
        const int RB = B.size(), CB = B[0].size();
        if (RA != RB || CA != CB) return vector<vector<int64> >();
        vector<vector<int64> > M(RA, vector<int64>(CA,0));
        for (int i = 0; i < RA; i++) {
            for (int j = 0; j < CA; j++) {
                M[i][j] += A[i][j] + B[i][j];
                if (M[i][j] > 2147483647ll || M[i][j] < -2147483648ll)
                    return vector<vector<int64> >();
            }
        }
        return M;
    }
};

2009-09-05

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

BadClock

| 15:23

問題文, SRM 172

何時間後に2つの時計が同時刻を指すか。

class BadClock {
public:
    double nextAgreement(string trueTime, string skewTime, int hourlyGain) {
        int X = getTime(trueTime);
        int Y = getTime(skewTime);
        if (hourlyGain < 0) {
            hourlyGain = -hourlyGain;
            swap(X, Y);
        }
        while (X < Y) X += 12*60*60;
        return (double) (X - Y) / hourlyGain;
    }
private:
    int getTime(const string& time) {
        int hh, mm, ss;
        sscanf(time.c_str(), "%d:%d:%d", &hh, &mm, &ss);
        return (hh*60 + mm)*60 + ss;
    }
};

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