Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

HourGlass

| 11:16

問題文

2つの砂時計を使って測れる時間を求める。Brute-forceで解ける問題だけど、どういう状態を調べれば解けるのかがわからなかった。慣れるしかないか。

class HourGlass {
public:
    vector <int> measurable(int glass1, int glass2) {
        g1 = glass1;
        g2 = glass2;
        times.clear();
        memo = vector<vector<vector<bool> > >(MAX_POSSIBLE_TIME+1, 
                vector<vector<bool> >(g1+1, vector<bool>(g2+1,false)));
        go(0, 0, 0);
        const static int RETURN_VALUES = 10;
        vector <int> result(RETURN_VALUES);
        set<int>::const_iterator itr = times.begin();
        for (int i = 0; i < RETURN_VALUES; i++) {
            itr++;
            result[i] = *itr;
        }
        return result;
    }
private:
    set<int> times;
    int g1, g2;
    const static int MAX_POSSIBLE_TIME = 500;
    vector<vector<vector<bool> > > memo;
    void go(const int sand1, const int sand2, const int time) {
        if (time > MAX_POSSIBLE_TIME) return;
        if (memo[time][sand1][sand2]) return;
        memo[time][sand1][sand2] = true;
        times.insert(time);
        if (sand1==0 || sand2==0) {
            go(g1-sand1, sand2, time);
            go(sand1, g2-sand2, time);
            go(g1-sand1, g2-sand2, time);
        }
        if (sand1>0 && sand2==0) go(0, 0, time+sand1);
        if (sand2>0 && sand1==0) go(0, 0, time+sand2);
        if (sand1>0 && sand2>0) {
            int minSand = min(sand1, sand2);
            go(sand1-minSand, sand2-minSand, time+minSand);
        }
    }
};

Salary

| 09:09

問題文

給料を計算。

class Salary {
public:
    int howMuch(vector <string> arrival, vector <string> departure, int wage) {
        double amount = 0;
        for (int i = 0; i < arrival.size(); i++) {
            const static int NIGHT_END = calcTime(6, 0, 0);
            const static int EVENING_START = calcTime(18, 0, 0);
            const static double SEC_PER_HOUR = 60 * 60;
            int hh, mm, ss;
            sscanf(arrival[i].c_str(), "%d:%d:%d", &hh, &mm, &ss);
            int aTime = calcTime(hh, mm, ss);
            sscanf(departure[i].c_str(), "%d:%d:%d", &hh, &mm, &ss);
            int dTime = calcTime(hh, mm, ss);
            if (aTime < NIGHT_END) {
                if (dTime < NIGHT_END) {
                    amount += 1.5 * wage * (dTime-aTime)/SEC_PER_HOUR;
                    dTime = aTime;
                } else {
                    amount += 1.5 * wage * (NIGHT_END-aTime)/SEC_PER_HOUR;
                    aTime = NIGHT_END;
                }
            }
            if (dTime > EVENING_START) {
                if (aTime >= EVENING_START) {
                    amount += 1.5 * wage * (dTime-aTime)/SEC_PER_HOUR;
                    aTime = dTime;
                } else {
                    amount += 1.5 * wage * (dTime-EVENING_START)/SEC_PER_HOUR;
                    dTime = EVENING_START;
                }
            }
            amount += wage * (dTime-aTime)/SEC_PER_HOUR;
        }
        return static_cast<int>(floor(amount));
    }
private:
    int calcTime(const int h, const int m, const int s) {
        return (h*60 + m) * 60 + s;
    }
};

GuessTheNumber

| 09:09

問題文

数字を推測。問題文の疑似コードを実装するだけ。

class GuessTheNumber {
public:
    int noGuesses(int upper, int answer) {
        int no = 1;
        int lower = 1;
        while (true) {
            int guess = (lower+upper) / 2;
            if (guess == answer) return no;
            else if (guess < answer) lower = guess+1;
            else if (guess > answer) upper = guess-1; 
            no++;
        }
        return -1;
    }
};