Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-17

LargestCircle

| 19:05

問題文, SRM 212

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

マークされたマスを通らない円を描くとき、描くことができる最大の円の半径を求める。円がマスを通るかどうかの判定をどのように実装すればいいのかわからなかった。

428.44/1000 (cheated)

int square(const int x) { return x * x; }

class LargestCircle {
public:
    int radius(vector <string> grid) {
        const int H = grid.size();
        const int W = grid[0].size();
        for (int rad = min(H/2,W/2); rad >= 1; rad--) {
            const int sr = square(rad);
            for (int cy = rad; cy <= H-rad; cy++)
                for (int cx = rad; cx <= W-rad; cx++) {
                    bool passed = true;
                    for (int y = 0; y < H; y++) {
                        for (int x = 0; x < W; x++) {
                            if (grid[y][x] != '#') continue;
                            const int dy = y - cy;
                            const int dx = x - cx;
                            const int p0 = square(dy)   + square(dx);
                            const int p1 = square(dy+1) + square(dx);
                            const int p2 = square(dy)   + square(dx+1);
                            const int p3 = square(dy+1) + square(dx+1);
                            if (p0<=sr && p1<=sr && p2<=sr && p3<=sr) continue;
                            if (p0>=sr && p1>=sr && p2>=sr && p3>=sr) continue;
                            passed = false;
                            break;
                        }
                        if (!passed) break;
                    }
                    if (passed) return rad;
                }
        }
        return 0;
    }
};

2009-08-08

ConvexPolygon

| 13:23

このDIV2の問題セットは簡単だった。

問題文

凸多角形の面積を求めるだけ。解法を調べながら解いたために、時間がかかった。計算幾何の勉強をする必要がある。

576.16/900 - 00:25:12

class ConvexPolygon {
    public:
        double findArea(vector <int> x, vector <int> y) {
            double area = 0;
            for (int i = 0; i+1 < x.size(); i++) {
                int x0 = x[i] - x[0];
                int y0 = y[i] - y[0];
                int x1 = x[i+1] - x[0];
                int y1 = y[i+1] - y[0];
                int cross = x0*y1 - x1*y0;
                area += cross;
            }
            return fabs(area/2);
        }
};

ewnfzgewnfzg2011/02/28 00:358HHlV6 <a href="http://nfypkepkeych.com/">nfypkepkeych</a>, [url=http://azgnisbcmhab.com/]azgnisbcmhab[/url], [link=http://jedmlehhrowo.com/]jedmlehhrowo[/link], http://pqvizwthqdkq.com/

2009-08-01

Intersect

| 18:34

問題文

全ての矩形に囲まれる矩形の面積を求める。

class Intersect {
public:
    int area(vector <int> x, vector <int> y) {
        int left =INT_MIN, right=INT_MAX;
        int upper=INT_MIN, lower=INT_MAX;
        for (int i = 0; i < x.size(); i += 2) {
            if (x[i] > x[i+1]) swap(x[i], x[i+1]);
            if (y[i] > y[i+1]) swap(y[i], y[i+1]);
            left  = max(left, x[i]);
            right = min(right, x[i+1]);
            upper = max(upper, y[i]);
            lower = min(lower, y[i+1]);
        }
        if ((right-left) <= 0 || (lower-upper) <= 0) return 0;
        else return (right-left) * (lower-upper);
    }
};

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

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>