Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-05-02

BridgeCrossing

| 18:09

問題文

456.12->950.72->985.42 / 1000

わからなくて Editorial を見た。Brute force な方法で解ける。

class BridgeCrossing {
public:
    int minTime(vector <int> times) {
        n = times.size();
        if (n == 1)
            return times[0];
        int best = 9999999;
        vector<bool> side(n, false);
        go(times, 0, n, side, best);
        return best;
    }
private:
    int n;
    void go(const vector<int>& times, const int tm, const int left,
            vector<bool>& side, int& best) {
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!side[i] && !side[j]) {
                    side[i] = side[j] = true;
                    int new_tm = tm + max(times[i],times[j]);
                    if (left == 2) {
                        best = min(best, new_tm);
                    } else {
                        for (int k = 0; k < n; k++) {
                            if (side[k]) {
                                side[k] = false;
                                go(times, new_tm+times[k], left-1,
                                        side, best);
                                side[k] = true;
                            }
                        }
                    }
                    side[i] = side[j] = false;
                }
            }
        }
    }
};

RectangularGrid

| 18:11

問題文

436.45->498.51 / 500

widht×height のグリッドに含まれる長方形(ただし正方形は除外)の数を求めよ、という問題。解法はすぐに思いついた。

class RectangularGrid {
public:
    long long countRectangles(int width, int height) {
        long long rectangles = 0;
        for (int w = 1; w <= width; w++) {
            for (int h = 1; h <= height; h++) {
                if (w == h) continue;
                rectangles += (width-w+1) * (height-h+1);
            }
        }
        return rectangles;
    }
};

Yahtzee

| 11:48

問題文

245.61->249.76 / 250

極めて簡単な問題。

class YahtzeeScore {
public:
    int maxPoints(vector <int> toss) {
        vector<int> sum(7, 0);
        for (int i = 0; i < toss.size(); i++)
            sum[toss[i]] += toss[i];
        return *max_element(sum.begin(), sum.end());
    }
};

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/caligue/20090502