Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-15

GeneralChess

| 18:47

問題文, SRM 197

Algorithm Tutorials -- How to Find a Solutionから。

全てのナイトから脅かされているマスの位置を探す。

219.34/250

class GeneralChess {
public:
    vector <string> attackPositions(vector <string> pieces) {
        const int n = pieces.size();
        map<pair<int,int>,int> count;
        for (int i = 0; i < n; i++) {
            int x, y;
            sscanf(pieces[i].c_str(), "%d,%d", &x, &y);
            for (int dx = -2; dx <= 2; dx++)
                for (int dy = -2; dy <= 2; dy++) {
                    if (dx*dx+dy*dy != 5) continue;
                    count[make_pair(x+dx,y+dy)]++;
                }
        }

        vector<string> result;
        for (map<pair<int,int>,int>::const_iterator itr = count.begin();
                itr != count.end(); itr++)
            if (itr->second == n) {
                ostringstream oss;
                oss << itr->first.first << ',' << itr->first.second;
                result.push_back(oss.str());
            }
        return result;
    }
};

2009-09-07

GardenHose

| 12:51

問題文, SRM 197

庭の外側からホースを使って水を撒くとき、撒けないプラントは何個か。1回落とされたのは、ホースの長さが庭の長さより長い場合の処理を実装するのを忘れたため。解いた後にEditorialを見たら、撒けた場合にはcontinueし、ループの最後までいってしまったらカウンタを増やすというやり方が紹介されていた。その方法の方がバグを作りにくいな。

173.11/250 (1 failed)

class GardenHose {
public:
    int countDead(int n, int rowDist, int colDist, int hoseDist) {
        if (rowDist*n <= hoseDist || colDist*n <= hoseDist)
            return 0;
        vector<vector<int> > garden(n, vector<int>(n, 'x'));
        for (int i = 0; i < n; i++) {
            for (int j = 0; (j+1)*rowDist <= hoseDist; j++)
                garden[j][i] = garden[n-j-1][i] = 'o';
            for (int j = 0; (j+1)*colDist <= hoseDist; j++)
                garden[i][j] = garden[i][n-j-1] = 'o';
        }
        int result = 0;
        for (int i = 0; i < n; i++)
            result += count(garden[i].begin(), garden[i].end(), 'x');
        return result;
    }
};

2009-09-05

QuickSums

| 11:11

問題文, SRM 197

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

合計値が指定された数にするために、最低必要な足し算の数。この問題、分類がDynamic Programmingになっているけど、最悪のケースが2^9なのでBrute Forceな方法で解いてしまった。

669.36/1100

class QuickSums {
public:
    int minSums(string numbers, int sum) {
        int result = INT_MAX;
        D = numbers.length();
        for (int i = 0; i < power2(D-1); i++) {
            bitset<9> plus(i);
            int thisSum = getSum(numbers, plus);
            if (thisSum == sum) 
                result = min(result, (int)plus.count());
        }
        if (result == INT_MAX) return -1;
        else return result;
    }
private:
    int D;
    int power2(int d) {
        int ret = 1;
        while (d-- > 0) ret *= 2;
        return ret;
    }
    int getSum(const string& nums, const bitset<9>& plus) {
        int sum = 0;
        int pre = 0;
        for (int i = 0; i < D-1; i++) {
            if (plus[i]) {
                sum += atoi(nums.substr(pre,i-pre+1).c_str());
                pre = i+1;
            }
        }
        sum += atoi(nums.substr(pre,D-pre).c_str());
        return sum;
    }
};