Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-10

TheCardShufflingDivTwo

| 22:38

問題文, SRM 448

カードを並べ替えたときに、一番に上にくるのは何か。変換テーブルを作って求めた。もう少し考えて、法則性があるかどうかを検討した方が、提出までの時間を短縮できたと思う。

266.46/500

class TheCardShufflingDivTwo {
public:
    int shuffle(int n, int m) {
        vector<int> L((int)ceil((double)n/2));
        vector<int> R(n/2);
        for (int i = 0; i < n/2; i++) {
            L[i] = 2*i+1;
            R[i] = 2*i+2;
        }
        if (n%2 == 1) L[n/2] = n;
        vector<int> table(n+1);
        for (int i = L.size()-1; i >= 0; i--)
            table[R.size()+i+1] = L[i];
        for (int i = R.size()-1; i >= 0; i--)
            table[i+1] = R[i];

        int top = 1;
        for (int i = 0; i < m; i++)
            top = table[top];
        return top;
    }
};

TheBlackJackDivTwo

| 22:32

Level-1は簡単で、すぐに解けた。Level-2は少し時間がかかったけど解けた。ChallengeはLevel-2の解答で2重ループ使っている方がいたので、それを落とした。Ratingは増加(1081->1158)。もう少しでDiv1。

問題文, SRM 448

カードの数の和。

245.23/250

class TheBlackJackDivTwo {
public:
    int score(vector <string> cards) {
        int result = 0;
        for (int i = 0; i < cards.size(); i++) {
            if ('2' <= cards[i][0] && cards[i][0] <= '9')
                result += cards[i][0] - '0';
            else if ('A' == cards[i][0])
                result += 11;
            else
                result += 10;
        }
        return result;
    }
};

WalkingHome

| 16:29

問題文, SRM 222

Algorithm Tutorials -- How to Find a Solutionから。

学校から家に帰るまでに、最低何回道路を横断すればよいのか。道路は2つまでしか横断できないと勘違いしたために、1回落ちた。

150.00/500 (1 failed)

struct Johnny {
    int y, x, times;
    Johnny() { Johnny(0,0,0); }
    Johnny(const int y, const int x, const int times) :
        y(y), x(x), times(times) {}
};

class WalkingHome {
public:
    int fewestCrossings (vector <string> map) {
        const int H = map.size();
        const int W = map[0].size();
        Q = queue<Johnny>();
        visited = vector<vector<int> >(H, vector<int>(W, INT_MAX));
        int homeY=0, homeX=0;
        for (int y = 0; y < H; y++) {
            // cout << map[y]<< endl;
            for (int x = 0; x < W; x++) {
                if (map[y][x] == 'S') {
                    checkAndPush(Johnny(y,x,0));
                } else if (map[y][x] == 'H') {
                    homeY = y;
                    homeX = x;
                    map[y][x] = '.';
                }
            }
        }

        int result = INT_MAX;
        while (!Q.empty()) {
            Johnny j(Q.front());  Q.pop();
            if (j.y == homeY && j.x == homeX)
                result = min(result, j.times);
            const static int d[4][2] = {
                {1,0}, {-1,0}, {0,1}, {0,-1} };
            for (int i = 0; i < 4; i++) {
                const int ny = j.y + d[i][0];
                const int nx = j.x + d[i][1];
                int nnx, nny;
                if (!(0<=ny&&ny<H && 0<=nx&&nx<W)) continue;
                switch (map[ny][nx]) {
                    case '.':
                        checkAndPush(Johnny(ny,nx,j.times));
                        break;
                    case '|':
                        if (d[i][1] == 0) break;
                        nnx = nx + d[i][1];
                        while (0<=nnx&&nnx<W && map[ny][nnx] == '|')
                            nnx += d[i][1];
                        if (0<=nnx&&nnx<W && map[ny][nnx] == '.')
                            checkAndPush(Johnny(ny,nnx,j.times+1));
                        break;
                    case '-':
                        if (d[i][0] == 0) break;
                        nny = ny + d[i][0];
                        while (0<=nny&&nny<H && map[nny][nx] == '-')
                            nny += d[i][0];
                        if (0<=nny&&nny<H && map[nny][nx] == '.')
                            checkAndPush(Johnny(nny,nx,j.times+1));
                        break;
                }

            }
        }
        if (result == INT_MAX) return -1;
        else return result;
    }
private:
    queue<Johnny> Q;
    vector<vector<int> > visited;
    void checkAndPush(const Johnny& j) {
        if (j.times < visited[j.y][j.x]) {
            Q.push(j);
            visited[j.y][j.x] = j.times;
        }
    }
};

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/caligue/20090910