Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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-05-23

MergeSort

| 16:47

問題文

548.28->886.11->890.45->962.99/1000

マージソートを行う際に必要な比較回数を数える。

class MergeSort {
public:
    int howManyComparisons(vector <int> numbers) {
        count = 0;
        const int sz = numbers.size();
        vector<long long> nums(sz);
        for (int i = 0; i < sz; i++)
            nums[i] = numbers[i];
        mergeSort(nums, 0, sz);
        return count;
    }
private:
    int count;
    const static long long INF = INT_MAX + 1ll;
    void merge(vector<long long>& A,
            const int p, const int q, const int r) {
        const int n1 = q - p;
        const int n2 = r - q;
        vector<long long> L(n1+1), R(n2+1);
        for (int i = 0; i < n1; i++)
            L[i] = A[p+i];
        for (int j = 0; j < n2; j++)
            R[j] = A[q+j];
        L[n1] = R[n2] = INF;
        int i = 0, j = 0;
        for (int k = p; k < r; k++) {
            if (L[i] != INF && R[j] != INF)
                count++;
            if (L[i] < R[j]) {
                A[k] = L[i];
                i++;
            } else if (L[i] > R[j]) {
                A[k] = R[j];
                j++;
            } else {
                A[k] = L[i]; k++;
                A[k] = R[j];
                i++; j++;
            }
        }
    }
    void mergeSort(vector<long long>& A, const int p, const int r) {
        if (r-p > 1) {
            const int q = (p+r) / 2;
            mergeSort(A, p, q);
            mergeSort(A, q, r);
            merge(A, p, q, r);
        }
    }
};

Birthday

| 19:43

問題文

336.13->498.40/500

直近にある誕生日を探す。

class Birthday {
public:
    string getNext(string date, vector <string> birthdays) {
        sort(birthdays.begin(), birthdays.end());
        for (int i = 0; i < birthdays.size(); i++) {
            if (birthdays[i] >= date) {
                return birthdays[i].substr(0, 5);
            }
        }
        return birthdays[0].substr(0, 5);
    }
};

PrefixCode

| 19:40

問題文

232.80->249.10/250

words に含まれる各文字列が他の文字列の prefix code (前方一致している)かどうかを調べる。

class PrefixCode {
public:
    string isOne(vector <string> words) {
        for (int i = 0; i < words.size(); i++) {
            int len = words[i].length();
            for (int j = 0; j < words.size(); j++) {
                if (i == j || len > words[j].length()) continue;
                if (words[i] == words[j].substr(0,len)) {
                    ostringstream os;
                    os << "No, " << i;
                    return os.str();
                }
            }
        }
        return "Yes";
    }
};