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

TheBlackJackDivTwo

| 22:32

Level-1は簡単で、すぐに解けた。Level-2は少し時間がかかったけど解けた。ChallengeはLevel-2の解答で2重ループ使っている方がいたので、それを落とした。Ratingは増加(1081->1158)。もう少しでDiv1。

問題文, SRM 448

カードの数の和。

245.23/250

class TheBlackJackDivTwo {
public:
    int score(vector <string> cards) {
        int result = 0;
        for (int i = 0; i < cards.size(); i++) {
            if ('2' <= cards[i][0] && cards[i][0] <= '9')
                result += cards[i][0] - '0';
            else if ('A' == cards[i][0])
                result += 11;
            else
                result += 10;
        }
        return result;
    }
};

2009-08-26

ImportantTasks

| 14:09

Level-1は、比較的スムースに解けたが、Level-2は問題の意図を理解し間違えたため、解けなかった。Ratingは微減(1100->1081)。

問題文, SRM 447

最大何個のタスクを処理することができるか。

230.20/250

class ImportantTasks {
public:
    int maximalCost(vector <int> complexity, vector <int> computers) {
        sort(complexity.rbegin(), complexity.rend());
        sort(computers.rbegin(), computers.rend());
        int tasks = 0;
        int i = 0, j = 0;
        while (i < complexity.size() && j < computers.size()) {
            if (complexity[i] <= computers[j]) {
                tasks++;
                i++; j++;
            } else {
                i++;
            }
        }
        return tasks;
    }
};

WelcomeWelcome2011/09/01 00:19I was seroiulsy at DefCon 5 until I saw this post.

xcwzlbzzzqxcwzlbzzzq2011/09/02 16:148TE9sS <a href="http://rpjeaawsdcmb.com/">rpjeaawsdcmb</a>

eigjincydeigjincyd2011/09/02 21:26TMEB5D , [url=http://pxvfxgiatbjw.com/]pxvfxgiatbjw[/url], [link=http://gcpkduewkcfg.com/]gcpkduewkcfg[/link], http://xawthkldnhbn.com/

cvvyposcvvypos2011/09/03 19:54CW44Qv <a href="http://qnydwuhvacqh.com/">qnydwuhvacqh</a>