Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-29

Rochambo

| 17:09

問題文, SRM 163

じゃんけんの勝数。

157.83/250

class Rochambo {
public:
    int wins(string opponent) {
        int counter = 0;
        for (int i = 0; i < 2 && i < opponent.size(); i++)
            if (isWin('R', opponent[i]))
                counter++;
        for (int i = 2; i < opponent.size(); i++) {
            string pre2 = opponent.substr(i-2, 2);
            char move;
            if (pre2 == "RR") move = 'P';
            else if (pre2 == "SS") move = 'R';
            else if (pre2 == "PP") move = 'S';
            else if (pre2.find("R") == string::npos) move = 'P';
            else if (pre2.find("S") == string::npos) move = 'R';
            else move = 'S';
            if (isWin(move, opponent[i]))
                counter++;
        }
        return counter;
    }
private:
    bool isWin(const char a, const char b) {
        return (a=='R'&&b=='S') || (a=='S'&&b=='P') || (a=='P'&&b=='R');
    }
};

IsHomomorphism

| 16:05

問題文, SRM 161

同じ答えを返すかどうかを調べる。問題の意味がわかりにくいが、わかれば簡単な問題。

196.13/300

class IsHomomorphism {
public:
    vector <string> numBad(vector <string> source, vector <string> target, vector <int> mapping) {
        vector <string> result;
        for (int i = 0; i < source.size(); i++) {
            for (int j = 0; j < source[0].size(); j++) {
                if (mapping[source[i][j]-'0'] != target[mapping[i]][mapping[j]]-'0') {
                    ostringstream oss;
                    oss << "(" << i << "," << j << ")";
                    result.push_back(oss.str());
                }
            }
        }
        return result;
    }
};

QuipuReader

| 14:05

問題文, SRM 155

特殊な数記法で表わされた数を処理。解くのに時間かかり過ぎ。

191.33/450

class QuipuReader {
public:
    vector <int> readKnots(vector <string> knots) {
        const int sz = knots.size();
        const int len = knots[0].length();
        vector<vector<int> > num(sz), start(sz), last(sz);
        for (int i = 0; i < sz; i++) {
            int j = 0;
            while (j < len) {
                while (j < len && knots[i][j] != 'X') j++;
                if (j == len && knots[i][len-1] != 'X') break;
                start[i].push_back(j);
                j++;
                while (j < len && knots[i][j] == 'X') j++;
                num[i].push_back(j-start[i].back());
                last[i].push_back(j-1);
            }
        }

        vector <int> result(sz,0), idx(sz,0);
        int i = 0;
        while (i < len) {
            int s = INT_MAX, l=INT_MAX;
            for (int j = 0; j < sz; j++) {
                if (idx[j] < start[j].size() && start[j][idx[j]] < s) {
                    s = start[j][idx[j]];
                    l = last[j][idx[j]];
                }
            }
            if (s == INT_MAX) break;
            for (int j = 0; j < sz; j++) {
                result[j] *= 10;
                if (idx[j] < start[j].size() &&
                        ((s<=start[j][idx[j]] && last[j][idx[j]]<=l) ||
                        (start[j][idx[j]]<=s && l<=last[j][idx[j]]))) {
                    result[j] += num[j][idx[j]];
                    idx[j]++;
                } 
            }
            i = l + 1;
        }
        return result;
    }
};

Iditarod

| 10:30

問題文, SRM 160

所要時間の平均を求める。

212.31/250

class Iditarod {
public:
    int avgMinutes(vector <string> times) {
        int total = 0;
        for (int i = 0; i < times.size(); i++)
            total += getTime(times[i]);
        return (int)((double) total / times.size() + 0.5);
    }
private:
    int getTime(string& time) {
        int hh, mm, n;
        char apm;
        sscanf(time.c_str(), "%d:%d %cM, DAY %d", &hh, &mm, &apm, &n);
        if (hh == 12) hh = 0;
        if (apm == 'P') hh += 12;
        return 24*(n-1)*60 + hh*60 + mm - 8*60;
    }
};