Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-22

BirthdayOdds

| 16:29

問題文, SRM 174

同じ誕生日になる確率。

467.33/500

class BirthdayOdds {
public:
    int minPeople(int minOdds, int daysInYear) {
        double p = 1;
        for (int i = 1; i <= daysInYear; i++) {
            p *= static_cast<double>(daysInYear-i+1)/daysInYear;
            if ((1-p)*100 >= minOdds)
                return i;
        }
        return 0;
    }
};

2009-08-19

Archimedes

| 11:09

問題文, SRM 151

円周率の近似値を求める。どうすれば求められるのかは、すぐに分かった。

230.08/250

class Archimedes {
    public:
        double approximatePi(int numSides) {
            return numSides * sin(M_PI/numSides);
        }
};

RenaRena2011/07/22 11:40Articles like this really grease the shftas of knowledge.

mtosqkksxfnmtosqkksxfn2011/07/22 18:19nGge95 <a href="http://htbsbsjhateo.com/">htbsbsjhateo</a>

vouvotvouvot2011/07/24 22:10AbhEFB <a href="http://udtjnaqmvoon.com/">udtjnaqmvoon</a>

lraetvllraetvl2011/07/25 02:03Ueilew , [url=http://ofkchvqjbqph.com/]ofkchvqjbqph[/url], [link=http://mhzhqovckhxx.com/]mhzhqovckhxx[/link], http://kgxfqnawhoqk.com/

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-08-10

NumberGuesser

| 19:34

問題文

数字を推測。自力で解けなかった。総当たりで解いたが、数学的な解法もある。

190.54/500 - 01:06:07 (cheated)

class NumberGuesser {
    public:
        int guess(string leftOver) {
            int candidate = 0;
            for (int d = 1; d <= 9; d++) {
                int found = 0;
                for (int i = 0; i < 4; i++) {
                    ostringstream oss;
                    oss << leftOver.substr(0,i) << d << leftOver.substr(i);
                    int z;
                    istringstream(oss.str()) >> z;
                    for (int x = 1; x+z <= 9998; x++) {
                        int y = x + z;
                        if (isDigitMatch(x, y)) {
                            candidate = d;
                            found++;
                            break;
                        }
                    }
                }
                if (found == 4) return d;
            }
            return candidate;
        }
    private:
        bool isDigitMatch(int x, int y) {
            vector<int> ndigits(10, 0);
            while (x > 0) {
                if (x%10 != 0) ndigits[x%10]++;
                x /= 10;
            }
            while (y > 0) {
                if (y%10 != 0) ndigits[y%10]--;
                y /= 10;
            }
            for (int i = 0; i < ndigits.size(); i++) {
                if (ndigits[i] != 0)
                    return false;
            }
            return true;
        }
};

2009-08-08

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

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/

2009-08-05

CalendarRecycle

| 19:09

問題文

次にカレンダーを使いまわせる年を求める。

class CalendarRecycle {
    public:
        int useAgain(int year) {
            int day = 0;
            const pair<bool,int> yearPair = make_pair(isLeapYear(year),day);
            for (int y = year+1; ; y++) {
                if (isLeapYear(y-1)) day = (day+366) % 7;
                else day = (day+365) % 7;
                if (yearPair == make_pair(isLeapYear(y),day))
                    return y;
            }
            return -1;
        }
    private:
        bool isLeapYear(const int year) {
            return (year%4 == 0 && year%100 != 0) || year%400 == 0;
        }
};

2009-08-04

LCMRange

| 18:43

問題文

最小公倍数の問題。

class LCMRange {
    public:
        int lcm(int first, int last) {
            int result = first;
            for (int i = first+1; i <= last; i++) {
                result = lcd(result, i);
            }
            return result;
        }
    private:
        int gcd(int c, int d) {
            int v;
            v = c;
            while (v > 0) {
                v = c % d;
                c = d;
                d = v;
            }
            return c;
        }
        int lcd(int c, int d) {
            return c*d / gcd(c,d);
        }
};

2009-07-28

Sets

| 18:25

問題文

集合演算。

class Sets {
public:
    vector <int> operate(vector <int> A, vector <int> B, string operation) {
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        if (operation == "UNION") {
            return union_set(A, B);
        } else if (operation == "INTERSECTION") {
            return intersection(A, B);
        } else if (operation == "SYMMETRIC DIFFERENCE") {
            return symmetric_difference(A, B);
        } else {
            return vector<int>();
        }
    }
private:
    vector<int> union_set(const vector<int>& A, const vector<int>& B) {
        set<int> tmp_union;
        for (int i = 0; i < A.size(); i++) tmp_union.insert(A[i]);
        for (int i = 0; i < B.size(); i++) tmp_union.insert(B[i]);
        vector<int> ret;
        for (set<int>::const_iterator itr = tmp_union.begin();
                itr != tmp_union.end(); itr++)
            ret.push_back(*itr);
        return ret;            
    }
    vector<int> intersection(const vector<int>& A, const vector<int>& B) {
        int i=0, j=0;
        vector<int> ret;
        while (i<A.size() && j<B.size()) {
            if (A[i] == B[j]) {
                ret.push_back(A[i]);
                i++; j++;
            } else if (A[i] < B[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ret;
    }
    vector<int> symmetric_difference(const vector<int>& A, const vector<int>& B) {
        vector<int> uni = union_set(A, B);
        vector<int> inter = intersection(A, B);
        vector<int> ret;
        for (int i = 0; i < uni.size(); i++) {
            if (find(inter.begin(),inter.end(),uni[i]) == inter.end())
                ret.push_back(uni[i]);
        }
        return ret;
    }
};

2009-07-26

Salary

| 09:09

問題文

給料を計算。

class Salary {
public:
    int howMuch(vector <string> arrival, vector <string> departure, int wage) {
        double amount = 0;
        for (int i = 0; i < arrival.size(); i++) {
            const static int NIGHT_END = calcTime(6, 0, 0);
            const static int EVENING_START = calcTime(18, 0, 0);
            const static double SEC_PER_HOUR = 60 * 60;
            int hh, mm, ss;
            sscanf(arrival[i].c_str(), "%d:%d:%d", &hh, &mm, &ss);
            int aTime = calcTime(hh, mm, ss);
            sscanf(departure[i].c_str(), "%d:%d:%d", &hh, &mm, &ss);
            int dTime = calcTime(hh, mm, ss);
            if (aTime < NIGHT_END) {
                if (dTime < NIGHT_END) {
                    amount += 1.5 * wage * (dTime-aTime)/SEC_PER_HOUR;
                    dTime = aTime;
                } else {
                    amount += 1.5 * wage * (NIGHT_END-aTime)/SEC_PER_HOUR;
                    aTime = NIGHT_END;
                }
            }
            if (dTime > EVENING_START) {
                if (aTime >= EVENING_START) {
                    amount += 1.5 * wage * (dTime-aTime)/SEC_PER_HOUR;
                    aTime = dTime;
                } else {
                    amount += 1.5 * wage * (dTime-EVENING_START)/SEC_PER_HOUR;
                    dTime = EVENING_START;
                }
            }
            amount += wage * (dTime-aTime)/SEC_PER_HOUR;
        }
        return static_cast<int>(floor(amount));
    }
private:
    int calcTime(const int h, const int m, const int s) {
        return (h*60 + m) * 60 + s;
    }
};

2009-07-24

BenfordsLaw

| 05:41

問題文

Benford's Law により計算される、期待される取引金額の先頭数字の出現数より、実際の出現数が基準よりずれているかどうかを調べる。

class BenfordsLaw {
public:
    int questionableDigit(vector <int> transactions, int threshold) {
        const int numTrans = transactions.size();
        double expected[10];
        for (int d = 1; d <= 9; d++) {
            expected[d] = log10(1.0l+1.0l/d) * numTrans;
        }
        vector<int> count(10, 0);
        for (int i = 0; i < numTrans; i++) {
            int first = transactions[i];
            while (first >= 10) first /= 10;
            count[first]++;
        }
        for (int d = 1; d <= 9; d++) {
            if (count[d] > threshold*expected[d] 
                  || count[d] < expected[d]/threshold)
                return d;
        }
        return -1;
    }
};