Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-05

Jumper

| 19:49

問題文, SRM 158

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

一番上までいくのに何ステップかかるか。BFSで解ける。問題を理解するのに1時間。そして、解法が浮かばなくてEditorialを見ながら解くのに2時間ぐらいかかった。

304.01/1000 (cheated)

struct State {
    int x, y, t;
    State() {}
    State(const int x, const int y, const int t) :
        x(x), y(y), t(t) {}
};
bool operator< (const State& a, const State& b) {
    if (a.t < b.t) {
        return true;
    } else if (a.t > b.t) {
        return false;
    } else {
        if (a.y > b.y) {
            return true;
        } else if (a.y < b.y) {
            return false;
        } else {
            return a.x < b.x;
        }
    }
}

class Jumper {
public:
    int minTime(vector <string> patterns, vector <int> speeds, string rows) {
        const int HEIGHT = rows.size()+1;
        const int WIDTH = 20;
        vector<string> grid(HEIGHT+1);
        grid[0] = grid[HEIGHT] = string(WIDTH, '#');
        for (int i = 0; i < rows.size(); i++) 
            for (int j = 0; j < 4; j++)
                grid[i+1] += patterns[rows[i]-'0'];
        queue<State> Q;
        Q.push(State(0,0,0));
        set<State> checked;
        while (!Q.empty()) {
            State s = Q.front(); Q.pop();
            if (s.t > 2100) break;
            if (s.y >= HEIGHT) return s.t;
            const static int MOVE_KINDS = 5;
            const static int d[MOVE_KINDS][2] = {
                {0,0},{1,0},{-1,0},{0,1},{0,-1} };
            for (int i = 0; i < MOVE_KINDS; i++) {
                const int dx = s.x + d[i][0];
                const int dy = s.y + d[i][1];
                if (0<=dx&&dx<WIDTH && 0<=dy) {
                    int offset = (dy==0||dy==HEIGHT) ? 0 : 
                        (((-s.t*speeds[rows[dy-1]-'0'])%5)+5)%5;
                    if (grid[dy][(dx+offset)%WIDTH] == '#') {
                        const int ddx = dx + ((dy==0||dy==HEIGHT)? 0 :
                                speeds[rows[dy-1]-'0']);
                        if (0<=ddx && ddx<WIDTH) {
                            State next(ddx, dy, s.t+1);
                            if (checked.find(next) == checked.end()) {
                                checked.insert(next);
                                Q.push(next);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
};

TickTick

| 13:04

問題文, SRM 177

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

何種類のイベントの組み合わせができるか。問題の意味がわからなかった。Editorialを読んでようやく理解できた。

122.36/300 (cheated)

class TickTick {
public:
    int count(vector <string> events) {
        vector<double> e; 
        e.push_back(0.0);
        for (int i = 0; i < events.size(); i++) 
            e.push_back(atof(events[i].c_str()));
        set<string> ret;
        for (int i = 0; i < e.size(); i++) {
            double tick = e[i] + 5e-8;
            double prev = DBL_MIN;
            string seq;
            for (int j = 0; j < e.size(); j++) {
                double tickIndex = floor(e[j]-tick);
                if (tickIndex == prev) seq += "S";
                else seq += "D";
                prev = tickIndex;
            }
            ret.insert(seq);
        }
        return ret.size();
    }
};

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

TallPeople

| 10:33

問題文, SRM 208

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

一番小さい人の中から一番大きい人を選び、一番大きい人の中から一番小さい人を選ぶ。

210.68/250

class TallPeople {
public:
    vector <int> getPeople(vector <string> people) {
        R = people.size();
        ppl = vector<vector<int> >(R);
        for (int i = 0; i < R; i++) {
            istringstream iss(people[i]);
            int t;
            while (iss >> t) ppl[i].push_back(t);
        }
        C = ppl[0].size();

        vector <int> result(2);
        result[0] = tallestOfShortest();
        result[1] = shortestOfTallest();
        return result;
    }
private:
    int R, C;
    vector<vector<int> > ppl;
    int tallestOfShortest() {
        int tallest = INT_MIN;
        for (int i = 0; i < R; i++)
            tallest = max(tallest, 
                    *min_element(ppl[i].begin(),ppl[i].end()));
        return tallest;
    }
    int shortestOfTallest() {
        int shortest = INT_MAX;
        for (int i = 0; i < C; i++) {
            int tallest = INT_MIN;
            for (int j = 0; j < R; j++)
                tallest = max(tallest, ppl[j][i]);
            shortest = min(shortest, tallest);
        }
        return shortest;
    }
};