Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2010-02-07

TheQuestionsAndAnswersDivTwo

| 07:31

たまには参加するかと思って、3ヶ月ぶりにSRMに参戦しました。結果は678.75点で、62位(Div2)。Level-1,-2ともあっさり解けた。Level-3は解けるかもと思って最後まで解こうとしていたが、結局答えが合わなかった。

Rating は 1187 から 1252 に上がり、苦難(?)の1年半を経てようやくDiv1に再昇格できた。Div1でやっていくには微妙な実力だが、また1回で降格してそのままずるずるというのは避けたいな。

-----

問題文, SRM 460

Yes/Noのみのインタビューで、想定された回答の組み合わせは全何種類か。

2のパターン乗で答えが求められる。

239.14/250

class TheQuestionsAndAnswersDivTwo {
public:
    int find(vector <string> questions) {
        set<string> s;
        for (int i = 0; i < questions.size(); i++)
            s.insert(questions[i]);
        return (int)pow(2.0, (double)s.size());
    }
}

nbrrvlwonbrrvlwo2011/02/28 02:021t5XZT <a href="http://zfbmnqbofnfy.com/">zfbmnqbofnfy</a>, [url=http://ahgnwsctjvhh.com/]ahgnwsctjvhh[/url], [link=http://hyvrokviobof.com/]hyvrokviobof[/link], http://mtinuysnserr.com/

EriklesErikles2012/11/14 20:56Heck yeah this is exactly what I nedeed.

wbifcqahpfwbifcqahpf2012/11/15 12:17WIV2s4 <a href="http://fvdiwshhnhfy.com/">fvdiwshhnhfy</a>

bclurpjuqvcbclurpjuqvc2012/11/16 10:42j0qQxV , [url=http://xripkjekfhlk.com/]xripkjekfhlk[/url], [link=http://nqncovdmomdj.com/]nqncovdmomdj[/link], http://wgpfjbkvtjgo.com/

xjkekpxjkekp2012/11/17 11:23Aogh4X <a href="http://tpebktqqllbu.com/">tpebktqqllbu</a>

yxhqrnjctkryxhqrnjctkr2012/11/17 20:59SMxofJ , [url=http://lzrngezmevzk.com/]lzrngezmevzk[/url], [link=http://rqgcqejpucew.com/]rqgcqejpucew[/link], http://ccklhgmvvezl.com/

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

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

GardenHose

| 12:51

問題文, SRM 197

庭の外側からホースを使って水を撒くとき、撒けないプラントは何個か。1回落とされたのは、ホースの長さが庭の長さより長い場合の処理を実装するのを忘れたため。解いた後にEditorialを見たら、撒けた場合にはcontinueし、ループの最後までいってしまったらカウンタを増やすというやり方が紹介されていた。その方法の方がバグを作りにくいな。

173.11/250 (1 failed)

class GardenHose {
public:
    int countDead(int n, int rowDist, int colDist, int hoseDist) {
        if (rowDist*n <= hoseDist || colDist*n <= hoseDist)
            return 0;
        vector<vector<int> > garden(n, vector<int>(n, 'x'));
        for (int i = 0; i < n; i++) {
            for (int j = 0; (j+1)*rowDist <= hoseDist; j++)
                garden[j][i] = garden[n-j-1][i] = 'o';
            for (int j = 0; (j+1)*colDist <= hoseDist; j++)
                garden[i][j] = garden[i][n-j-1] = 'o';
        }
        int result = 0;
        for (int i = 0; i < n; i++)
            result += count(garden[i].begin(), garden[i].end(), 'x');
        return result;
    }
};

2009-09-04

PassingGrade

| 17:21

メイン(?)ブログの方にGoogle Code Jam 2009 - Qualification Roundの参戦記録は書いた。結果は約1時間半で全問解けて、65位。

問題文, SRM 185

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

期末テストで単位を得るためにとらなければならない最低点数を求める。単精度では精度が足りないらしく、落とされた。

204.22/250 (1 failed)

class PassingGrade {
public:
    int pointsNeeded(vector <int> pointsEarned, vector <int> pointsPossible, int finalExam) {
        int totalEarned = accumulate(pointsEarned.begin(), pointsEarned.end(), 0);
        int totalPossible = accumulate(pointsPossible.begin(), pointsPossible.end(), 0) 
            + finalExam;
        int minimum = (int) ceil(0.65l*totalPossible - totalEarned);
        if (minimum > finalExam) return -1;
        else if (minimum < 0) return 0;
        else return minimum;
    }
};

2009-09-02

BettingMoney

| 16:55

問題文, SRM 191

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

229.00/250

class BettingMoney {
public:
    int moneyMade(vector <int> amounts, vector <int> centsPerDollar, int finalResult) {
        int result = 0;
        for (int i = 0; i < amounts.size(); i++) {
            if (i == finalResult) result -= amounts[i] * centsPerDollar[i];
            else result += 100 * amounts[i];
        }
        return result;
    }
};

2009-08-30

RGBColor

| 15:54

問題文, SRM 176

補色を返す。

224.33/250

class RGBColor {
public:
    vector <int> getComplement(vector <int> rgb) {
        vector <int> result(3);
        result[0] = 255 - rgb[0];
        result[1] = 255 - rgb[1];
        result[2] = 255 - rgb[2];
        if (abs(rgb[0]-result[0])<=32 && abs(rgb[1]-result[1])<=32 
                && abs(rgb[2]-result[2])<=32) {
            result[0] = (rgb[0]+128 <= 255) ? rgb[0]+128: rgb[0]-128;
            result[1] = (rgb[1]+128 <= 255) ? rgb[1]+128: rgb[1]-128;
            result[2] = (rgb[2]+128 <= 255) ? rgb[2]+128: rgb[2]-128;
        }
        return result;
    }
};

2009-08-24

ClockWalk

| 17:39

問題文, SRM 175

時計を動かし終わった後は、何時か。テストをしないで出したら、tailの場合の計算で、馬鹿なバグがあり、落とされた。

214.27/250

class ClockWalk {
public:
    int finalPosition(string flips) {
        int hour = 0;
        for (int i = 0; i < flips.size(); i++) {
            if (flips[i] == 'h') hour = (hour + i+1) % 12;
            else  hour = (hour - (i+1) + 120) % 12;
        }
        if (hour == 0) hour = 12;
        return hour;
    }
};

2009-08-20

ProgressBar

| 17:36

問題文, SRM 173

インストール作業の進捗具合を示すプログレス・バーを表示する。

240.19/250

class ProgressBar {
public:
    string showProgress(vector <int> taskTimes, int tasksCompleted) {
        int total = accumulate(taskTimes.begin(), taskTimes.end(), 0);
        int completed = accumulate(taskTimes.begin(), 
                taskTimes.begin()+tasksCompleted, 0);
        double percent = static_cast<double>(completed) / total;
        string progress(20, '.');
        for (int i = 0; i < floor(percent*20); i++)
            progress[i] = '#';
        return progress;
    }
};