Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-10-14

OmahaLow

| 14:30

問題文, SRM 206

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

あるトランプゲームにおいて、最善の手を求める。

121.31/250 (cheated)

class OmahaLow {
public:
    string low(string sharedCards, string playersCards) {
        string ret = "";
        sort(sharedCards.rbegin(), sharedCards.rend());
        sort(playersCards.rbegin(), playersCards.rend());
        do {
            do {
                string s = sharedCards.substr(0,3) + playersCards.substr(0,2);
                sort(s.rbegin(), s.rend());
                if (s[0] >= '9') continue;
                int i;
                for (i = 0; i < 4; i++) if (s[i] == s[i+1]) break;
                if (i < 4) continue;
                if (ret == "" || s < ret) ret = s;
            } while (next_permutation(playersCards.rbegin(), playersCards.rend()));
        } while (next_permutation(sharedCards.rbegin(), sharedCards.rend()));
        return ret;
    }
};

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-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-09-22

FanFailure

| 20:26

問題文, SRM 195

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

プロセッサを充分に冷やすために、壊れても大丈夫かもしれない最大のファンの数と、壊れても絶対に大丈夫なファンの数を求める。問題文がわかりにくいが、解法は単純。

170.53/250

class FanFailure {
public:
    vector <int> getRange(vector <int> capacities, int minCooling) {
        vector <int> result(2, 0);
        sort(capacities.begin(), capacities.end());
        int sum = accumulate(capacities.begin(), capacities.end(), 0);
        for (int i = 0; i < capacities.size(); i++) {
            sum -= capacities[i];
            if (sum < minCooling) break;
            result[0]++;
        }
        sum = accumulate(capacities.begin(), capacities.end(), 0);
        for (int i = capacities.size()-1; i >= 0; i--) {
            sum -= capacities[i];
            if (sum < minCooling) break;
            result[1]++;
        }
        return result;
    }
};

Fifteen

| 07:35

問題文, SRM 172

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

言った数の内、3つの数の合計が15になったら勝ちのゲームにおいて、挑戦者(patron)が勝てるかどうか。TutorialにTick-Tack-Toeの変装だと書かれていたので、どのように解くか考えたが、少し強引な方法しか考えつかなかった。

204.31/500

class Fifteen {
public:
    string outcome(vector <int> moves) {
        for (int n = 1; n <= 9; n++) {
            if (find(moves.begin(),moves.end(),n) == moves.end()) {
                vector<int> newMoves(moves);
                newMoves.push_back(n);
                if (isWin(newMoves, true)) {
                    char res[10];
                    sprintf(res, "WIN %d", n);
                    return string(res);
                }
            }
        }
        return "LOSE";
    }
private:
    bool isWin(const vector<int>& moves, const bool isPatron) {
        for (int i = isPatron? 1:0; i < moves.size(); i += 2)
            for (int j = i+2; j < moves.size(); j += 2)
                for (int k = j+2; k < moves.size(); k += 2)
                    if (moves[i]+moves[j]+moves[k] == 15)
                        return true;
        for (int n = 1; n <= 9; n++)
            if (find(moves.begin(),moves.end(),n) == moves.end()) {
                vector<int> newMoves(moves);
                newMoves.push_back(n);
                if (isWin(newMoves, !isPatron))
                    return false;
            }
        return true;
    }
};

2009-09-21

CityLink

| 20:12

問題文, SRM 170

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

全ての都市をつなげるにはどのぐらいの期間が必要か。Floyd-Warshall法の変形法で解ける。

398.94/550

class CityLink {
public:
    int timeTaken(vector <int> x, vector <int> y) {
        const int n = x.size();
        vector<vector<int> > D(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (x[i] == x[j])
                    D[i][j] = (abs(y[i]-y[j])+1) / 2;
                else if (y[i] == y[j])
                    D[i][j] = (abs(x[i]-x[j])+1) / 2;
                else
                    D[i][j] = max(abs(x[i]-x[j]), abs(y[i]-y[j]));
            }

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    D[i][j] = min(D[i][j], max(D[i][k], D[k][j]));

        int result = 0;
        for (int i = 0; i < n; i++)
            result = max(result, *max_element(D[i].begin(), D[i].end()));
        return result;
    }
};

HonneyHonney2011/08/30 15:59A miunte saved is a minute earned, and this saved hours!

wyemhhwwyemhhw2011/09/01 00:575HxeEE <a href="http://ybnebnwcovjs.com/">ybnebnwcovjs</a>

nibmiiinibmiii2011/09/01 16:45G2F1Yz , [url=http://sawuiwwztonv.com/]sawuiwwztonv[/url], [link=http://afgrzejquery.com/]afgrzejquery[/link], http://qcxtuwjadjsa.com/

yadxlbnejvmyadxlbnejvm2011/09/03 17:37kFklXm <a href="http://cmwvbpywnvnz.com/">cmwvbpywnvnz</a>

miiugpaimiiugpai2011/09/04 02:04wqBYC6 , [url=http://tmkxgkbnxbnf.com/]tmkxgkbnxbnf[/url], [link=http://zmtmrmbpaobv.com/]zmtmrmbpaobv[/link], http://ulmzbcooroqn.com/

IdelIdel2013/02/17 07:36I can aalredy tell that's gonna be super helpful.

2009-09-20

MatArith

| 21:03

問題文, TCI '02 Round 2

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

行列同士の足し算と掛け算。

169.75/500 (1 failed)

typedef long long int64;

class MatArith {
public:
    vector <string> calculate(vector <string> A, vector <string> B, vector <string> C, string equation) {
        return print(calc(parse(A),parse(B),parse(C),equation));
    }
private:
    vector<string> print(vector<vector<int64> > M) {
        const int R = M.size();
        if (R == 0) return vector<string>();
        const int C = M[0].size();
        vector<string> ret(R);
        for (int r = 0; r < R; r++) {
            ostringstream oss;
            for (int c = 0; c < C; c++) {
                if (c >= 1) oss << " ";
                oss << M[r][c];
            }
            ret[r] = oss.str();
        }
        return ret;
    }
    vector<vector<int64> > parse(vector<string>& M) {
        const int R = M.size();
        vector<vector<int64> > ret(R);
        for (int r = 0; r < R; r++) {
            istringstream iss(M[r]);
            int t;
            while (iss >> t) ret[r].push_back(t);
        }
        return ret;
    }
    vector<vector<int64> > calc(const vector<vector<int64> > A,
            const vector<vector<int64> > B, const vector<vector<int64> > C,
            const string& equation) {
        stack<vector<vector<int64> > > matStack;
        int opStack = 0;
        for (int i = 0; i < equation.size(); i++) {
            if (equation[i] == '+') {
                opStack++;
            } else if (equation[i] == '*') {
                vector<vector<int64> > T1 = matStack.top(); matStack.pop();
                i++;
                vector<vector<int64> > T2;
                if (equation[i] == 'A') T2 = A;
                else if (equation[i] == 'B') T2 = B;
                else  T2 = C;
                vector<vector<int64> > M = matmul(T1, T2);
                if (M.size() == 0) return M;
                matStack.push(M);
            } else if (equation[i] == 'A') {
                matStack.push(A);
            } else if (equation[i] == 'B') {
                matStack.push(B);
            } else {
                matStack.push(C);
            }
        }
        while (opStack-- > 0) {
            vector<vector<int64> > T1 = matStack.top(); matStack.pop();
            vector<vector<int64> > T2 = matStack.top(); matStack.pop();
            vector<vector<int64> > M = matadd(T1, T2);
            if (M.size() == 0) return M;
            matStack.push(M);
        }
        return matStack.top();
    }
    vector<vector<int64> > matmul(const vector<vector<int64> >& A,
            const vector<vector<int64> >& B) {
        const int RA = A.size(), CA = A[0].size();
        const int RB = B.size(), CB = B[0].size();
        if (CA != RB) return vector<vector<int64> >();
        vector<vector<int64> > M(RA, vector<int64>(CB,0));
        for (int i = 0; i < RA; i++) {
            for (int j = 0; j < CB; j++) {
                for (int k = 0; k < CA; k++) {
                    M[i][j] += A[i][k] * B[k][j];
                }
                if (M[i][j] > 2147483647ll || M[i][j] < -2147483648ll)
                    return vector<vector<int64> >();
            }
        }
        return M;
    }
    vector<vector<int64> > matadd(const vector<vector<int64> >& A,
            const vector<vector<int64> >& B) {
        const int RA = A.size(), CA = A[0].size();
        const int RB = B.size(), CB = B[0].size();
        if (RA != RB || CA != CB) return vector<vector<int64> >();
        vector<vector<int64> > M(RA, vector<int64>(CA,0));
        for (int i = 0; i < RA; i++) {
            for (int j = 0; j < CA; j++) {
                M[i][j] += A[i][j] + B[i][j];
                if (M[i][j] > 2147483647ll || M[i][j] < -2147483648ll)
                    return vector<vector<int64> >();
            }
        }
        return M;
    }
};

2009-09-19

WordFind

| 10:10

問題文, SRM 232

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

worldListの単語は2次元配列gridのどこに隠れているのか。

171.37/250

class WordFind {
public:
    vector <string> findWords(vector <string> grid, vector <string> wordList) {
        const int H = grid.size();
        const int W = grid[0].size();
        vector <string> result(wordList.size(), "");
        for (int i = 0; i < wordList.size(); i++) {
            const int len = wordList[i].length();
            for (int r = 0; r < H; r++) {
                for (int c = 0; c < W; c++) {
                    const static int DIR_KINDS = 3;
                    const static int d[DIR_KINDS][2] = { {1,0}, {0,1}, {1,1} };
                    for (int j = 0; j < DIR_KINDS; j++) {
                        if (r+len*d[j][0] > H) continue;
                        if (c+len*d[j][1] > W) continue;
                        for (int k = 0; k < len; k++) {
                            if (wordList[i][k] != grid[r+k*d[j][0]][c+k*d[j][1]]) break;
                            if (k == len-1) {
                                ostringstream pos;
                                pos << r << " " << c;
                                result[i] = pos.str();
                                break;
                            }
                        }
                        if (result[i] != "") break;
                    }
                    if (result[i] != "") break;
                }
                if (result[i] != "") break;
            }
        }
        return result;
    }
};

YulyYuly2012/11/15 07:39You've hit the ball out the park! Incrieldbe!

ogjjxpbfedogjjxpbfed2012/11/16 05:36fSvQ3Y <a href="http://opkomgzlgoxs.com/">opkomgzlgoxs</a>

lllebwlllebw2012/11/17 05:07hx1oWF , [url=http://cdmmhpymcwvw.com/]cdmmhpymcwvw[/url], [link=http://zhernoocdpab.com/]zhernoocdpab[/link], http://pnimqosbodna.com/

fjpobhvgxctfjpobhvgxct2012/11/17 12:09CrZUBe <a href="http://gitnhbscrxca.com/">gitnhbscrxca</a>

wahfhgiylpwahfhgiylp2012/11/17 21:39wFLUSt , [url=http://eovjxcvzlscm.com/]eovjxcvzlscm[/url], [link=http://kpmczprsyijg.com/]kpmczprsyijg[/link], http://lqammhsdbqsp.com/

2009-09-18

Cafeteria

| 19:21

問題文, SRM 229

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

学食が閉まる前に大学に着くには遅くとも何時何分に家を出ればよいのか。ややこしく考えすぎた。素直にBrute forceな方法で解けばすぐに解けた問題。

113.94/250

class Cafeteria {
public:
    string latestTime(vector <int> offset, vector <int> walkingTime, vector <int> drivingTime) {
        const static int closeTime = 14*60 + 30;
        const static int interval = 10;
        const int n = offset.size();
        int latest = 0;
        for (int i = 0; i < n; i++) {
            for (int j = closeTime/interval; j >= 0; j--) {
                int time = interval*j + offset[i];
                if (time+drivingTime[i] <= closeTime) {
                    latest = max(latest, time-walkingTime[i]);
                    break;
                }
            }
        }
        char result[10];
        int hh = latest/60;
        if (hh > 12) hh -= 12;
        int mm = latest%60;
        sprintf(result, "%02d:%02d", hh, mm);
        return string(result);
    }
};

LaticiaLaticia2011/08/30 13:38AFAIC that's the best asnewr so far!

parpntparpnt2011/09/01 01:49bhJbxd <a href="http://zdrhotngocjb.com/">zdrhotngocjb</a>

xtmxmyqetycxtmxmyqetyc2011/09/01 16:48NJOJOQ , [url=http://wrzwsyjcsqsw.com/]wrzwsyjcsqsw[/url], [link=http://wfmzjrcnpugt.com/]wfmzjrcnpugt[/link], http://iipgxojwlgto.com/

xhxqwjfozxhxqwjfoz2011/09/03 18:07AyKuiE <a href="http://bcyztvxrbbno.com/">bcyztvxrbbno</a>

fgetygzmhsfgetygzmhs2011/09/04 01:21sWPIEu , [url=http://tsztjxihmrvp.com/]tsztjxihmrvp[/url], [link=http://leqihxtiuisd.com/]leqihxtiuisd[/link], http://mqdfcrmvtkyt.com/

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-15

GeneralChess

| 18:47

問題文, SRM 197

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

全てのナイトから脅かされているマスの位置を探す。

219.34/250

class GeneralChess {
public:
    vector <string> attackPositions(vector <string> pieces) {
        const int n = pieces.size();
        map<pair<int,int>,int> count;
        for (int i = 0; i < n; i++) {
            int x, y;
            sscanf(pieces[i].c_str(), "%d,%d", &x, &y);
            for (int dx = -2; dx <= 2; dx++)
                for (int dy = -2; dy <= 2; dy++) {
                    if (dx*dx+dy*dy != 5) continue;
                    count[make_pair(x+dx,y+dy)]++;
                }
        }

        vector<string> result;
        for (map<pair<int,int>,int>::const_iterator itr = count.begin();
                itr != count.end(); itr++)
            if (itr->second == n) {
                ostringstream oss;
                oss << itr->first.first << ',' << itr->first.second;
                result.push_back(oss.str());
            }
        return result;
    }
};