Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-07-23

ContestScore

| 07:50

問題文

合計ランクと合計スコアを計算して、結果をソートする。

bool compGroup(const string& a, const string& b)
{
    string aName, bName;
    int aRank, bRank;
    double aScore, bScore;
    istringstream isa(a), isb(b);
    isa >> aName >> aRank >> aScore;
    isb >> bName >> bRank >> bScore;
    if (aRank < bRank) {
        return true;
    } else if (aRank > bRank) {
        return false;
    } else {
        if (aScore > bScore) {
            return true;
        } else if (aScore < bScore) {
            return false;
        } else {
            return aName < bName;
        }
    }
}

class ContestScore {
public:
    vector <string> sortResults(vector <string> data) {
        const int numGroups = data.size();
        vector<vector<double> > scores(numGroups);
        vector<string> names(numGroups);
        vector<double> totalScores(numGroups);
        for (int i = 0; i < numGroups; i++) {
            istringstream iss(data[i]);
            iss >> names[i];
            double score;
            while (iss >> score) scores[i].push_back(score);
            totalScores[i] = accumulate(scores[i].begin(),scores[i].end(),0.0l);
        }

        int numScores = scores[0].size();
        vector<int> totalRanks(numGroups);
        for (int i = 0; i < numScores; i++) {
            double pre = 100.0;
            for (int rank = 1; rank <= numGroups; ) {
                double maxScore = -1.0;
                for (int j = 0; j < numGroups; j++) {
                    if (scores[j][i] < pre && scores[j][i] > maxScore) {
                        maxScore = scores[j][i];
                    }
                }
                int sameScores = 0;
                for (int j = 0; j < numGroups; j++) {
                    if (scores[j][i] == maxScore) {
                        totalRanks[j] += rank;
                        sameScores++;
                    }
                }
                rank += sameScores;
                pre = maxScore;
            }
        }

        vector<string> result(numGroups);
        for (int i = 0; i < numGroups; i++) {
            ostringstream oss;
            oss.setf(ios_base::fixed);
            oss.precision(1);
            oss << names[i] << " " << totalRanks[i] << " " << totalScores[i];
            result[i] = oss.str();
        }
        sort(result.begin(), result.end(), compGroup);
        return result;
    }
};

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