Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-23

CheatCode

| 11:08

問題文, SRM 154

どの裏技コードを入力したかを判定。1回目に出したときは、しょうもないバグがあり、落とされた。

152.30/350

class CheatCode {
public:
    vector <int> matches(string keyPresses, vector <string> codes) {
        vector <int> result;
        const int keyLen = keyPresses.length();
        for (int i = 0; i < codes.size(); i++) {
            const int codeLen = codes[i].length();
            for (int j = 0; j < keyLen; j++) {
                if (codes[i][0] != keyPresses[j]) continue;
                int idx = 1;
                for (int k = j+1; idx < codeLen && k < keyLen; k++) {
                    if (codes[i][idx] == keyPresses[k])
                        idx++;
                    else if (keyPresses[k] != codes[i][idx-1])
                        break;
                }
                if (idx == codeLen) {
                    result.push_back(i);
                    break;
                }
            }
        }
        return result;
    }
};

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

SuperRot

| 05:33

問題文

暗号化された文字列を復号。

class SuperRot {
public:
    string decoder(string message) {
        setToTable('A', 'M', 'N');
        setToTable('N', 'Z', 'A');
        setToTable('a', 'm', 'n');
        setToTable('n', 'z', 'a');
        setToTable('0', '4', '5');
        setToTable('5', '9', '0');
        for (int i = 0; i < message.length(); i++) {
            if (isalnum(message[i]))
                message[i] = table[message[i]];
        }
        return message;
    }
private:
    char table[256];
    void setToTable(const char l, const char h, const char s) {
        for (int i = l; i <= h; i++) table[i] = s+(i-l);
    }
};

ProfitCalculator

| 05:33

問題文

利益率を計算。

class ProfitCalculator {
public:
    int percent(vector <string> items) {
        double totalPrice=0, totalCost=0;
        for (int i = 0; i < items.size(); i++) {
            double price, cost;
            istringstream(items[i]) >> price >> cost;
            totalPrice += price;
            totalCost += cost;
        }
        return static_cast<int>(floor((1-totalCost/totalPrice)*100));
    }
};