Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-08

Orchard

| 20:44

SRM447 (DIV2)の結果は、300と500を通すことができ、Ratingは 1063 -> 1099 と上がった。両問題とももう少し速くサブミットできたのだが、コードを何度も確認していたため、しょぼいポイントになった。慎重になりすぎた。

問題文

幅優先探索(BFS)で解ける問題。実装に手間取った。

328.06/900 - 01:03:38

enum INDEX { Y_IDX=0, X_IDX=1, DIS_IDX=2};

class Orchard {
    public:
        vector <int> nextTree(vector <string> orchard) {
            const int size = orchard.size();
            vector<int> best = vector<int>(2);
            int longest = -1;
            for (int y = 0; y < size; y++) 
                for (int x = 0; x < size; x++)
                    if (orchard[y][x] == '-') {
                        set<vector<int> > visited;
                        queue<vector<int> > Q;
                        vector<int> tmp(3);
                        tmp[Y_IDX]=y; tmp[X_IDX]=x; tmp[DIS_IDX] = 0;
                        Q.push(tmp);
                        while (!Q.empty()) {
                            vector<int> v = Q.front(); Q.pop();
                            if (v[Y_IDX] < 0 || v[Y_IDX] >= size ||
                                    v[X_IDX] < 0 || v[X_IDX] >= size ||
                                    orchard[v[Y_IDX]][v[X_IDX]] == 'T') {
                                if (v[DIS_IDX] > longest) {
                                    longest = v[DIS_IDX];
                                    best[Y_IDX] = y + 1;
                                    best[X_IDX] = x + 1;
                                }
                                break;
                            }
                            tmp = vector<int>(v.begin(), v.begin()+2);
                            if (visited.find(tmp) != visited.end()) continue;
                            visited.insert(tmp);
                            vector<int> newV(3); 
                            newV[DIS_IDX] = v[DIS_IDX] + 1;
                            newV[Y_IDX]=v[Y_IDX]+1; newV[X_IDX]=v[X_IDX]; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]-1; newV[X_IDX]=v[X_IDX]; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]; newV[X_IDX]=v[X_IDX]+1; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]; newV[X_IDX]=v[X_IDX]-1; Q.push(newV);
                        }
                    }
            return best;
        }
};

Animation

| 19:40

問題文

粒子の動き。強引に解きすぎて、バグが増え、時間がかかった。

150.00/500 - 00:57:22

class Animation {
    public:
        vector <string> animate(int speed, string init) {
            const int len = init.length();
            const static char RIGHT = '1';
            const static char LEFT = '2';
            string pre(init);
            for (int i = 0; i < len; i++) {
                if (pre[i] == 'R') pre[i] = RIGHT;
                else if (pre[i] == 'L') pre[i] = LEFT;
                else pre[i] = 0;
            }
            vector <string> result;
            while (true) {
                string s(toX(pre));
                result.push_back(s);
                if (find(s.begin(),s.end(),'X') == s.end())
                    break;
                s = string(len, 0);
                for (int i = 0; i < len; i++) {
                    int d;
                    switch (pre[i]) {
                    case RIGHT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        break;
                    case LEFT:
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    case RIGHT+LEFT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    }
                }
                pre = s;
            }
            return result;
        }
    private:
        string toX(const string& s) {
            string ret(s.length(), '.');
            for (int i = 0; i < s.length(); i++)
                if (s[i] != 0)
                    ret[i] = 'X';
            return ret;
        }
};

EyeDrops

| 19:36

問題文

目薬をする最適な間隔を求める。DIV2のeasyにしては難しい問題。すぐには解法が思いつかなかったが、Examplesを見て、2種類のケースが考えられることがわかり、解けた。

238.97/300

class EyeDrops {
    public:
        double closest(int sleepTime, int k) {
            double dk = static_cast<double>(k);
            if (sleepTime <= 24/dk)
                return 24*60/dk;
            else
                return (24-sleepTime)*60/(dk-1);
        }
};

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

BinaryCardinality

| 19:29

問題文

立っているビット数が少ない順にソート。300の問題よりこっちの方が解きやすかった。提出した後に気づいたことだけど、比較関数の中でbitsetを使えば、余計なvector配列を使う必要がないな。

453.99/500 - 00:09:18

bool compBinary(const bitset<32>& a, const bitset<32>& b)
{
    if (a.count() < b.count()) {
        return true;
    } else if (a.count() > b.count()) {
        return false;
    } else {
        return a.to_ulong() < b.to_ulong();
    }
}

class BinaryCardinality {
    public:
        vector <int> arrange(vector <int> numbers) {
            const int size = numbers.size();
            vector<bitset<32> > binaries(size);
            for (int i = 0; i < size; i++)
                binaries[i] = numbers[i];
            sort(binaries.begin(), binaries.end(), compBinary);
            vector <int> result(size);
            for (int i = 0; i < size; i++)
                result[i] = static_cast<int>(binaries[i].to_ulong());
            return result;
        }
};

Workshop

| 19:29

問題文

作れる三角形の数を数える。

267.09/300 - 00:10:38

class Workshop {
    public:
        int pictureFrames(vector <int> pieces) {
            int result = 0;
            sort(pieces.begin(), pieces.end());
            const int size = pieces.size();
            for (int i = 0; i < size-2; i++) {
                for (int j = i+1; j < size-1; j++) {
                    for (int k = j+1; k < size; k++) {
                        if (pieces[i]<pieces[j]+pieces[k] &&
                                pieces[j]<pieces[i]+pieces[k] &&
                                pieces[k]<pieces[i]+pieces[j])
                            result++;
                    }
                }
            }
            return result;
        }
};

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

ゲスト



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