Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-10-23

PizzaDelivery

| 07:29

問題文, SRM 451

2人の配達人を使って、ピザを配達し終えるのにかかる最短時間を求める。

解くのに2時間強かかった。しょうもないバグにより3回、時間制限により1回、システムテストで落とされた。解法はBFS+Brute Forceなので割と単純だが、異常に調子が良い時でないと本番の時間内にバグなしで解ける気がしない。

300.00/1000 (4-failed)

const static int INFTY = INT_MAX/2;

class PizzaDelivery {
    public:
        int deliverAll(vector <string> terrain) {
            const int H = terrain.size();
            const int W = terrain[0].size();
            vector<pair<int,int> > piza;
            pair<int,int> r;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (terrain[y][x] == 'X') {
                        r = make_pair(y, x);
                    } else if (terrain[y][x] == '$') {
                        piza.push_back(make_pair(y,x));
                    }
                }

            int D[100];
            int T[100][100];
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++)
                    T[y][x] = INFTY;
            T[r.first][r.second] = 0;
            queue<pair<int,int> > Q;
            Q.push(r);
            while (!Q.empty()) {
                pair<int,int> a = Q.front(); Q.pop();
                const int y = a.first, x = a.second;
                const static int d[4][2] = {
                    {0,1}, {0,-1}, {1,0}, {-1,0} };
                for (int i = 0; i < 4; i++) {
                    const int ny = y + d[i][0];
                    const int nx = x + d[i][1];
                    if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                        if (!isdigit(terrain[ny][nx]) || !isdigit(terrain[y][x])) {
                            if (T[y][x]+2 < T[ny][nx]) {
                                T[ny][nx] = T[y][x] + 2;
                                Q.push(make_pair(ny, nx));
                            }
                            continue;
                        }
                        if (abs(terrain[ny][nx]-terrain[y][x]) == 0 && 
                                T[y][x]+1 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 1;
                            Q.push(make_pair(ny, nx));
                        } else if (abs(terrain[ny][nx]-terrain[y][x]) == 1 && 
                                T[y][x]+3 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 3;
                            Q.push(make_pair(ny, nx));
                        }
                    }
                }
            }
            for (int i = 0; i < piza.size(); i++) {
                D[i] = T[piza[i].first][piza[i].second];
                if (D[i] == INFTY) return -1;
            }

            int minTime = INFTY;
            for (int i = 0; i < 1<<(piza.size()-1); i++) {
                bitset<20> pat(i);
                vector<int> vboy1, vboy2;
                for (int j = 0; j < piza.size(); j++) {
                    if (pat[j]) vboy1.push_back(D[j]);
                    else        vboy2.push_back(D[j]);
                }
                int boy1=0, boy2=0;
                if (vboy1.size() > 0)
                    boy1 = 2*accumulate(vboy1.begin(), vboy1.end(), 0) 
                        - *max_element(vboy1.begin(), vboy1.end());
                if (vboy2.size() > 0)
                    boy2 = 2*accumulate(vboy2.begin(), vboy2.end(), 0) 
                        - *max_element(vboy2.begin(), vboy2.end());
                //cout << pat << " " << boy1 << " " << boy2 << endl;
                minTime = min(minTime, max(boy1, boy2));
            }
            return minTime;
        }
};

nphuuejznphuuejz2011/02/28 17:01PX5gMr <a href="http://thxvtmuhvzkh.com/">thxvtmuhvzkh</a>, [url=http://aegsueyzfdwj.com/]aegsueyzfdwj[/url], [link=http://juwwqktqnkxe.com/]juwwqktqnkxe[/link], http://fuvdtrdrrxop.com/

2009-10-12

TopographicalImage

| 19:19

問題文, SRM 210

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

各頂上から上らずに到達することができる地点の数を数える。ただし、同じ地点は数えない。

390.67/1000

class TopographicalImage {
public:
    vector <int> calcPeakAreas(vector <string> topoData) {
        H = topoData.size();
        W = topoData[0].size();
        result.clear();
        while (true) {
            int mx=0, my=0;
            char mh=0;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (topoData[y][x] != VISITED && topoData[y][x] > mh) {
                        my = y;
                        mx = x;
                        mh = topoData[y][x];
                    }
                }
            if (mh == 0) break;
            result.push_back(0);
            visit(my, mx, mh, topoData);
        }
        return result;
    }
private:
    const static char VISITED = 127;
    int H, W;
    vector <int> result;
    void visit(const int py, const int px, const char ph, 
            vector<string>& topoData) {
        result.back()++;
        topoData[py][px] = VISITED;
        for (int dy = -1; dy <= 1; dy++)
            for (int dx = -1; dx <= 1; dx++) {
                if (dy == 0 && dx == 0) continue;
                const int ny = py + dy;
                const int nx = px + dx;
                if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                    const int nh = topoData[ny][nx];
                    if (nh <= ph)
                        visit(ny, nx, nh, topoData);
                }
            }
    }
};

2009-09-17

LargestCircle

| 19:05

問題文, SRM 212

Algorithm Tutorials -- How to Find a Solutionから。

マークされたマスを通らない円を描くとき、描くことができる最大の円の半径を求める。円がマスを通るかどうかの判定をどのように実装すればいいのかわからなかった。

428.44/1000 (cheated)

int square(const int x) { return x * x; }

class LargestCircle {
public:
    int radius(vector <string> grid) {
        const int H = grid.size();
        const int W = grid[0].size();
        for (int rad = min(H/2,W/2); rad >= 1; rad--) {
            const int sr = square(rad);
            for (int cy = rad; cy <= H-rad; cy++)
                for (int cx = rad; cx <= W-rad; cx++) {
                    bool passed = true;
                    for (int y = 0; y < H; y++) {
                        for (int x = 0; x < W; x++) {
                            if (grid[y][x] != '#') continue;
                            const int dy = y - cy;
                            const int dx = x - cx;
                            const int p0 = square(dy)   + square(dx);
                            const int p1 = square(dy+1) + square(dx);
                            const int p2 = square(dy)   + square(dx+1);
                            const int p3 = square(dy+1) + square(dx+1);
                            if (p0<=sr && p1<=sr && p2<=sr && p3<=sr) continue;
                            if (p0>=sr && p1>=sr && p2>=sr && p3>=sr) continue;
                            passed = false;
                            break;
                        }
                        if (!passed) break;
                    }
                    if (passed) return rad;
                }
        }
        return 0;
    }
};

2009-09-06

CaptureThemAll

| 19:09

問題文, SRM 207

Algorithm Tutorials -- How to Find a Solutionから。

Knightだけで、RookとQueenをとるのに最低何ステップかかるか。BFSで解ける。どのように実装すればよいのかで迷った。1回目と2回目に出したときは、setを使って同じ条件の時にはもう調べないようにしなかったために、queueの許容量を超えてしまい、例外が発生して落ちた(例外が発生しなくても時間制限に引っかかったと思うが)。

300.00/1000 (2 failed)

struct State {
    const static int ROOK_VAL = 1;
    const static int QUEEN_VAL = 10;
    const static int BOTH_VAL = ROOK_VAL+QUEEN_VAL;
    pair<int,int> p;
    int step, val;
    State() {}
    State(const pair<int,int> p) : p(p) {
        step = 0;
        val = 0;
    }
    State(const pair<int,int> p, const int step) : p(p), step(step) {
        val = 0;
    }
};
bool operator< (const State& a, const State& b) {
    if (a.step < b.step) {
        return true;
    } else if (a.step > b.step) {
        return false;
    } else {
        if (a.val > b.val) {
            return true;
        } else if (a.val < b.val) {
            return false;
        } else {
            return a.p < b.p;
        }
    }
}

class CaptureThemAll {
public:
    int fastKnight(string knight, string rook, string queen) {
        const pair<int,int> rPos = getPos(rook);
        const pair<int,int> qPos = getPos(queen);
        queue<State> Q;
        Q.push(State(getPos(knight)));
        set<State> checked;
        checked.insert(Q.front());
        while (!Q.empty()) {
            State k = Q.front(); Q.pop();
            if (k.val == State::BOTH_VAL) return k.step;
            for (int dy = -2; dy <= 2; dy++) {
                for (int dx = -2; dx <= 2; dx++) {
                    if (dy*dy+dx*dx != 5) continue;
                    const int ny = k.p.first + dy;
                    const int nx = k.p.second + dx;
                    if (0<=ny&&ny<BOARD_SZ && 0<=nx&&nx<BOARD_SZ) {
                        State next(make_pair(ny,nx), k.step+1);
                        if (k.val%10 == 1 || next.p == rPos) 
                            next.val += State::ROOK_VAL;
                        if (k.val/10 == 1 || next.p == qPos)
                            next.val += State::QUEEN_VAL;
                        if (checked.find(next) == checked.end()) {
                            Q.push(next);
                            checked.insert(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
private:
    const static int BOARD_SZ = 8;
    pair<int,int> getPos(const string& s) {
        return make_pair(s[1]-'1', s[0]-'a');
    }
};

2009-09-05

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

2009-08-20

Poetry

| 13:47

問題文, SRM 170

与えられた詩が、どのように音韻を踏んでいるのかを調べる。

377.34/1000

class Poetry {
public:
    string rhymeScheme(vector <string> poem) {
        char label = 'a';
        vector<vector<string> > substrings(poem.size());
        string result(poem.size(), ' ');
        for (int i = 0; i < poem.size(); i++) {
            if (poem[i].length() == 0) continue;
            string s = tolowerString(poem[i]);
            istringstream iss(s);
            string last(""), tmp;
            while (iss >> tmp) last = tmp;
            if (last == "")
                continue;
            const int len = last.length();
            bool isPreVowel = false;
            for (int j = len-1; j >= 0; j--) {
                const char c = last[j];
                bool isVowel = (j!=len-1 && j!=0 && c=='y')
                    || c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
                if (isPreVowel && !isVowel) 
                    substrings[i].push_back(last.substr(j+1));
                isPreVowel = isVowel;
            }
            if (isPreVowel) substrings[i].push_back(last);
            for (int j = 0; j <= substrings[i].size(); j++) {
                if (j == substrings[i].size()) {
                    result[i] = label;
                    label++;
                    if (label > 'z') label = 'A';
                    break;
                }
                for (int k = 0; k < i; k++)  {
                    if (find(substrings[k].begin(), substrings[k].end(), substrings[i][j])
                            != substrings[k].end()) {
                        result[i] = result[k];
                        break;
                    }
                }
                if (result[i] != ' ') break;
            }

        }
        return result;
    }
private:
    string tolowerString(string s) {
        for (int i = 0; i < s.length(); i++)
            s[i] = tolower(s[i]);
        return s;
    }
};

2009-08-11

FairWorkload

| 13:17

問題文

仕事をなるべく均等になるように割り振る。良問。Level-2の問題より解きやすかった。

532.87/1000 - 00:32:37

class FairWorkload {
    public:
        int getMostWork(vector <int> folders, int workers) {
            amounts = vector<int>(workers, 0);
            maxOptimalAmount = INT_MAX;
            go(folders, 0, workers, 0);
            return maxOptimalAmount;
        }
    private:
        int maxOptimalAmount;
        vector<int> amounts;
        void go(const vector<int>& folders, const int f_id, 
                const int workers, const int w_id) {
            if (f_id == folders.size()) {
                for (int i = 0; i < workers; i++)
                    if (amounts[i] == 0)
                        return;
                maxOptimalAmount = min(maxOptimalAmount, 
                        *max_element(amounts.begin(),amounts.end()));
                return;
            }
            if (maxOptimalAmount <= amounts[w_id]) return;
            if (w_id == workers) return;
            amounts[w_id] += folders[f_id];
            go(folders, f_id+1, workers, w_id);
            amounts[w_id] -= folders[f_id];
            if (w_id+1 == workers) return;
            amounts[w_id+1] += folders[f_id];
            go(folders, f_id+1, workers, w_id+1);
            amounts[w_id+1] -= folders[f_id];
        }
};

OliviaOlivia2011/07/09 22:49Ppl like you get all the birans. I just get to say thanks for he answer.

cganpmvkaacganpmvkaa2011/07/10 00:21ozUmeq <a href="http://pjfcqeeeqmnr.com/">pjfcqeeeqmnr</a>

gkbfwfvcbgkbfwfvcb2011/07/10 21:09Bo1aDa , [url=http://xrkdnugczyzj.com/]xrkdnugczyzj[/url], [link=http://sbngsfqxhlpy.com/]sbngsfqxhlpy[/link], http://safjlfwoassi.com/

uxpnpunauxpnpuna2011/07/11 20:32crHIwv <a href="http://fodsgqzsvyim.com/">fodsgqzsvyim</a>

mhhaaumhhaau2011/07/12 21:58da56vU , [url=http://tqvvgrxdnlwt.com/]tqvvgrxdnlwt[/url], [link=http://ofcuaexemicz.com/]ofcuaexemicz[/link], http://shzifphpejdh.com/

2009-08-10

WindowWasher

| 14:08

問題文

窓掃除にかかる最短時間を求める。Level-3の問題なのに、あっさり解けてしまった。良い解法がすぐに思いつけば、これぐらいの速度で解けるのか。個人的にはLevel-2の問題の方が難しく感じた。

881.11/1100 - 00:14:58

class WindowWasher {
    public:
        int fastest(int width, int height, vector <int> washTimes) {
            const int numPeople = washTimes.size();
            for (int i = 0; i < numPeople; i++) 
                washTimes[i] *= height;
            vector<int> workTimes(numPeople, 0);
            while (width-- > 0) {
                int minIdx=-1, minTime=INT_MAX;
                for (int i = 0; i < numPeople; i++) {
                    int time = workTimes[i] + washTimes[i];
                    if (time < minTime) {
                        minTime = time;
                        minIdx = i;
                    }
                }
                workTimes[minIdx] += washTimes[minIdx];
            }
            return *max_element(workTimes.begin(), workTimes.end());
        }
};

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

ConvexPolygon

| 13:23

このDIV2の問題セットは簡単だった。

問題文

凸多角形の面積を求めるだけ。解法を調べながら解いたために、時間がかかった。計算幾何の勉強をする必要がある。

576.16/900 - 00:25:12

class ConvexPolygon {
    public:
        double findArea(vector <int> x, vector <int> y) {
            double area = 0;
            for (int i = 0; i+1 < x.size(); i++) {
                int x0 = x[i] - x[0];
                int y0 = y[i] - y[0];
                int x1 = x[i+1] - x[0];
                int y1 = y[i+1] - y[0];
                int cross = x0*y1 - x1*y0;
                area += cross;
            }
            return fabs(area/2);
        }
};

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/

2009-08-07

ShortPalindromes

| 12:58

問題文

与えられた文字列から作られる、最も短くて、辞書順で最初にくる回文を作れ、という問題。再帰+メモ化によって時間内に解ける問題。わからなくてEditorialを見た。思いつきそうでつかない解法だな。こういう問題は慣れれば解けるようになると思った。

572.72/1150 - 00:38:45 (cheated)

class ShortPalindromes {
    public:
        string shortest(string base) {
            memo.clear();
            return go(base);
        }
    private:
        map<string,string> memo;
        string go(const string& s) {
            if (memo.find(s) != memo.end()) 
                return memo[s];
            if (isPalindrome(s)) 
                return s;
            const int len = s.length();
            string ret;
            if (s[0] == s[len-1]) {
                ret = string(1,s[0]) + go(s.substr(1,len-2)) + string(1,s[0]);
            } else {
                ret = minStr(string(1,s[0]) + go(s.substr(1,len-1)) + string(1,s[0]),
                        string(1,s[len-1]) + go(s.substr(0,len-1)) + string(1,s[len-1]));
            }
            memo[s] = ret;
            return ret;
        }
        bool isPalindrome(const string& s) {
            const int len = s.length();
            for (int i = 0; i < len/2; i++)
                if (s[i] != s[len-i-1])
                    return false;
            return true;
        }
        string minStr(const string& a, const string& b) {
            if (a.length() < b.length()) {
                return a;
            } else if (a.length() > b.length()) {
                return b;
            } else if (a < b) {
                return a;
            } else {
                return b;
            }
        }
};