Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2010-01-30

TeXLeX

| 22:45

問題文, SRM 178

'^' のみが特別な入力である入力文字列のASCII値を返せ、という問題。この '^' をどのように処理するかが問題の肝。

この問題を解くには適宜文字列を変換ルールにしたがって1文字目から変換していく必要がある。基本的には変換ルールのとおりに機能を実装すればいい。注意する点としてはルール1を適用すると、値がchar型ではオーバーフローする場合があるので、それ対応する必要がある(僕は気づけなかったために、システムテストで落とされた。

238.78/600 (1 failed)

class TeXLeX {
public:
    vector <int> getTokens(string input) {
        vector <int> result;
        const int len = input.length();
        for (int i = 0; i < len; i++) {
            if (input[i] == '^') {
                if (i >= len-2) {
                    result.push_back('^');
                } else if (input[i+1] != '^') {
                    result.push_back('^');
                } else if (i < len-3 && isHex(input[i+2]) && isHex(input[i+3])) {
                    unsigned int c;
                    sscanf(input.substr(i+2,2).c_str(), "%x", &c);
                    if (c >= 128) {
                        result.push_back(c);
                        i += 3;
                    } else {
                        input[i+3] = (char) c;
                        i += 2;
                    }
                } else if (input[i+2] > 63) {
                    input[i+2] -= 64;
                    i += 1;
                } else {
                    input[i+2] += 64;
                    i += 1;
                }
            } else {
                result.push_back(input[i]);
            }
        }
        return result;
    }
private:
    bool isHex(const char c) {
        return ('0'<=c && c<='9') || ('a'<=c && c<='f');
    }
};

CamiCami2011/08/31 01:54Hey hey hey, take a gaednr at what' you've done

ifhwgxmyifhwgxmy2011/09/01 01:26IyxF2c <a href="http://zzvvdkadzyzw.com/">zzvvdkadzyzw</a>

vsyaesivsyaesi2011/09/03 20:20bbeGDx <a href="http://xqcimzgfyxjv.com/">xqcimzgfyxjv</a>

2009-11-06

NotTwo

| 06:54

問題文, SRM 452

石と石のユークリッド距離が2とならないように石を置いていくとき、最大で石を何個置けるか。

少し考えたけど、どのように並べれば最大になるのかわからなかったので、とりあえず(0,0)から貪欲に置けるだけ置くアルゴリズムを実装。そして、例題は通ったので、自信はないが提出。そしたら、システムテストも通ってしまった。これでいいのか。どう証明すればいいんだろう。

436.36/500

class NotTwo {
public:
    int maxStones(int w, int h) {
        vector<vector<int> > b(h, vector<int>(w, '_'));
        int count = 0;
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                for (int i = 0; i < 4; i++) {
                    // 追記: 左と上に石が置いてあるかどうかを調べるだけでよくて、 
                    //       右と下を調べる必要はなかった。
                    const static int d[4][2] = {
                        {2,0}, {-2,0}, {0,2}, {0,-2} };
                    const int ny = y + d[i][0];
                    const int nx = x + d[i][1];
                    if (0<=ny&&ny<h && 0<=nx&&nx<w && b[ny][nx] == '*')
                        break;
                    if (i == 3) {
                        b[y][x] = '*';
                        count++;
                    }
                }
            }
        }
        return count;
    }
};

mimanamimana2009/12/30 09:25NotTwoで
if (i == 3) {
としている理由を教えていただけませんか?

caliguecaligue2010/01/30 23:04しばらくの間、このブログのチェックをしていなくて、コメントに気づきませんでした。

NotTwo で
if (i == 3) {
としているのは、この方法ではi=0,1,2,3とそれぞれの干渉する場所に石が置かれていないかを確認していて、i=3 までbreakされずにこのif文まで来たときには干渉する場所に石が置かれていないと判断でき、位置(x,y)に石を置けます。なので、if (i==3) のブロック内ではその位置(x,y)に石を置いて、置けた石の数(count)を増やす処理を実行させてます。

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

IncredibleMachine

| 13:44

問題文, SRM 440

加速度を求める。二分探索法で解ける。以下はコード中の数式に関するメモ。

問題文から、

 d = v_0 t + 0.5at^2,

 v_1 = v_0 + at.

t を解の公式を用いて求めると、

 t = \frac{-v_0 + \sqrt{v_0^2+2ad} }{a}.

よって、

 v_1 = sqrt{v_0^2+2ad}.

地点(x_i,y_i)から地点(x_{i+1},y_{i+1})への移動距離d_iは三平方の定理により

 d_i = \sqrt{(x_i-x_{i+1})^2 + (y_i-y_{i+1})^2}.

この距離を移動するのに必要な時間 t_iは、この間の速度の平均が (v_0+v_1)/2なので、

 t_i = \frac{2d}{v_0+v_1}.

113.73/250 (cheated)

double squ(const double x) { return x*x; }

class IncredibleMachine {
public:
    double gravitationalAcceleration(vector <int> x, vector <int> y, int T) {
        double lg=0, hg=1e30;
        for (int step = 0; step < 3000; step++) {
            double g = (lg+hg) / 2;
            double v0=0, time=0;
            for (int i = 0; i < x.size()-1; i++) {
                double v1 = sqrt(squ(v0) + 2*g*(y[i]-y[i+1]));
                double d = sqrt(squ(x[i]-x[i+1]) + squ(y[i]-y[i+1]));
                time += 2*d / (v0+v1);
                v0 = v1;
            }
            if (time > T) lg = g;
            else hg = g;
        }
        return lg;
    }
};

MaguyMaguy2012/11/16 16:52Finally! This is just what I was looknig for.

zyjcemlzyjceml2012/11/18 07:41mKV8c4 , [url=http://osvnksruetrt.com/]osvnksruetrt[/url], [link=http://mgxdumvbmsag.com/]mgxdumvbmsag[/link], http://ninqkbvhlrwd.com/

bremwwuhxbremwwuhx2012/11/18 14:11IzzeKk <a href="http://bcfzmpdxhygr.com/">bcfzmpdxhygr</a>

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