Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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-22

Fifteen

| 07:35

問題文, SRM 172

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

言った数の内、3つの数の合計が15になったら勝ちのゲームにおいて、挑戦者(patron)が勝てるかどうか。TutorialにTick-Tack-Toeの変装だと書かれていたので、どのように解くか考えたが、少し強引な方法しか考えつかなかった。

204.31/500

class Fifteen {
public:
    string outcome(vector <int> moves) {
        for (int n = 1; n <= 9; n++) {
            if (find(moves.begin(),moves.end(),n) == moves.end()) {
                vector<int> newMoves(moves);
                newMoves.push_back(n);
                if (isWin(newMoves, true)) {
                    char res[10];
                    sprintf(res, "WIN %d", n);
                    return string(res);
                }
            }
        }
        return "LOSE";
    }
private:
    bool isWin(const vector<int>& moves, const bool isPatron) {
        for (int i = isPatron? 1:0; i < moves.size(); i += 2)
            for (int j = i+2; j < moves.size(); j += 2)
                for (int k = j+2; k < moves.size(); k += 2)
                    if (moves[i]+moves[j]+moves[k] == 15)
                        return true;
        for (int n = 1; n <= 9; n++)
            if (find(moves.begin(),moves.end(),n) == moves.end()) {
                vector<int> newMoves(moves);
                newMoves.push_back(n);
                if (isWin(newMoves, !isPatron))
                    return false;
            }
        return true;
    }
};

2009-09-13

grafixMask

| 14:18

問題文, SRM 211

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

マスクしていない部分の面積。Flood fill。

351.71/500

class grafixMask {
public:
    vector <int> sortedAreas(vector <string> rectangles) {
        const static int H = 400, W = 600;
        char canvas[H][W];
        memset(canvas, ' ', H*W);
        for (int i = 0; i < rectangles.size(); i++) {
            int r0, c0, r1, c1;
            sscanf(rectangles[i].c_str(), "%d %d %d %d", &r0, &c0, &r1, &c1);
            for (int r = r0; r <= r1; r++)
                for (int c = c0; c <= c1; c++)
                    canvas[r][c] = '#';
        }

        vector<int> areas;
        for (int r = 0; r < H; r++)
            for (int c = 0; c < W; c++) {
                if (canvas[r][c] == '#') continue;
                canvas[r][c] = '#';
                int area = 1;
                queue<pair<int,int> > Q;
                Q.push(make_pair(r, c));
                while (!Q.empty()) {
                    pair<int,int> p(Q.front()); Q.pop();
                    for (int i = 0; i < 4; i++) {
                        const static int d[4][2] = {
                            {1,0}, {-1,0}, {0,1}, {0,-1} };
                        const int nr = p.first + d[i][0];
                        const int nc = p.second + d[i][1];
                        if (0<=nr&&nr<H && 0<=nc&&nc<W && canvas[nr][nc] != '#') {
                            canvas[nr][nc] = '#';
                            Q.push(make_pair(nr,nc));
                            area++;
                        }
                    }
                }
                areas.push_back(area);
            }
        sort(areas.begin(), areas.end());
        return areas;
    }
};

2009-08-24

StripePainter

| 13:03

問題文, SRM 150

最低何回ペンキを塗りつける必要があるか。DP+メモ化で解ける問題。

224.12/500

class StripePainter {
public:
    int minStrokes(string stripes) {
        const int size = stripes.size();
        memo = vector<vector<vector<int> > >(size,vector<vector<int> >(size+1,vector<int>(128,-1)));
        return go(stripes, 0, size, '?');
    }
private:
    vector<vector<vector<int> > > memo;
    int go(const string& stripes, 
            const int left, const int size, const char color) {
        if (size <= 0) return 0;
        if (memo[left][size][color] >= 0) return memo[left][size][color];
        int best = INT_MAX;
        if (stripes[left] == color) {
            best = go(stripes, left+1, size-1, color);
        } else {
            for (int i = 1; i <= size; i++) 
                best = min(best, 1
                        + go(stripes,left+1,i-1,stripes[left])
                        + go(stripes,left+i,size-i,color));
        }
        memo[left][size][color] = best;
        return best;
    }
};

2009-08-07

ShortPalindromes

| 12:58

問題文

与えられた文字列から作られる、最も短くて、辞書順で最初にくる回文を作れ、という問題。再帰+メモ化によって時間内に解ける問題。わからなくてEditorialを見た。思いつきそうでつかない解法だな。こういう問題は慣れれば解けるようになると思った。

572.72/1150 - 00:38:45 (cheated)

class ShortPalindromes {
    public:
        string shortest(string base) {
            memo.clear();
            return go(base);
        }
    private:
        map<string,string> memo;
        string go(const string& s) {
            if (memo.find(s) != memo.end()) 
                return memo[s];
            if (isPalindrome(s)) 
                return s;
            const int len = s.length();
            string ret;
            if (s[0] == s[len-1]) {
                ret = string(1,s[0]) + go(s.substr(1,len-2)) + string(1,s[0]);
            } else {
                ret = minStr(string(1,s[0]) + go(s.substr(1,len-1)) + string(1,s[0]),
                        string(1,s[len-1]) + go(s.substr(0,len-1)) + string(1,s[len-1]));
            }
            memo[s] = ret;
            return ret;
        }
        bool isPalindrome(const string& s) {
            const int len = s.length();
            for (int i = 0; i < len/2; i++)
                if (s[i] != s[len-i-1])
                    return false;
            return true;
        }
        string minStr(const string& a, const string& b) {
            if (a.length() < b.length()) {
                return a;
            } else if (a.length() > b.length()) {
                return b;
            } else if (a < b) {
                return a;
            } else {
                return b;
            }
        }
};

2009-07-26

HourGlass

| 11:16

問題文

2つの砂時計を使って測れる時間を求める。Brute-forceで解ける問題だけど、どういう状態を調べれば解けるのかがわからなかった。慣れるしかないか。

class HourGlass {
public:
    vector <int> measurable(int glass1, int glass2) {
        g1 = glass1;
        g2 = glass2;
        times.clear();
        memo = vector<vector<vector<bool> > >(MAX_POSSIBLE_TIME+1, 
                vector<vector<bool> >(g1+1, vector<bool>(g2+1,false)));
        go(0, 0, 0);
        const static int RETURN_VALUES = 10;
        vector <int> result(RETURN_VALUES);
        set<int>::const_iterator itr = times.begin();
        for (int i = 0; i < RETURN_VALUES; i++) {
            itr++;
            result[i] = *itr;
        }
        return result;
    }
private:
    set<int> times;
    int g1, g2;
    const static int MAX_POSSIBLE_TIME = 500;
    vector<vector<vector<bool> > > memo;
    void go(const int sand1, const int sand2, const int time) {
        if (time > MAX_POSSIBLE_TIME) return;
        if (memo[time][sand1][sand2]) return;
        memo[time][sand1][sand2] = true;
        times.insert(time);
        if (sand1==0 || sand2==0) {
            go(g1-sand1, sand2, time);
            go(sand1, g2-sand2, time);
            go(g1-sand1, g2-sand2, time);
        }
        if (sand1>0 && sand2==0) go(0, 0, time+sand1);
        if (sand2>0 && sand1==0) go(0, 0, time+sand2);
        if (sand1>0 && sand2>0) {
            int minSand = min(sand1, sand2);
            go(sand1-minSand, sand2-minSand, time+minSand);
        }
    }
};

2009-05-04

MNS

| 06:13

問題文

541.75->986.47 / 1000

全ケースを試す方法で解けた。

class MNS {
public:
    int combos(vector <int> numbers) {
        sort(numbers.begin(), numbers.end());
        int counter = 0;
        do {
            const static int d[6][3] = {
                { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 },
                { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 } };
            const int sum = numbers[0] + numbers[1] + numbers[2];
            for (int i = 1; i < 6; i++) {
                if (sum != (numbers[d[i][0]]+numbers[d[i][1]]+numbers[d[i][2]])) {
                    break;
                } else if (i == 5) {
                    counter++;
                    break;
                }
            }
        } while (next_permutation(numbers.begin(), numbers.end()));
        return counter;
    }
};

2009-05-02

BridgeCrossing

| 18:09

問題文

456.12->950.72->985.42 / 1000

わからなくて Editorial を見た。Brute force な方法で解ける。

class BridgeCrossing {
public:
    int minTime(vector <int> times) {
        n = times.size();
        if (n == 1)
            return times[0];
        int best = 9999999;
        vector<bool> side(n, false);
        go(times, 0, n, side, best);
        return best;
    }
private:
    int n;
    void go(const vector<int>& times, const int tm, const int left,
            vector<bool>& side, int& best) {
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!side[i] && !side[j]) {
                    side[i] = side[j] = true;
                    int new_tm = tm + max(times[i],times[j]);
                    if (left == 2) {
                        best = min(best, new_tm);
                    } else {
                        for (int k = 0; k < n; k++) {
                            if (side[k]) {
                                side[k] = false;
                                go(times, new_tm+times[k], left-1,
                                        side, best);
                                side[k] = true;
                            }
                        }
                    }
                    side[i] = side[j] = false;
                }
            }
        }
    }
};