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/

2010-01-31

OnLineRank

| 22:32

問題文, SRM 179

成績のランクを直前の k 人の成績の中でランクで計算するとき、そのランクの合計を求める。その通りに実装すればいい。Editorial を読んで気づいたが、rank 変数は作らずとも sum のインクリメントだけで充分だった。

235.88/250

class OnLineRank {
public:
    int calcRanks(int k, vector <int> scores) {
        int sum = 1;
        for (int i = 1; i < scores.size(); i++) {
            int rank = 1;
            for (int j = max(0,i-k); j < i; j++) {
                if (scores[j] > scores[i])
                    rank++;
            }
            sum += rank;
        }
        return sum;
    }
};

MateoMateo2013/02/17 22:51Inteillgence and simplicity - easy to understand how you think.

schgrzschgrz2013/02/19 00:42foexv7 <a href="http://krsawktetuoo.com/">krsawktetuoo</a>

ixdtrsrixdtrsr2013/02/21 12:375pdlI9 <a href="http://vmkqxxlmsxmu.com/">vmkqxxlmsxmu</a>

ixdtrsrixdtrsr2013/02/21 12:375pdlI9 <a href="http://vmkqxxlmsxmu.com/">vmkqxxlmsxmu</a>

oaxixvwpreuoaxixvwpreu2013/02/21 17:01OpAgB8 , [url=http://wexmtjdpiwje.com/]wexmtjdpiwje[/url], [link=http://loprselolouh.com/]loprselolouh[/link], http://eeikflgzlhwl.com/

2010-01-29

SimpleCalculator

| 19:13

久しぶりに解いた。最近解いてなかったのは英語力の強化を重視していて、英語力が充分ついてから解くのを再開しようかと思っていたから。しかし、思ったよりも時間がかかりそうで(頑張っても1年はかかる)、問題を解く感覚が鈍りそうなので、1日1時間程度をアルゴリズム系の問題を解く時間かそのための勉強に当てようと思います。1時間だと難しめの問題を解くのは時間的に厳しいので、解く問題はDiv2のLevel-1,2とDiv1のLevel-1の問題を中心にします。

問題文, SRM 178

四則演算だけのシンプルな計算機。今度からはしっかり解説を付けたいなと思ったのに、何も語ることがない。この問題はどのように入力値を文字列から得るかだと思うが、それも istringstream か sscanf を使えば実現できるので、やはり語ることがない。

248.39/250

class SimpleCalculator {
public:
    int calculate(string input) {
        int a, b;
        char c;
        istringstream(input) >> a >> c >> b;
        if (c == '+') return a + b;
        else if (c == '-') return a - b;
        else if (c == '*') return a * b;
        else return a / b;
    }
};

MaheshMahesh2012/11/14 15:48Furrealz? That's marovelusly good to know.

mrmqezkqxwmrmqezkqxw2012/11/15 11:52s6bK06 <a href="http://gcchvukbnzox.com/">gcchvukbnzox</a>

spsrxxspsrxx2012/11/16 10:14TvaJTu , [url=http://eciyaqdchfxo.com/]eciyaqdchfxo[/url], [link=http://ttwirdzyever.com/]ttwirdzyever[/link], http://mnxmkjngbida.com/

lewoklxfgxlewoklxfgx2012/11/17 00:38yuecsC <a href="http://lqhnazvgbvem.com/">lqhnazvgbvem</a>

gflffsgflffs2012/11/17 10:45N1Z2Z1 , [url=http://vngcyqvvvmgl.com/]vngcyqvvvmgl[/url], [link=http://dkarqzmcxylp.com/]dkarqzmcxylp[/link], http://zzwhaounqels.com/

2009-11-06

EggCartons

| 06:31

SRM 452 Div2は250,500を解けて、674.40点。Division rankは76位で、比較的よかった。1000の問題は30分以上あまっていたけど、解法が思いつかなかったので早々に諦めた。Ratingは 1120 から 1187 に上がった。Challenge phaseに真面目に参加して、Challengeを一回でも成功させていればDiv1に昇格できていたかもしれない。


問題文, SRM 452

卵が6個入ったパックと8個が入ったパックがあるとき、指定された数の卵を買うには最低何パック買えばいいのか。

問題を読んだときにナップサック問題みたいだなと思ったので、DPで解いた。他の方の回答を見ると 8i+6j=n を満たす i,j を調べている方が多かった。

238.04/250

class EggCartons {
public:
    int minCartons(int n) {
        if (n < 6) return -1;
        vector<int> v(n+1, -1);
        v[0] = 0;
        for (int w = 0; w <= n; w++) {
            if (w >= 8 && v[w-8] != -1) v[w] = 1 + v[w-8];
            else if (w >= 6 && v[w-6] != -1) v[w] = 1 + v[w-6];
        }
        return v[n];
    }
};

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