Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

NoOrderOfOperations

| 12:44

問題文, SRM 200

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

式を左から右に評価。

243.45/250

class NoOrderOfOperations {
public:
    int evaluate(string expr) {
        int result = expr[0]-'0';
        for (int i = 1; i < expr.length(); i += 2) {
            switch (expr[i]) {
                case '+':
                    result += expr[i+1]-'0';
                    break;
                case '-':
                    result -= expr[i+1]-'0';
                    break;
                case '*':
                    result *= expr[i+1]-'0';
                    break;
            }
        }
        return result;
    }
};

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-09-01

| 17:45

問題文, SRM 203

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

使用可能なユーザ名を返す。

242.00/250

class UserName {
public:
    string newMember(vector <string> existingNames, string newName) {
        if (find(existingNames.begin(),existingNames.end(),newName) 
                == existingNames.end())
            return newName;
        for (int i = 1; ; i++) {
            ostringstream nameoss;
            nameoss << newName << i;
            if (find(existingNames.begin(),existingNames.end(),nameoss.str())
                    == existingNames.end())
                return nameoss.str();
        }
        return "";
    }
};

Stairs

| 13:15

問題文, SRM 177

与えられた条件の階段は何種類作れるか。問題の意味を理解するのに時間がかかった。内側のループは必要ない、ということに他の方のコードを見て気がついた。

177.45/250

class Stairs {
public:
    int designs(int maxHeight, int minWidth, int totalHeight, int totalWidth) {
        int designs = 0;
        for (int h = maxHeight; h >= 1; h--) {
            if (totalHeight%h == 0) {
                int parts = totalHeight/h - 1;
                if (parts == 0) continue;
                for (int w = minWidth; ; w++) {
                    int width = w * parts;
                    if (width > totalWidth) break;
                    if (width == totalWidth) 
                        designs++;
                }

            }
        }
        return designs;
    }
};

MitchellMitchell2011/07/11 00:05Big help, big help. And superlative news of crouse.

veiutvcwcveiutvcwc2011/07/11 02:29TlCswI <a href="http://vjnggvexbwuu.com/">vjnggvexbwuu</a>

zoksriviopzoksriviop2011/07/11 21:51epdS5v , [url=http://gqqjyfaqwssc.com/]gqqjyfaqwssc[/url], [link=http://mbceaafjqxom.com/]mbceaafjqxom[/link], http://qzkaecclvamc.com/

ntetzpntetzp2011/07/13 18:23bYD1yS <a href="http://bgyraruehckt.com/">bgyraruehckt</a>

mxixglmxixgl2011/07/14 00:35GtzmkZ , [url=http://mxgzmwjlggpm.com/]mxgzmwjlggpm[/url], [link=http://xraideylozrg.com/]xraideylozrg[/link], http://jcutzvphyqwn.com/

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

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

CrossWord

| 17:29

問題文, SRM 174

size個だけ連続した横方向の空白が、いくつあるのかを数える。

230.35/250

class CrossWord {
public:
    int countWords(vector <string> board, int size) {
        int count = 0;
        string pat(size, '.');
        pat = "X" + pat + "X";
        for (int i = 0; i < board.size(); i++) {
            board[i] = "X" + board[i] + "X";
            int idx = 0;
            while ((idx = board[i].find(pat,idx)) != string::npos) {
                count++;
                idx += size + 1;
            }
        }
        return count;
    }
};