Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-29

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

2009-08-01

Quilting

| 11:24

問題文

キルト作り。自力で解けたが、解くのに一時間以上かかった。

class Quilting {
    public:
        string lastPatch(int length, int width, vector <string> colorList) {
            vector<vector<string> > quilt(200,vector<string>(200,string(".")));
            map<string,int> prevCount;
            int y=100, x=100, dir=0;
            quilt[y][x] = colorList[0];
            prevCount[colorList[0]]++;
            for (int i = 1; i < length*width; i++) {
                const static int NEIGHBORS = 8;
                const static int nd[NEIGHBORS][2] = {
                    {-1,-1}, {-1, 0}, {-1, 1},
                    { 0,-1},          { 0, 1},
                    { 1,-1}, { 1, 0}, { 1, 1} };
                const static int MOVE_KINDS = 4;
                const static int mvd[MOVE_KINDS][4] = {
                    {-1, 0, 0,-1}, { 0,-1, 1, 0},
                    { 1, 0, 0, 1}, { 0, 1,-1, 0} };
                y += mvd[dir][0];
                x += mvd[dir][1];
                map<string,int> neighorCount;
                for (int j = 0; j < NEIGHBORS; j++) {
                    const int dy = y + nd[j][0];
                    const int dx = x + nd[j][1];
                    if (quilt[dy][dx] != ".") {
                        neighorCount[quilt[dy][dx]]++;
                    }
                }
                string color;
                int minSameColor = INT_MAX;
                if (neighorCount.size() == colorList.size()) {
                    for (map<string,int>::const_iterator itr = neighorCount.begin();
                            itr != neighorCount.end(); itr++) {
                        if (itr->second < minSameColor) {
                            color = itr->first;
                            minSameColor = itr->second;
                        } else if (itr->second == minSameColor) {
                            if (prevCount[itr->first] < prevCount[color]) {
                                color = itr->first;
                            } else if (prevCount[itr->first] == prevCount[color]) {
                                if (find(colorList.begin(),colorList.end(),itr->first) 
                                        < find(colorList.begin(),colorList.end(),color)) {
                                    color = itr->first;
                                }
                            }
                        }
                    }
                } else {
                    for (int j = 0; j < colorList.size(); j++) {
                        if (neighorCount.find(colorList[j]) == neighorCount.end()) {
                            if (prevCount[colorList[j]] < minSameColor) {
                                minSameColor = prevCount[colorList[j]];
                                color = colorList[j];
                            }
                        }
                    }
                }
                quilt[y][x] = color;
                prevCount[color]++;
                if (quilt[y+mvd[dir][2]][x+mvd[dir][3]] == ".") {
                    dir = (dir+1) % MOVE_KINDS;
                }
            }
            return quilt[y][x];
        }
};

Intersect

| 18:34

問題文

全ての矩形に囲まれる矩形の面積を求める。

class Intersect {
public:
    int area(vector <int> x, vector <int> y) {
        int left =INT_MIN, right=INT_MAX;
        int upper=INT_MIN, lower=INT_MAX;
        for (int i = 0; i < x.size(); i += 2) {
            if (x[i] > x[i+1]) swap(x[i], x[i+1]);
            if (y[i] > y[i+1]) swap(y[i], y[i+1]);
            left  = max(left, x[i]);
            right = min(right, x[i+1]);
            upper = max(upper, y[i]);
            lower = min(lower, y[i+1]);
        }
        if ((right-left) <= 0 || (lower-upper) <= 0) return 0;
        else return (right-left) * (lower-upper);
    }
};

Substitute

| 18:34

コードがはみ出るので、ブログのデザインを横幅が広いデザインに変更した。

問題文

1文字ごとの復号。

class Substitute {
public:
    int getValue(string key, string code) {
        map<char,int> decoder;
        for (int i = 0; i < key.length(); i++) {
            if (i == key.length()-1) decoder[key[i]] = 0;
            else decoder[key[i]] = i+1;
        }
        int value = 0;
        for (int i = 0; i < code.length(); i++) {
            if (decoder.find(code[i]) != decoder.end()) {
                value *= 10;
                value += decoder[code[i]];
            }
        }
        return value;
    }
};