TopCoderの問題を解く

Quilting

SRM 160, Div2, Div2 Level-3, Div1, Div1 Level-2, Simulation | 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

SRM 160, Div2, Div2 Level-2, Geometry | 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

SRM 160, Div2, Div2 Level-1, String Manipulation | 18:34

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

問題文

１文字ごとの復号。

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