Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-30

InstantRunoff

| 17:56

問題文, SRM 175

選挙で、誰が過半数の票を獲得するか。

166.88/550 (1 failed)

class InstantRunoff {
public:
    string outcome(string candidates, vector <string> ballots) {
        const int numCandidates = candidates.size();
        const int numVoters = ballots.size();
        vector<int> idx(numVoters, 0);
        vector<char> failed;
        for (int i = 0; i < numCandidates; ) {
            map<char,int> votes;
            for (int k = 0; k < numCandidates; k++) 
                if (find(failed.begin(),failed.end(),candidates[k]) == failed.end())
                    votes[candidates[k]] = 0;
            for (int j = 0; j < numVoters; j++) {
                while (votes.find(ballots[j][idx[j]]) == votes.end()) idx[j]++;
                votes[ballots[j][idx[j]]]++;
            }
            int minimum = INT_MAX;
            for (map<char,int>::const_iterator v = votes.begin();
                    v != votes.end(); v++) {
                if (v->second > numVoters/2)
                    return string(1,v->first);
                if (v->second < minimum)
                    minimum = v->second;
            }
            for (map<char,int>::const_iterator v = votes.begin();
                    v != votes.end(); v++) {
                if (v->second == minimum) {
                    failed.push_back(v->first);
                    i++;
                    for (int j = 0; j < numVoters; j++) {
                        if (v->first == ballots[j][idx[j]])
                            idx[j]++;
                    }
                }
            }
        }
        return "";
    }
};

2009-08-24

ClockWalk

| 17:39

問題文, SRM 175

時計を動かし終わった後は、何時か。テストをしないで出したら、tailの場合の計算で、馬鹿なバグがあり、落とされた。

214.27/250

class ClockWalk {
public:
    int finalPosition(string flips) {
        int hour = 0;
        for (int i = 0; i < flips.size(); i++) {
            if (flips[i] == 'h') hour = (hour + i+1) % 12;
            else  hour = (hour - (i+1) + 120) % 12;
        }
        if (hour == 0) hour = 12;
        return hour;
    }
};