Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-07

ParallelSpeedup

| 19:21

問題文

何基のコンピュータを使って、並列処理させた場合が一番速いのかを求める。

388.73/500 - 00:16:33

class ParallelSpeedup {
    public:
        int numProcessors(int k, int overhead) {
            long long minTime = k;
            for (int p = 2; p <= k; p++) {
                const long long time = overhead*calcCommCount(p) 
                    + static_cast<long long>(ceil(static_cast<double>(k)/p));
                if (time >= minTime) 
                    return p-1;
                minTime = time;
            }
            return k;
        }
    private:
        long long calcCommCount(const int p) {
            return static_cast<long long>(p) * (p-1) / 2;
        }
};

2009-08-06

PartySeats

| 19:16

問題文 PartySeats

席順決め。

class PartySeats {
    public:
        vector <string> seating (vector <string> attendees) {
            multiset<string> boys, girls;
            for (int i = 0; i < attendees.size(); i++) {
                string name, gender;
                istringstream iss(attendees[i]);
                iss >> name >> gender;
                if (gender[0] == 'b') boys.insert(name);
                else girls.insert(name);
            }
            vector<string> result;
            if (boys.size() != girls.size() || boys.size()%2 == 1)
                return result;
            multiset<string>::const_iterator bItr = boys.begin();
            multiset<string>::const_iterator gItr = girls.begin();
            result.push_back("HOST");
            for (int i = 0; i < attendees.size()/2; i += 2) {
                result.push_back(*gItr); gItr++;
                result.push_back(*bItr); bItr++;
            }
            result.push_back("HOSTESS");
            for (int i = attendees.size()/2; i < attendees.size(); i += 2) {
                result.push_back(*bItr); bItr++;
                result.push_back(*gItr); gItr++;
            }
            return result;
        }
};

NathalieadsonNathalieadson2012/07/10 00:48Unparaellled accuracy, unequivocal clarity, and undeniable importance!

qumvofqumvof2012/07/10 15:55k9l8Kn <a href="http://ffbnrpylucxq.com/">ffbnrpylucxq</a>

kxvfpogrvtkxvfpogrvt2012/07/10 21:52DUrnSr , [url=http://odqnuvepnfcs.com/]odqnuvepnfcs[/url], [link=http://gllexsagvhok.com/]gllexsagvhok[/link], http://ctntvviqpnwt.com/

ahphkwegfjvahphkwegfjv2012/07/12 12:12jHPHB5 <a href="http://wujnvnxoozdt.com/">wujnvnxoozdt</a>

2009-08-05

CalendarRecycle

| 19:09

問題文

次にカレンダーを使いまわせる年を求める。

class CalendarRecycle {
    public:
        int useAgain(int year) {
            int day = 0;
            const pair<bool,int> yearPair = make_pair(isLeapYear(year),day);
            for (int y = year+1; ; y++) {
                if (isLeapYear(y-1)) day = (day+366) % 7;
                else day = (day+365) % 7;
                if (yearPair == make_pair(isLeapYear(y),day))
                    return y;
            }
            return -1;
        }
    private:
        bool isLeapYear(const int year) {
            return (year%4 == 0 && year%100 != 0) || year%400 == 0;
        }
};

2009-07-28

StreetParking

| 18:25

問題文

道に駐車できるかどうか。

class StreetParking {
public:
    int freeParks(string street) {
        const int len = street.length();
        int total = 0;
        for (int i = 0; i < len; i++) {
            if (street[i] != '-') continue;
            if (i+2 < len && street[i+2]=='B') continue;
            if (i+1 < len && 
                (street[i+1]=='B'||street[i+1]=='S')) continue;
            if (i-1 >= 0 && street[i-1]=='S') continue;
            total++;
        }
        return total;
    }
};

2009-07-26

Gems

| 19:52

ボード中の2つの隣接する宝石を入れ替えた時に、3つ以上宝石が並ぶかどうか。自力で解けると思って実装したが、重複して数えてしまってうまくいかず、結局Editorialを見た。

class Gems {
public:
    int numMoves(vector <string> board) {
        int moves = 0;
        const static int d[DIR_KINDS][2] = {
            { 0, 1}, { 1, 0}, { 0,-1}, {-1, 0} };
        const int h=board.size(), w=board[0].length();
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                const char gem = board[y][x];
                for (int i = 0; i < DIR_KINDS/2; i++) {
                    const int dy = y + d[i][0];
                    const int dx = x + d[i][1];
                    if (!isInRage(dy,dx,h,w)) continue;
                    if (gem == board[dy][dx]) continue;
                    if (isAligned(gem,dy,dx,i,board,h,w) ||
                      isAligned(board[dy][dx],y,x,i+DIR_KINDS/2,board,h,w)) {
                        moves++;
                    }
                }
            }
        }
        return moves;
    }
private:
    const static int DIR_KINDS = 4;
    bool isInRage(const int y, const int x, const int h, const int w) {
        return 0<=y&&y<h && 0<=x&&x<w;
    }
    bool isAligned(const char gem, const int dy, const int dx, const int dir,
              const vector<string>& board, const int h, const int w) {
        const static int CHECK_KINDS = 4;
        const static int check[DIR_KINDS][CHECK_KINDS][2][2] = {
            { {{-1, 0},{ 1, 0}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}} },
            { {{-1, 0},{ 1, 0}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}} } };
        for (int j = 0; j < CHECK_KINDS; j++) {
            for (int k = 0; k < 2; k++) {
                const int cy = dy + check[dir][j][k][0];
                const int cx = dx + check[dir][j][k][1];
                if (!isInRage(cy,cx,h,w)) break;
                if (gem != board[cy][cx]) break;
                if (k == 2-1) return true;
            }
        }
        return false;
    }
};

BaseMystery

| 09:14

問題文

n進数を採用したとき、等式を満たすかどうか。見落としが多く、2回システムテストで落とされ、3回目で通った。

class BaseMystery {
public:
    vector <int> getBase(string equation) {
        vector <int> result;
        vector<string> nums(3); 
        nums[0] = string(equation.begin(), 
                find(equation.begin(),equation.end(),'+'));
        nums[1] = string(equation.begin()+nums[0].length()+1, 
            find(equation.begin()+nums[0].length()+1,equation.end(),'='));
        nums[2] = string(equation.begin()+nums[0].length()+nums[1].length()+2,
                equation.end());
        int maxDigit = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < nums[i].length(); j++) {
                maxDigit = max(maxDigit, getIntDigit(nums[i][j]));
            }
        }
        for (int p = max(2,maxDigit+1); p <= 20; p++) {
            if (toBase10(nums[0],p)+toBase10(nums[1],p)
                                    == toBase10(nums[2],p))
                result.push_back(p);
        }
        return result;
    }
private:
    int getIntDigit(const char c) {
        if (isdigit(c)) return c - '0';
        else return 10 + c - 'A';
    }
    int toBase10(const string& s, const int p) {
        int d = 0;
        for (int i = 0; i < s.length(); i++) {
            d *= p;
            d += getIntDigit(s[i]);
        }
        return d;
    }
};

TireRotation

| 09:14

問題文

タイヤを長持ちさせるために、タイヤをローテートするときの法則にcurrentが従っているかどうか。問題文の書き出しに難しそうな印象を受けたが、問題はタイヤが4つの場合だけなので簡単だった。

class TireRotation {
public:
    int getCycle(string initial, string current) {
        const static int CHAR_LONG = 4;
        const static int rot[CHAR_LONG] = { 2, 3, 1, 0 };
        vector<string> pattern(CHAR_LONG, initial);
        for (int cycle = 1; cycle < CHAR_LONG; cycle++) {
            if (current == pattern[cycle-1]) return cycle;
            for (int i = 0; i < CHAR_LONG; i++) {
                pattern[cycle][rot[i]] = pattern[cycle-1][i];
            }
        }
        if (current == pattern[CHAR_LONG-1]) return CHAR_LONG;
        else return -1;
    }
};

2009-07-25

BombSweeper

| 05:47

問題文

ゲームの勝率を求める。

class BombSweeper {
public:
    double winPercentage(vector <string> board) {
        const int height = board.size();
        const int width = board[0].length();
        const static int DIR_KINDS = 8;
        const int d[DIR_KINDS][2] = {
            {-1,-1}, {-1, 0}, {-1, 1},
            { 0,-1},          { 0, 1},
            { 1,-1}, { 1, 0}, { 1, 1} };

        int wins=0, loses=0;
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (board[y][x] == 'B') {
                    loses++;
                    continue;
                }
                for (int i = 0; i < DIR_KINDS; i++) {
                    const int dy = y + d[i][0];
                    const int dx = x + d[i][1];
                    if (0<=dy&&dy<height && 0<=dx&&dx<width) {
                        if (board[dy][dx] == 'B') break;
                    }
                    if (i == DIR_KINDS-1) wins++;
                }
            }
        }
        const double percentage = 100.0l * wins / (wins+loses); 
        return percentage;
    }
};

2009-05-02

Yahtzee

| 11:48

問題文

245.61->249.76 / 250

極めて簡単な問題。

class YahtzeeScore {
public:
    int maxPoints(vector <int> toss) {
        vector<int> sum(7, 0);
        for (int i = 0; i < toss.size(); i++)
            sum[toss[i]] += toss[i];
        return *max_element(sum.begin(), sum.end());
    }
};

2009-04-30

DitherCounter

| 21:36

問題文

207.35->249.12 / 250

問題文がわかりにくいなと思ったが、screen 中に dithered に含まれる文字が何個含まれているかを数えるだけの問題だった。

class ImageDithering {
public:
    int count(string dithered, vector <string> screen) {
        vector<bool> check(256, false);
        for (int i = 0; i < dithered.length(); i++)
            check[dithered[i]] = true;

        int counter = 0;
        for (int i = 0; i < screen.size(); i++)
            for (int j = 0; j < screen[0].length(); j++)
                if (check[screen[i][j]])
                    counter++;
        return counter;
    }
};