Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

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

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/