Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-25

TeamPhoto

| 20:54

問題文, SRM 167

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

写真を撮る際に、身長の差の合計が最も小さくなるような並び方を考える。

232.95/750 (cheated)

class TeamPhoto {
public:
    int minDiff(vector <int> height) {
        n = height.size();
        vector<int> mem(height.begin()+3, height.end());
        sort(mem.begin(), mem.end());
        m = mem.size();

        int minSum = calc(height, mem, m/2);
        if (n%2 == 0)
            minSum = min(minSum, calc(height, mem, m/2+1));
        return minSum;
    }
private:
    int n, m;
    int calc(vector<int>& ht, vector<int>& mem, int mid) {
        return min(diff(ht[1], mem[0], mem[mid-1], ht[0]) +
                     diff(ht[0], mem[mid], mem[m-1], ht[2]),
                   diff(ht[2], mem[0], mem[mid-1], ht[0]) +
                     diff(ht[0], mem[mid], mem[m-1], ht[1]));
    }
    int diff(int a, int l, int h, int b) {
        return h-l + min(abs(a-l)+abs(b-h), abs(a-h)+abs(b-l));
    }
}

JohnieJohnie2013/02/16 22:15Check that off the list of things I was cofnsued about.

lpzworxlpzworx2013/02/17 21:13EhdvUV <a href="http://lggmfstpruis.com/">lggmfstpruis</a>

kdwdegjekdwdegje2013/02/18 05:09QCIf4X , [url=http://nxklzrjfqokk.com/]nxklzrjfqokk[/url], [link=http://iopulhzspqez.com/]iopulhzspqez[/link], http://vwnoyqhqksel.com/

kfuflfxdkfuflfxd2013/02/19 19:10JRh8jp , [url=http://ybazmifswqhs.com/]ybazmifswqhs[/url], [link=http://ceackqdzvvcl.com/]ceackqdzvvcl[/link], http://smwogahevohi.com/

2009-08-08

Orchard

| 20:44

SRM447 (DIV2)の結果は、300と500を通すことができ、Ratingは 1063 -> 1099 と上がった。両問題とももう少し速くサブミットできたのだが、コードを何度も確認していたため、しょぼいポイントになった。慎重になりすぎた。

問題文

幅優先探索(BFS)で解ける問題。実装に手間取った。

328.06/900 - 01:03:38

enum INDEX { Y_IDX=0, X_IDX=1, DIS_IDX=2};

class Orchard {
    public:
        vector <int> nextTree(vector <string> orchard) {
            const int size = orchard.size();
            vector<int> best = vector<int>(2);
            int longest = -1;
            for (int y = 0; y < size; y++) 
                for (int x = 0; x < size; x++)
                    if (orchard[y][x] == '-') {
                        set<vector<int> > visited;
                        queue<vector<int> > Q;
                        vector<int> tmp(3);
                        tmp[Y_IDX]=y; tmp[X_IDX]=x; tmp[DIS_IDX] = 0;
                        Q.push(tmp);
                        while (!Q.empty()) {
                            vector<int> v = Q.front(); Q.pop();
                            if (v[Y_IDX] < 0 || v[Y_IDX] >= size ||
                                    v[X_IDX] < 0 || v[X_IDX] >= size ||
                                    orchard[v[Y_IDX]][v[X_IDX]] == 'T') {
                                if (v[DIS_IDX] > longest) {
                                    longest = v[DIS_IDX];
                                    best[Y_IDX] = y + 1;
                                    best[X_IDX] = x + 1;
                                }
                                break;
                            }
                            tmp = vector<int>(v.begin(), v.begin()+2);
                            if (visited.find(tmp) != visited.end()) continue;
                            visited.insert(tmp);
                            vector<int> newV(3); 
                            newV[DIS_IDX] = v[DIS_IDX] + 1;
                            newV[Y_IDX]=v[Y_IDX]+1; newV[X_IDX]=v[X_IDX]; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]-1; newV[X_IDX]=v[X_IDX]; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]; newV[X_IDX]=v[X_IDX]+1; Q.push(newV);
                            newV[Y_IDX]=v[Y_IDX]; newV[X_IDX]=v[X_IDX]-1; Q.push(newV);
                        }
                    }
            return best;
        }
};

Animation

| 19:40

問題文

粒子の動き。強引に解きすぎて、バグが増え、時間がかかった。

150.00/500 - 00:57:22

class Animation {
    public:
        vector <string> animate(int speed, string init) {
            const int len = init.length();
            const static char RIGHT = '1';
            const static char LEFT = '2';
            string pre(init);
            for (int i = 0; i < len; i++) {
                if (pre[i] == 'R') pre[i] = RIGHT;
                else if (pre[i] == 'L') pre[i] = LEFT;
                else pre[i] = 0;
            }
            vector <string> result;
            while (true) {
                string s(toX(pre));
                result.push_back(s);
                if (find(s.begin(),s.end(),'X') == s.end())
                    break;
                s = string(len, 0);
                for (int i = 0; i < len; i++) {
                    int d;
                    switch (pre[i]) {
                    case RIGHT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        break;
                    case LEFT:
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    case RIGHT+LEFT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    }
                }
                pre = s;
            }
            return result;
        }
    private:
        string toX(const string& s) {
            string ret(s.length(), '.');
            for (int i = 0; i < s.length(); i++)
                if (s[i] != 0)
                    ret[i] = 'X';
            return ret;
        }
};

EyeDrops

| 19:36

問題文

目薬をする最適な間隔を求める。DIV2のeasyにしては難しい問題。すぐには解法が思いつかなかったが、Examplesを見て、2種類のケースが考えられることがわかり、解けた。

238.97/300

class EyeDrops {
    public:
        double closest(int sleepTime, int k) {
            double dk = static_cast<double>(k);
            if (sleepTime <= 24/dk)
                return 24*60/dk;
            else
                return (24-sleepTime)*60/(dk-1);
        }
};

ewnfzgewnfzg2011/02/28 00:358HHlV6 <a href="http://nfypkepkeych.com/">nfypkepkeych</a>, [url=http://azgnisbcmhab.com/]azgnisbcmhab[/url], [link=http://jedmlehhrowo.com/]jedmlehhrowo[/link], http://pqvizwthqdkq.com/