Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

ゲスト