Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-01

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

2009-07-28

Sets

| 18:25

問題文

集合演算。

class Sets {
public:
    vector <int> operate(vector <int> A, vector <int> B, string operation) {
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        if (operation == "UNION") {
            return union_set(A, B);
        } else if (operation == "INTERSECTION") {
            return intersection(A, B);
        } else if (operation == "SYMMETRIC DIFFERENCE") {
            return symmetric_difference(A, B);
        } else {
            return vector<int>();
        }
    }
private:
    vector<int> union_set(const vector<int>& A, const vector<int>& B) {
        set<int> tmp_union;
        for (int i = 0; i < A.size(); i++) tmp_union.insert(A[i]);
        for (int i = 0; i < B.size(); i++) tmp_union.insert(B[i]);
        vector<int> ret;
        for (set<int>::const_iterator itr = tmp_union.begin();
                itr != tmp_union.end(); itr++)
            ret.push_back(*itr);
        return ret;            
    }
    vector<int> intersection(const vector<int>& A, const vector<int>& B) {
        int i=0, j=0;
        vector<int> ret;
        while (i<A.size() && j<B.size()) {
            if (A[i] == B[j]) {
                ret.push_back(A[i]);
                i++; j++;
            } else if (A[i] < B[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ret;
    }
    vector<int> symmetric_difference(const vector<int>& A, const vector<int>& B) {
        vector<int> uni = union_set(A, B);
        vector<int> inter = intersection(A, B);
        vector<int> ret;
        for (int i = 0; i < uni.size(); i++) {
            if (find(inter.begin(),inter.end(),uni[i]) == inter.end())
                ret.push_back(uni[i]);
        }
        return ret;
    }
};

2009-07-26

BaseMystery

| 09:14

問題文

n進数を採用したとき、等式を満たすかどうか。見落としが多く、2回システムテストで落とされ、3回目で通った。

class BaseMystery {
public:
    vector <int> getBase(string equation) {
        vector <int> result;
        vector<string> nums(3); 
        nums[0] = string(equation.begin(), 
                find(equation.begin(),equation.end(),'+'));
        nums[1] = string(equation.begin()+nums[0].length()+1, 
            find(equation.begin()+nums[0].length()+1,equation.end(),'='));
        nums[2] = string(equation.begin()+nums[0].length()+nums[1].length()+2,
                equation.end());
        int maxDigit = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < nums[i].length(); j++) {
                maxDigit = max(maxDigit, getIntDigit(nums[i][j]));
            }
        }
        for (int p = max(2,maxDigit+1); p <= 20; p++) {
            if (toBase10(nums[0],p)+toBase10(nums[1],p)
                                    == toBase10(nums[2],p))
                result.push_back(p);
        }
        return result;
    }
private:
    int getIntDigit(const char c) {
        if (isdigit(c)) return c - '0';
        else return 10 + c - 'A';
    }
    int toBase10(const string& s, const int p) {
        int d = 0;
        for (int i = 0; i < s.length(); i++) {
            d *= p;
            d += getIntDigit(s[i]);
        }
        return d;
    }
};

Salary

| 09:09

問題文

給料を計算。

class Salary {
public:
    int howMuch(vector <string> arrival, vector <string> departure, int wage) {
        double amount = 0;
        for (int i = 0; i < arrival.size(); i++) {
            const static int NIGHT_END = calcTime(6, 0, 0);
            const static int EVENING_START = calcTime(18, 0, 0);
            const static double SEC_PER_HOUR = 60 * 60;
            int hh, mm, ss;
            sscanf(arrival[i].c_str(), "%d:%d:%d", &hh, &mm, &ss);
            int aTime = calcTime(hh, mm, ss);
            sscanf(departure[i].c_str(), "%d:%d:%d", &hh, &mm, &ss);
            int dTime = calcTime(hh, mm, ss);
            if (aTime < NIGHT_END) {
                if (dTime < NIGHT_END) {
                    amount += 1.5 * wage * (dTime-aTime)/SEC_PER_HOUR;
                    dTime = aTime;
                } else {
                    amount += 1.5 * wage * (NIGHT_END-aTime)/SEC_PER_HOUR;
                    aTime = NIGHT_END;
                }
            }
            if (dTime > EVENING_START) {
                if (aTime >= EVENING_START) {
                    amount += 1.5 * wage * (dTime-aTime)/SEC_PER_HOUR;
                    aTime = dTime;
                } else {
                    amount += 1.5 * wage * (dTime-EVENING_START)/SEC_PER_HOUR;
                    dTime = EVENING_START;
                }
            }
            amount += wage * (dTime-aTime)/SEC_PER_HOUR;
        }
        return static_cast<int>(floor(amount));
    }
private:
    int calcTime(const int h, const int m, const int s) {
        return (h*60 + m) * 60 + s;
    }
};

2009-07-25

BombSweeper

| 05:47

問題文

ゲームの勝率を求める。

class BombSweeper {
public:
    double winPercentage(vector <string> board) {
        const int height = board.size();
        const int width = board[0].length();
        const static int DIR_KINDS = 8;
        const int d[DIR_KINDS][2] = {
            {-1,-1}, {-1, 0}, {-1, 1},
            { 0,-1},          { 0, 1},
            { 1,-1}, { 1, 0}, { 1, 1} };

        int wins=0, loses=0;
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (board[y][x] == 'B') {
                    loses++;
                    continue;
                }
                for (int i = 0; i < DIR_KINDS; i++) {
                    const int dy = y + d[i][0];
                    const int dx = x + d[i][1];
                    if (0<=dy&&dy<height && 0<=dx&&dx<width) {
                        if (board[dy][dx] == 'B') break;
                    }
                    if (i == DIR_KINDS-1) wins++;
                }
            }
        }
        const double percentage = 100.0l * wins / (wins+loses); 
        return percentage;
    }
};

2009-07-24

BenfordsLaw

| 05:41

問題文

Benford's Law により計算される、期待される取引金額の先頭数字の出現数より、実際の出現数が基準よりずれているかどうかを調べる。

class BenfordsLaw {
public:
    int questionableDigit(vector <int> transactions, int threshold) {
        const int numTrans = transactions.size();
        double expected[10];
        for (int d = 1; d <= 9; d++) {
            expected[d] = log10(1.0l+1.0l/d) * numTrans;
        }
        vector<int> count(10, 0);
        for (int i = 0; i < numTrans; i++) {
            int first = transactions[i];
            while (first >= 10) first /= 10;
            count[first]++;
        }
        for (int d = 1; d <= 9; d++) {
            if (count[d] > threshold*expected[d] 
                  || count[d] < expected[d]/threshold)
                return d;
        }
        return -1;
    }
};

2009-07-23

SuperRot

| 05:33

問題文

暗号化された文字列を復号。

class SuperRot {
public:
    string decoder(string message) {
        setToTable('A', 'M', 'N');
        setToTable('N', 'Z', 'A');
        setToTable('a', 'm', 'n');
        setToTable('n', 'z', 'a');
        setToTable('0', '4', '5');
        setToTable('5', '9', '0');
        for (int i = 0; i < message.length(); i++) {
            if (isalnum(message[i]))
                message[i] = table[message[i]];
        }
        return message;
    }
private:
    char table[256];
    void setToTable(const char l, const char h, const char s) {
        for (int i = l; i <= h; i++) table[i] = s+(i-l);
    }
};

2009-07-22

Inventory

| 19:55

問題文

30日間換算で1商品当たりいくつ売れるのかを計算。

const static double EPS = 1.0e-9;

class Inventory {
public:
    int monthlyOrder(vector <int> sales, vector <int> daysAvailable) {
        const static int DAYS_OF_MONTH = 30;
        double sum = 0;
        int availableItems = 0;
        for (int i = 0; i < sales.size(); i++) {
            if (daysAvailable[i] != 0) {
                sum += (static_cast<double>(sales[i])/daysAvailable[i])
                                                        * DAYS_OF_MONTH;
                availableItems++;
            }
        }
        return static_cast<int>(ceil(sum/availableItems-EPS));
    }
};

2009-07-05

LeaguePicks

| 19:47

問題文

436.29 -> 498.91 / 500

position-th と (2*friends+position+1)-th にあたる pick を取る。簡単な問題。問題文の Examples にヒントが書かれている。

class LeaguePicks {
public:
    vector <int> returnPicks(int position, int friends, int picks) {
        vector <int> result;
        int p = 0;
        while (true) {
            int next = p + position;
            if (next <= picks) result.push_back(next);
            else break;
            next = p + 2*friends - position + 1;
            if (next <= picks) result.push_back(next);
            else break;
            p += 2 * friends;
        }
        return result;
    }
};

2009-05-23

Birthday

| 19:43

問題文

336.13->498.40/500

直近にある誕生日を探す。

class Birthday {
public:
    string getNext(string date, vector <string> birthdays) {
        sort(birthdays.begin(), birthdays.end());
        for (int i = 0; i < birthdays.size(); i++) {
            if (birthdays[i] >= date) {
                return birthdays[i].substr(0, 5);
            }
        }
        return birthdays[0].substr(0, 5);
    }
};

2009-05-11

InterestingDigits

| 18:51

問題文

251.51->499.03

説明が面倒なので無し。

class InterestingDigits {
public:
    vector <int> digits(int base) {
        vector <int> result;
        for (int d = 2; d < base; d++) {
            if (isInterestingDigit(base, d))
                result.push_back(d);
        }
        return result;
    }
private:
    bool isInterestingDigit(const int base, const int d) {
        return base%d == 1;
    }
};

MissyMissy2011/07/22 16:09Now I know who the brainy one is, I'll keep looknig for your posts.

zrwuybrcsgozrwuybrcsgo2011/07/23 22:08xDBJGa , [url=http://ngbsklytunqc.com/]ngbsklytunqc[/url], [link=http://olpwwtwjhupr.com/]olpwwtwjhupr[/link], http://vfyjnrgeopbs.com/

qbqmjjqbqmjj2011/07/24 21:58F1VCcA <a href="http://iyopswirddsc.com/">iyopswirddsc</a>