Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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-05-11

BrickByBrick

| 20:58

問題文

479.40->1045.11 / 1100

ブロック崩しをシミュレート。実装力が問われる問題。

class BrickByBrick {
public:
    int timeToClear(vector <string> map) {
        int r = map.size();
        int c = map[0].size();
        vector<string> m(r+2, string(c+2,'#'));
        int remain = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                m[i+1][j+1] = map[i][j];
                if (map[i][j] == 'B')
                    remain++;
            }
        }

        int counter = 0;
        int idle = 0;
        int x=1, y=1, dx=1, dy=1;
        while (remain > 0 && idle < 514) {
            if (m[y][x+dx] == '.') {
                x += dx;
            } else if (m[y][x+dx] == 'B') {
                remain--, m[y][x+dx]='.', dx*=-1, idle=0;
            } else {
                dx *= -1;
            }
            counter++;
            if (remain == 0) break;

            if (m[y+dy][x] == '.') {
                y += dy;
            } else if (m[y+dy][x] == 'B') {
                remain--, m[y+dy][x]='.', dy*=-1, idle=0;
            } else {
                dy *= -1;
            }
            counter++;
            idle++;
        }

        return (remain > 0) ? -1 : counter;
    }
};

InterestingDigits

| 18:51

問題文

251.51->499.03

説明が面倒なので無し。

class InterestingDigits {
public:
    vector <int> digits(int base) {
        vector <int> result;
        for (int d = 2; d < base; d++) {
            if (isInterestingDigit(base, d))
                result.push_back(d);
        }
        return result;
    }
private:
    bool isInterestingDigit(const int base, const int d) {
        return base%d == 1;
    }
};

WidgetRepairs

| 18:51

問題文

229.90->249.41 / 250

何日働く必要があるのかを求める。

class WidgetRepairs {
public:
    int days(vector <int> arrivals, int numPerDay) {
        int days = 0;
        int remain = 0;
        for (int i = 0; i < arrivals.size(); i++) {
            remain += arrivals[i];
            if (remain > 0)
                days++;
            remain = max(0, remain-numPerDay);
        }
        if (remain > 0)
            days += (remain-1)/numPerDay + 1;
        return days;
    }
};

MissyMissy2011/07/22 16:09Now I know who the brainy one is, I'll keep looknig for your posts.

zrwuybrcsgozrwuybrcsgo2011/07/23 22:08xDBJGa , [url=http://ngbsklytunqc.com/]ngbsklytunqc[/url], [link=http://olpwwtwjhupr.com/]olpwwtwjhupr[/link], http://vfyjnrgeopbs.com/

qbqmjjqbqmjj2011/07/24 21:58F1VCcA <a href="http://iyopswirddsc.com/">iyopswirddsc</a>