Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-11-03

MazeWanderingEasy

| 19:01

問題文, SRM 440

ねずみが最短でチーズに到達するために必要な決断の回数を求める。BFS。

387.83/500

struct State {
    int y, x, dec;
    State() {}
    State(int y, int x, int dec) : y(y), x(x), dec(dec) {}
};

class MazeWanderingEasy {
public:
    int decisions(vector <string> maze) {
        const int H = maze.size();
        const int W = maze[0].size();
        queue<State> Q;
        for (int y = 0; y < H; y++)
            for (int x = 0; x < W; x++) {
                if (maze[y][x] == 'M') {
                    Q.push(State(y,x,0));
                    maze[y][x] = 'X';
                    break;
                }
                if (!Q.empty()) break;
            }
        while (!Q.empty()) {
            State s(Q.front()); Q.pop();
            vector<State> candid;
            for (int i = 0; i < 4; i++) {
                const static int d[4][2] = {
                    {0,1}, {0,-1}, {1,0}, {-1,0} };
                const int ny = s.y + d[i][0];
                const int nx = s.x + d[i][1];
                if (0<=ny&&ny<H && 0<=nx&&nx<W && maze[ny][nx] != 'X') {
                    candid.push_back(State(ny,nx,s.dec));
                }
            }
            if (candid.size() >= 2)
                for (int i = 0; i < candid.size(); i++)
                    candid[i].dec++;
            for (int i = 0; i < candid.size(); i++) {
                const int y = candid[i].y;
                const int x = candid[i].x;
                if (maze[y][x] == '*')
                    return candid[i].dec;
                maze[y][x] = 'X';
                Q.push(candid[i]);
            }
        }
        return 0;
    }
};

2009-10-23

PizzaDelivery

| 07:29

問題文, SRM 451

2人の配達人を使って、ピザを配達し終えるのにかかる最短時間を求める。

解くのに2時間強かかった。しょうもないバグにより3回、時間制限により1回、システムテストで落とされた。解法はBFS+Brute Forceなので割と単純だが、異常に調子が良い時でないと本番の時間内にバグなしで解ける気がしない。

300.00/1000 (4-failed)

const static int INFTY = INT_MAX/2;

class PizzaDelivery {
    public:
        int deliverAll(vector <string> terrain) {
            const int H = terrain.size();
            const int W = terrain[0].size();
            vector<pair<int,int> > piza;
            pair<int,int> r;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (terrain[y][x] == 'X') {
                        r = make_pair(y, x);
                    } else if (terrain[y][x] == '$') {
                        piza.push_back(make_pair(y,x));
                    }
                }

            int D[100];
            int T[100][100];
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++)
                    T[y][x] = INFTY;
            T[r.first][r.second] = 0;
            queue<pair<int,int> > Q;
            Q.push(r);
            while (!Q.empty()) {
                pair<int,int> a = Q.front(); Q.pop();
                const int y = a.first, x = a.second;
                const static int d[4][2] = {
                    {0,1}, {0,-1}, {1,0}, {-1,0} };
                for (int i = 0; i < 4; i++) {
                    const int ny = y + d[i][0];
                    const int nx = x + d[i][1];
                    if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                        if (!isdigit(terrain[ny][nx]) || !isdigit(terrain[y][x])) {
                            if (T[y][x]+2 < T[ny][nx]) {
                                T[ny][nx] = T[y][x] + 2;
                                Q.push(make_pair(ny, nx));
                            }
                            continue;
                        }
                        if (abs(terrain[ny][nx]-terrain[y][x]) == 0 && 
                                T[y][x]+1 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 1;
                            Q.push(make_pair(ny, nx));
                        } else if (abs(terrain[ny][nx]-terrain[y][x]) == 1 && 
                                T[y][x]+3 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 3;
                            Q.push(make_pair(ny, nx));
                        }
                    }
                }
            }
            for (int i = 0; i < piza.size(); i++) {
                D[i] = T[piza[i].first][piza[i].second];
                if (D[i] == INFTY) return -1;
            }

            int minTime = INFTY;
            for (int i = 0; i < 1<<(piza.size()-1); i++) {
                bitset<20> pat(i);
                vector<int> vboy1, vboy2;
                for (int j = 0; j < piza.size(); j++) {
                    if (pat[j]) vboy1.push_back(D[j]);
                    else        vboy2.push_back(D[j]);
                }
                int boy1=0, boy2=0;
                if (vboy1.size() > 0)
                    boy1 = 2*accumulate(vboy1.begin(), vboy1.end(), 0) 
                        - *max_element(vboy1.begin(), vboy1.end());
                if (vboy2.size() > 0)
                    boy2 = 2*accumulate(vboy2.begin(), vboy2.end(), 0) 
                        - *max_element(vboy2.begin(), vboy2.end());
                //cout << pat << " " << boy1 << " " << boy2 << endl;
                minTime = min(minTime, max(boy1, boy2));
            }
            return minTime;
        }
};

nphuuejznphuuejz2011/02/28 17:01PX5gMr <a href="http://thxvtmuhvzkh.com/">thxvtmuhvzkh</a>, [url=http://aegsueyzfdwj.com/]aegsueyzfdwj[/url], [link=http://juwwqktqnkxe.com/]juwwqktqnkxe[/link], http://fuvdtrdrrxop.com/

2009-10-12

TopographicalImage

| 19:19

問題文, SRM 210

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

各頂上から上らずに到達することができる地点の数を数える。ただし、同じ地点は数えない。

390.67/1000

class TopographicalImage {
public:
    vector <int> calcPeakAreas(vector <string> topoData) {
        H = topoData.size();
        W = topoData[0].size();
        result.clear();
        while (true) {
            int mx=0, my=0;
            char mh=0;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (topoData[y][x] != VISITED && topoData[y][x] > mh) {
                        my = y;
                        mx = x;
                        mh = topoData[y][x];
                    }
                }
            if (mh == 0) break;
            result.push_back(0);
            visit(my, mx, mh, topoData);
        }
        return result;
    }
private:
    const static char VISITED = 127;
    int H, W;
    vector <int> result;
    void visit(const int py, const int px, const char ph, 
            vector<string>& topoData) {
        result.back()++;
        topoData[py][px] = VISITED;
        for (int dy = -1; dy <= 1; dy++)
            for (int dx = -1; dx <= 1; dx++) {
                if (dy == 0 && dx == 0) continue;
                const int ny = py + dy;
                const int nx = px + dx;
                if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                    const int nh = topoData[ny][nx];
                    if (nh <= ph)
                        visit(ny, nx, nh, topoData);
                }
            }
    }
};

2009-09-21

CityLink

| 20:12

問題文, SRM 170

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

全ての都市をつなげるにはどのぐらいの期間が必要か。Floyd-Warshall法の変形法で解ける。

398.94/550

class CityLink {
public:
    int timeTaken(vector <int> x, vector <int> y) {
        const int n = x.size();
        vector<vector<int> > D(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (x[i] == x[j])
                    D[i][j] = (abs(y[i]-y[j])+1) / 2;
                else if (y[i] == y[j])
                    D[i][j] = (abs(x[i]-x[j])+1) / 2;
                else
                    D[i][j] = max(abs(x[i]-x[j]), abs(y[i]-y[j]));
            }

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    D[i][j] = min(D[i][j], max(D[i][k], D[k][j]));

        int result = 0;
        for (int i = 0; i < n; i++)
            result = max(result, *max_element(D[i].begin(), D[i].end()));
        return result;
    }
};

HonneyHonney2011/08/30 15:59A miunte saved is a minute earned, and this saved hours!

wyemhhwwyemhhw2011/09/01 00:575HxeEE <a href="http://ybnebnwcovjs.com/">ybnebnwcovjs</a>

nibmiiinibmiii2011/09/01 16:45G2F1Yz , [url=http://sawuiwwztonv.com/]sawuiwwztonv[/url], [link=http://afgrzejquery.com/]afgrzejquery[/link], http://qcxtuwjadjsa.com/

yadxlbnejvmyadxlbnejvm2011/09/03 17:37kFklXm <a href="http://cmwvbpywnvnz.com/">cmwvbpywnvnz</a>

miiugpaimiiugpai2011/09/04 02:04wqBYC6 , [url=http://tmkxgkbnxbnf.com/]tmkxgkbnxbnf[/url], [link=http://zmtmrmbpaobv.com/]zmtmrmbpaobv[/link], http://ulmzbcooroqn.com/

IdelIdel2013/02/17 07:36I can aalredy tell that's gonna be super helpful.

2009-09-10

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

2009-09-06

SmartWordToy

| 16:33

問題文, SRM 233

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

startからfinishに禁止された文字列を経由するためにかかる変換回数。BFSで解ける。時間制限がきつかった。

157.45/500 (1 failed)

class SmartWordToy {
public:
    int minPresses(string start, string finish, vector <string> forbid) {
        forbids.clear();
        for (int i = 0; i < forbid.size(); i++) {
            istringstream iss(forbid[i]);
            vector<string> token(WORD_LEN);
            for (int j = 0; j < WORD_LEN; j++)
                iss >> token[j];
            generateForbids(0, 0, token);
        }

        queue<pair<int,int> > Q;
        const int startCode = encode(start);
        const int finishCode = encode(finish);
        Q.push(make_pair(startCode, 0));
        set<int> checked;
        checked.insert(startCode);
        while (!Q.empty()) {
            pair<int,int> p = Q.front(); Q.pop();
            if (p.first == finishCode) return p.second;
            for (int i = 0; i < 4; i++) {
                for (int pad = -1; pad <= 1; pad += 2) {
                    int nextCode(next(p.first, pad, i));
                    if (checked.find(nextCode) == checked.end() && 
                            forbids.find(nextCode) == forbids.end()) {
                        checked.insert(nextCode);
                        Q.push(make_pair(nextCode, p.second+1));
                    }
                }
            }
        }
        return -1;
    }
private:
    set<int> forbids;
    const static int WORD_LEN = 4;
    void generateForbids(const int code, const int idx, const vector<string>& token) {
        if (idx == WORD_LEN) {
            forbids.insert(code);
            return;
        }
        for (int i = 0; i < token[idx].size(); i++)
            generateForbids(code*100+token[idx][i]-'a', idx+1, token);
    }
    int encode(const string& s) {
        int code = 0;
        for (int i = 0; i < WORD_LEN; i++)
            code = 100*code + s[i]-'a';
        return code;
    }
    int next(int code, const int pad, const int i) {
        const static int table[5] = {100*100*100*100,100*100*100,100*100,100,1};
        int v = code % table[i] / table[i+1];
        code -= v * table[i+1];
        v = (v+pad+26) % 26;
        code += v * table[i+1];
        return code;
    }
};

2009-04-04

PowerOutage

| 15:52

問題文

333.10->1010.51

minMinutes = 2*total - farthestDistance

const static int MAX_ELEMENT = 50;
const static int INFTY = 9999999;

class PowerOutage {
public:
    int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength) {
        vector<vector<int> > J(MAX_ELEMENT, vector<int>(MAX_ELEMENT,INFTY));
        int elements = fromJunction.size();
        for (int i = 0; i < elements; i++) {
            J[fromJunction[i]][toJunction[i]] 
                = J[toJunction[i]][fromJunction[i]] = ductLength[i];
        }

        int farthestDis = dijkstra(J);
        int total = accumulate(ductLength.begin(), ductLength.end(), 0);
        int minMinutes = 2*total - farthestDis;
        return minMinutes;
    }

private:
    int dijkstra(const vector<vector<int> >& J) {
        vector<int> D(MAX_ELEMENT);
        for (int i = 1; i < MAX_ELEMENT; i++) {
            D[i] = J[0][i];
        }

        vector<bool> visited(MAX_ELEMENT, false);
        while (true) {
            int minDis = INFTY;
            int minIdx = -1;
            for (int j = 1; j < MAX_ELEMENT; j++) {
                if (!visited[j] && D[j] < minDis) {
                    minDis = D[j];
                    minIdx = j;
                }
            }
            if (minIdx == -1) 
                break;
            visited[minIdx] = true;

            for (int j = 1; j < MAX_ELEMENT; j++) {
                D[j] = min(D[j], minDis+J[minIdx][j]);
            }
        }

        int maxDis = 0;
        for (int i = 0; i < MAX_ELEMENT; i++) {
            if (D[i] != INFTY && D[i] > maxDis)
                maxDis = D[i];
        }
        return maxDis;
    }
};