Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-25

TeamPhoto

| 20:54

問題文, SRM 167

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

写真を撮る際に、身長の差の合計が最も小さくなるような並び方を考える。

232.95/750 (cheated)

class TeamPhoto {
public:
    int minDiff(vector <int> height) {
        n = height.size();
        vector<int> mem(height.begin()+3, height.end());
        sort(mem.begin(), mem.end());
        m = mem.size();

        int minSum = calc(height, mem, m/2);
        if (n%2 == 0)
            minSum = min(minSum, calc(height, mem, m/2+1));
        return minSum;
    }
private:
    int n, m;
    int calc(vector<int>& ht, vector<int>& mem, int mid) {
        return min(diff(ht[1], mem[0], mem[mid-1], ht[0]) +
                     diff(ht[0], mem[mid], mem[m-1], ht[2]),
                   diff(ht[2], mem[0], mem[mid-1], ht[0]) +
                     diff(ht[0], mem[mid], mem[m-1], ht[1]));
    }
    int diff(int a, int l, int h, int b) {
        return h-l + min(abs(a-l)+abs(b-h), abs(a-h)+abs(b-l));
    }
}

JohnieJohnie2013/02/16 22:15Check that off the list of things I was cofnsued about.

lpzworxlpzworx2013/02/17 21:13EhdvUV <a href="http://lggmfstpruis.com/">lggmfstpruis</a>

kdwdegjekdwdegje2013/02/18 05:09QCIf4X , [url=http://nxklzrjfqokk.com/]nxklzrjfqokk[/url], [link=http://iopulhzspqez.com/]iopulhzspqez[/link], http://vwnoyqhqksel.com/

kfuflfxdkfuflfxd2013/02/19 19:10JRh8jp , [url=http://ybazmifswqhs.com/]ybazmifswqhs[/url], [link=http://ceackqdzvvcl.com/]ceackqdzvvcl[/link], http://smwogahevohi.com/

2009-08-28

Collision

| 13:32

問題文, SRM 153

2つの確率の差を求める。

178.38/450 (cheated)

class Collision {
public:
    double probability(vector <int> assignments, int ids) {
        double p1=1, p2=1;
        int d = ids;
        for (int i = 0; i < assignments.size(); i++) {
            if (assignments[i] > ids) return 0;
            int n = ids;
            for (int j = 0; j < assignments[i]; j++) {
                p1 *= (double) d / ids;
                p2 *= (double) d / n;
                d--; n--;
            }
        }
        return p2 - p1;
    }
};

2009-08-13

Lottery

| 15:42

問題文

DIV1の問題を解き始めることにした。この問題から、1問につき1エントリを書く。過去のエントリも近いうちに1問1エントリに変える。

数字を使ったギャンブルで、勝率が高い順に並べる。組み合わせの問題で、解けそうと思いコードを書き始めたが、結局わからなくなり、Editorialを見た。

181.27 / 500 - 01:53:07

bool compValidTicketsNum(const pair<string,long long>& a,
        const pair<string,long long>& b) {
    if (a.second < b.second) {
        return true;
    } else if (a.second > b.second) {
        return false;
    } else {
        return a.first < b.first;
    }
}

class Lottery {
    public:
        vector <string> sortByOdds(vector <string> rules) {
            const int size = rules.size();
            vector <string> result(size);
            if (size == 0) return result;
            vector <pair<string,long long> > name(size);
            vector<int> choices(size), blanks(size);
            for (int i = 0; i < size; i++) {
                int p = find(rules[i].begin(),rules[i].end(),':') - rules[i].begin();
                name[i].first = rules[i].substr(0, p);
                istringstream iss(rules[i].substr(p+1));
                int choices, blanks;
                string sorted, unique;
                iss >> choices >> blanks >> sorted >> unique;
                if (sorted == "F" && unique == "F") {
                    name[i].second = power(choices, blanks);
                } else if (sorted == "T" && unique == "F") {
                    name[i].second = combination(choices+blanks-1, blanks);
                } else if (sorted == "F" && unique == "T") {
                    name[i].second = combination(choices, blanks) * factorial(blanks);
                } else if (sorted == "T" && unique == "T") {
                    name[i].second = combination(choices, blanks);
                }
            }
            stable_sort(name.begin(), name.end(), compValidTicketsNum);
            for (int i = 0; i < size; i++)
                result[i] = name[i].first;
            return result;
        }
    private:
        long long power(const long long x, long long y) {
            long long ret = 1;
            while (y-- > 0) ret *= x;
            return ret;
        }
        long long factorial(long long x) {
            long long ret = 1;
            while (x > 0) {
                ret *= x;
                x--;
            }
            return ret;
        }
        long long combination(long long x, long long y) {
            long long ret = 1;
            for (int i = 0; i < y; i++) {
                ret *= x;
                x--;
            }
            while (y > 1) {
                ret /= y;
                y--;
            }
            return ret;
        }
};

2009-05-03

GoldenChain

| 14:33

問題文

368.07->948.061 / 950

問題の意味がよくわからない。チートした。

class GoldenChain {
public:
    int minCuts(vector <int> sections) {
        sort(sections.begin(), sections.end());
        int cuts = 0;
        int i = 0;
        while (cuts < sections.size()-i) {
            cuts++;
            sections[i]--;
            if (sections[i] == 0)
                i++;
        }
        return cuts;
    }
};

ljgwenjuqljgwenjuq2011/02/28 11:40tFpXps <a href="http://cnqanfqzjpsf.com/">cnqanfqzjpsf</a>, [url=http://ecxrxcimgfag.com/]ecxrxcimgfag[/url], [link=http://buchmiybjeag.com/]buchmiybjeag[/link], http://qsgnzwnfmeyn.com/

NalerneNalerne2012/07/09 23:11That's a sharp way of tihnikng about it.

sgpszksgpszk2012/07/10 15:50uVoDFm <a href="http://zcpgsuoedxnr.com/">zcpgsuoedxnr</a>

nkfxqknkfxqk2012/07/10 21:46Oe4QRT , [url=http://mkqciqvhhsmq.com/]mkqciqvhhsmq[/url], [link=http://ljixvhzrjcar.com/]ljixvhzrjcar[/link], http://hxxtbrctakiz.com/

zqmlzhnitzuzqmlzhnitzu2012/07/12 12:05jEMaC7 <a href="http://cxlnhmsvwfmv.com/">cxlnhmsvwfmv</a>

xavvxxpsxavvxxps2012/07/12 17:37XLQaD8 , [url=http://xjwqjiilrtmr.com/]xjwqjiilrtmr[/url], [link=http://wibefrqdjint.com/]wibefrqdjint[/link], http://kgupbzwtdngh.com/