Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-05

Jumper

| 19:49

問題文, SRM 158

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

一番上までいくのに何ステップかかるか。BFSで解ける。問題を理解するのに1時間。そして、解法が浮かばなくてEditorialを見ながら解くのに2時間ぐらいかかった。

304.01/1000 (cheated)

struct State {
    int x, y, t;
    State() {}
    State(const int x, const int y, const int t) :
        x(x), y(y), t(t) {}
};
bool operator< (const State& a, const State& b) {
    if (a.t < b.t) {
        return true;
    } else if (a.t > b.t) {
        return false;
    } else {
        if (a.y > b.y) {
            return true;
        } else if (a.y < b.y) {
            return false;
        } else {
            return a.x < b.x;
        }
    }
}

class Jumper {
public:
    int minTime(vector <string> patterns, vector <int> speeds, string rows) {
        const int HEIGHT = rows.size()+1;
        const int WIDTH = 20;
        vector<string> grid(HEIGHT+1);
        grid[0] = grid[HEIGHT] = string(WIDTH, '#');
        for (int i = 0; i < rows.size(); i++) 
            for (int j = 0; j < 4; j++)
                grid[i+1] += patterns[rows[i]-'0'];
        queue<State> Q;
        Q.push(State(0,0,0));
        set<State> checked;
        while (!Q.empty()) {
            State s = Q.front(); Q.pop();
            if (s.t > 2100) break;
            if (s.y >= HEIGHT) return s.t;
            const static int MOVE_KINDS = 5;
            const static int d[MOVE_KINDS][2] = {
                {0,0},{1,0},{-1,0},{0,1},{0,-1} };
            for (int i = 0; i < MOVE_KINDS; i++) {
                const int dx = s.x + d[i][0];
                const int dy = s.y + d[i][1];
                if (0<=dx&&dx<WIDTH && 0<=dy) {
                    int offset = (dy==0||dy==HEIGHT) ? 0 : 
                        (((-s.t*speeds[rows[dy-1]-'0'])%5)+5)%5;
                    if (grid[dy][(dx+offset)%WIDTH] == '#') {
                        const int ddx = dx + ((dy==0||dy==HEIGHT)? 0 :
                                speeds[rows[dy-1]-'0']);
                        if (0<=ddx && ddx<WIDTH) {
                            State next(ddx, dy, s.t+1);
                            if (checked.find(next) == checked.end()) {
                                checked.insert(next);
                                Q.push(next);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
};

2009-08-31

StampPads

| 13:51

問題文, SRM 158

欲しい色を全部そろえるには、何種類のスタンプパッドを買えば良いのか。Brute forceで解ける問題だったが、DPで解こうとした。2回タイムアウトで落とされたが、始めにmaskを作る方法に変えたら通った。

150.00/500 (2 failed)

class StampPads {
public:
    int bestCombo(vector <string> pads, vector <string> wishlist) {
        numPads = pads.size();
        pds = vector<vector<string> >(numPads, vector<string>(5));
        for (int i = 0; i < numPads; i++) {
            istringstream iss(pads[i]);
            for (int j = 0; iss >> pds[i][j]; j++) ;
        }
        bitset<32> got;
        numWishes = wishlist.size();
        wishL = wishlist;
        mask = vector<bitset<32> >(numPads);
        for (int i = 0; i < numPads; i++)
            for (int j = 0; j < numWishes; j++)
                mask[i][j] = find(pds[i].begin(),pds[i].end(),wishL[j]) != pds[i].end();
        return go(0, 0, got);
    }
    int numPads;
    vector<vector<string> > pds;
    vector<string> wishL;
    vector<bitset<32> > mask;
    int numWishes;
    int go(const int bought, const int idx, const bitset<32>& got) {
        if (got.count() >= numWishes) return bought;
        if (idx >= numPads) return -1;
        bitset<32> next(got | mask[idx]);
        if (next != got) {
            int retBuy = go(bought+1, idx+1, next);
            int retNot = go(bought, idx+1, got);
            if (retBuy == -1 && retNot == -1) return -1;
            else if (retBuy == -1) return retNot;
            else if (retNot == -1) return retBuy;
            else return min(retBuy, retNot);
        } else {
            return go(bought, idx+1, got);
        }
    }
};

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