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を見た。

][cx]) 

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