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

ProblemWriting

| 15:12

問題文

497.42 -> 967.77 / 1000

以下の状態遷移図を基にプログラムすればいい。

f:id:caligue:20090720171507p:image

enum STATES { S0, S1, S2, S3 };

class ProblemWriting {
public:
    string myCheckData(string dotForm) {
        const int len = dotForm.length();
        if (len < 1 || 25 < len) {
            return "dotForm must contain between 1 and 25 characters, inclusive.";
        }
        vector<char> ops;
        ops.push_back('+'); ops.push_back('-');
        ops.push_back('*'); ops.push_back('/');
        int state = S0;
        for (int i = 0; i < len; i++) {
            const char c = dotForm[i];
            bool isError = false;
            switch (state) {
            case S0:
                if (isdigit(c)) 
                    state = S1;
                else 
                    isError = true;
                break;
            case S1:
            case S2:
                if (c == '.') 
                    state = S2;
                else if (find(ops.begin(),ops.end(),c) != ops.end()) 
                    state = S3;
                else 
                    isError = true;
                break;
            case S3:
                if (c == '.') 
                    state = S3;
                else if (isdigit(c)) 
                    state = S1;
                else 
                    isError = true;
                break;
            }
            if (isError) {
                ostringstream oss;
                oss << "dotForm is not in dot notation, check character "
                    << i << ".";
                return oss.str();
            }
        }
        if (state != S1) {
            ostringstream oss;
            oss << "dotForm is not in dot notation, check character "
                << len << ".";
            return oss.str();
        }
        return "";
    }
};

2009-05-23

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

2009-04-30

ExerciseMachine

| 17:51

問題文

266.14->498.44 / 500

これも問題がわかりにくい。エクササイズの進捗率が小数点以下を含まない時、経過時間も小数点以下を含まない場合にしか、その進捗率を表示しないという、妙なエクササイズマシンの話。gcd(s,100)-1でも解を求められる。

class ExerciseMachine {
public:
    int getPercentages(string time) {
        int HH, MM, SS;
        char pat;
        istringstream iss(time);
        iss >> HH >> pat >> MM >> pat >> SS;
        int s = (HH*60 + MM)*60 + SS;

        int count = 0;
        for (int i = 1; i <= 99; i++)
            if ((i*s)%100 == 0)
                count++;
        return count;
    }
};