TopCoderの問題を解く

Jumper

SRM 158, Div1, Div1 Level-3, Search, Algorithm Tutorials, cheated, 30% | 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;
    }
};

HillHike

SRM 145, Div1, Div1 Level-3, Dynamic Programming, cheated, 45% | 14:33

問題文

採りえる山の形の数を求める。問題は理解できたが、解法が全然思いつかなかった。

470.68/1000

class HillHike {
    public:
        long long numPaths(int distance, int maxHeight, vector <int> landmarks) {
            long long memory[2][52][51];
            memset(memory, 0, sizeof(memory));
            memory[0][0][0] = 1;
            landmarks.push_back(-1);
            for (int i = 1; i < distance; i++) {
                long long cache[2][52][51];
                memset(cache, 0, sizeof(memory));
                for (int h = 1; h <= maxHeight; h++) {
                    int mh = (h == maxHeight) ? 1 : 0;
                    for (int j = 0; j < landmarks.size(); j++)
                        for (int d = -1; d <= 1; d++) {
                            int lm = (h == landmarks[j]) ? j+1 : j;
                            cache[mh][h][lm] += memory[0][h+d][j];
                            cache[ 1][h][lm] += memory[1][h+d][j];
                        }
                }
                memcpy(memory, cache, sizeof(memory));
            }
            return memory[1][1][landmarks.size()-1];
        }
};