Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-17

Dragons

| 13:52

問題文, SRM 147

餌の奪い合いをした後に、ボスドラゴンはどれぐらいの餌をもっているのかを求める。1回目に出したときは、結果が0になる場合の処理を実装していなかったため、システムテストで落とされた。

150.0/500

typedef long long int64;

class Dragons {
    public:
        string snaug(vector <int> initialFood, int rounds) {
            const static int NUM_SIDES = 6;
            const static bool d[NUM_SIDES][NUM_SIDES] = {
                { false, false,  true,  true,  true,  true },
                { false, false,  true,  true,  true,  true },
                {  true,  true, false, false,  true,  true },
                {  true,  true, false, false,  true,  true },
                {  true,  true,  true,  true, false, false },
                {  true,  true,  true,  true, false, false } };
            vector<pair<int64,int64> > food(NUM_SIDES);
            for (int i = 0; i < NUM_SIDES; i++)
                food[i] = make_pair(initialFood[i], 1);

            while (rounds-- > 0) {
                vector<pair<int64,int64> > oneFourth(food);
                for (int i = 0; i < NUM_SIDES; i++) {
                    oneFourth[i].second *= 4;
                    oneFourth[i] = reduction(oneFourth[i]);
                }
                food = vector<pair<int64,int64> >(NUM_SIDES, make_pair(0,1));
                for (int i = 0; i < NUM_SIDES; i++) {
                    for (int j = 0; j < NUM_SIDES; j++) {
                        if (d[i][j]) 
                            food[i] = addFrac(food[i], oneFourth[j]);
                    }
                }
            }

            ostringstream res;
            const static int BOSS = 2;
            if (food[BOSS].first == 0) {
                res << 0;
            } else if (food[BOSS].second == 1) {
                res << food[BOSS].first;
            } else {
                res << food[BOSS].first << "/" << food[BOSS].second;
            }
            return res.str();
        }
    private:
        int64 gcd(int64 c, int64 d) {
            if (c==0 || d==0) return 1;
            int64 v = c;
            while (v > 0) {
                v = c % d;
                c = d;
                d = v;
            }
            return c;
        }
        int64 lcm(int64 c, int64 d) {
            return c / gcd(c,d) * d;
        }
        pair<int64,int64> reduction(const pair<int64,int64> a) {
            int64 g = gcd(a.first, a.second);
            return make_pair(a.first/g, a.second/g);
        }
        pair<int64,int64> addFrac(const pair<int64,int64> a, const pair<int64,int64> b) {
            pair<int64,int64> ret;
            int64 l = lcm(a.second, b.second);
            ret.second = l;
            ret.first = a.first*(l/a.second) + b.first*(l/b.second);
            return reduction(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;
    }
};

PeopleCircle

| 18:31

問題文

494.30->598.14->598.95 / 600

一読したときは難しい問題のように思えたが、単純な方法で解ける問題だった。

class PeopleCircle {
public:
    string order(int numMales, int numFemales, int K) {
        const int n = numMales + numFemales;
        string result(n, 'M');
        int idx = n - 1;
        for (int i = 0; i < numFemales; i++) {
            for (int j = 0; j < K; j++) {
                do {
                    idx = (idx+1) % n;
                } while (result[idx] == 'F');
            }
            result[idx] = 'F';
        }
        return result;
    }
};

CCipher

| 18:28

問題文

245.71->249.80 / 250

文字列をシフトする。Aの次はZ。

class CCipher {
public:
    string decode(string cipherText, int shift) {
        for (int i = 0; i < cipherText.length(); i++) {
            cipherText[i] -= shift;
            if (cipherText[i] < 'A')
                cipherText[i] += 26;
        }
        return cipherText;
    }
};

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/