Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-30

Table

| 14:44

問題文, SRM 157

テーブルの形式を変換。

366.23/500

class Table {
public:
    vector <string> layout(vector <string> tbl) {
        const int rows = tbl.size();
        vector <string> result(rows, string(51, '?'));
        for (int r = 0; r < rows; r++) {
            istringstream iss(tbl[r]);
            int colspan, rowspan;
            char content, pad;
            int c = 0;
            while (iss >> pad >> colspan >> pad >> rowspan 
                     >> pad >> content >> pad) {
                while (result[r][c] != '?') c++;
                for (int rr = r; rr < r+rowspan; rr++)
                    for (int cc = c; cc < c+colspan; cc++)
                        result[rr][cc] = content;
                c = c + colspan;
            }
        }
        const int cols = result[0].find("?");
        for (int r = 0; r < rows; r++)
            result[r] = result[r].substr(0, cols);
        return result;
    }
};

2009-07-26

HourGlass

| 11:16

問題文

2つの砂時計を使って測れる時間を求める。Brute-forceで解ける問題だけど、どういう状態を調べれば解けるのかがわからなかった。慣れるしかないか。

class HourGlass {
public:
    vector <int> measurable(int glass1, int glass2) {
        g1 = glass1;
        g2 = glass2;
        times.clear();
        memo = vector<vector<vector<bool> > >(MAX_POSSIBLE_TIME+1, 
                vector<vector<bool> >(g1+1, vector<bool>(g2+1,false)));
        go(0, 0, 0);
        const static int RETURN_VALUES = 10;
        vector <int> result(RETURN_VALUES);
        set<int>::const_iterator itr = times.begin();
        for (int i = 0; i < RETURN_VALUES; i++) {
            itr++;
            result[i] = *itr;
        }
        return result;
    }
private:
    set<int> times;
    int g1, g2;
    const static int MAX_POSSIBLE_TIME = 500;
    vector<vector<vector<bool> > > memo;
    void go(const int sand1, const int sand2, const int time) {
        if (time > MAX_POSSIBLE_TIME) return;
        if (memo[time][sand1][sand2]) return;
        memo[time][sand1][sand2] = true;
        times.insert(time);
        if (sand1==0 || sand2==0) {
            go(g1-sand1, sand2, time);
            go(sand1, g2-sand2, time);
            go(g1-sand1, g2-sand2, time);
        }
        if (sand1>0 && sand2==0) go(0, 0, time+sand1);
        if (sand2>0 && sand1==0) go(0, 0, time+sand2);
        if (sand1>0 && sand2>0) {
            int minSand = min(sand1, sand2);
            go(sand1-minSand, sand2-minSand, time+minSand);
        }
    }
};

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

GuessTheNumber

| 09:09

問題文

数字を推測。問題文の疑似コードを実装するだけ。

class GuessTheNumber {
public:
    int noGuesses(int upper, int answer) {
        int no = 1;
        int lower = 1;
        while (true) {
            int guess = (lower+upper) / 2;
            if (guess == answer) return no;
            else if (guess < answer) lower = guess+1;
            else if (guess > answer) upper = guess-1; 
            no++;
        }
        return -1;
    }
};