Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2010-02-03

Packhorses

| 06:13

問題文, SRM 179

自力で解けなかった。以下は Editorial で述べられている Brute force な解答。

165.0/550 (cheated)

class Packhorses {
public:
    int horses(int p, int x, int y) {
        int result = INT_MAX;
        for (int i = 0; i <= p; i++) {
            int xx = max(0, x-2*i);
            int yy = max(0, y-(p-i));
            result = min(result, p + (xx+2)/3 + (yy+1)/2);
        }
        return result;
    }
};

それと一定時間で解く方法が以下。最初の if (y%2 != 0) { ... } は、こうしないと (x,y) = (3a, 2b+1) (a,bは任意の自然数)の場合に対応出来ないから必要。

class Packhorses {
public:
    int horses(int p, int x, int y) {
        int rem = p;
        if (y%2 == 1) {
            y--;
            rem--;
        }
        if ((x+1)/2 < rem) {
            rem -= (x+1) / 2;
            x = 0;
            y -= rem;
            y = (y < 0) ? 0 : y;
        } else {
            x -= 2 * rem;
        }
        return p + (x+2)/3 + (y+1)/2;
    }
};

NelleNelle2011/07/10 03:50Shoot, who would have touhght that it was that easy?

eucmwztyzkeucmwztyzk2011/07/10 16:56z0NxqO <a href="http://hsgtzyqhmovt.com/">hsgtzyqhmovt</a>

wsahgnbbybpwsahgnbbybp2011/07/11 18:47rSe9kY , [url=http://eabtqfkuruwb.com/]eabtqfkuruwb[/url], [link=http://uzoqnjdenqul.com/]uzoqnjdenqul[/link], http://eulnzbieqxug.com/

fahoslsfahosls2011/07/12 18:23znpKbM <a href="http://lmfoqmdfvcpr.com/">lmfoqmdfvcpr</a>

dspfvndspfvn2011/07/12 22:56I7LUvz , [url=http://dqdjjrbohqdj.com/]dqdjjrbohqdj[/url], [link=http://mhsjmpzjdfmi.com/]mhsjmpzjdfmi[/link], http://uyelavyaiohl.com/

IceIce2013/02/18 17:06A million thnkas for posting this information.

ezbdugvezbdugv2013/02/19 02:06uJLKpj <a href="http://gtvcccrcfhuh.com/">gtvcccrcfhuh</a>

ezbdugvezbdugv2013/02/19 02:06uJLKpj <a href="http://gtvcccrcfhuh.com/">gtvcccrcfhuh</a>

ezbdugvezbdugv2013/02/19 02:06uJLKpj <a href="http://gtvcccrcfhuh.com/">gtvcccrcfhuh</a>

qnsmprqnsmpr2013/02/19 02:06IDXBp6 <a href="http://tdiutlvrhsqr.com/">tdiutlvrhsqr</a>

ldlhvtldlhvt2013/02/21 14:11jqHKkH <a href="http://ihumrmpkwbiu.com/">ihumrmpkwbiu</a>

rexpxqrexpxq2013/02/21 18:34FMdzWL , [url=http://fvgkmkrgfoyd.com/]fvgkmkrgfoyd[/url], [link=http://dfkwhpnoefiw.com/]dfkwhpnoefiw[/link], http://elpxctkydvad.com/

2009-11-06

EggCartons

| 06:31

SRM 452 Div2は250,500を解けて、674.40点。Division rankは76位で、比較的よかった。1000の問題は30分以上あまっていたけど、解法が思いつかなかったので早々に諦めた。Ratingは 1120 から 1187 に上がった。Challenge phaseに真面目に参加して、Challengeを一回でも成功させていればDiv1に昇格できていたかもしれない。


問題文, SRM 452

卵が6個入ったパックと8個が入ったパックがあるとき、指定された数の卵を買うには最低何パック買えばいいのか。

問題を読んだときにナップサック問題みたいだなと思ったので、DPで解いた。他の方の回答を見ると 8i+6j=n を満たす i,j を調べている方が多かった。

238.04/250

class EggCartons {
public:
    int minCartons(int n) {
        if (n < 6) return -1;
        vector<int> v(n+1, -1);
        v[0] = 0;
        for (int w = 0; w <= n; w++) {
            if (w >= 8 && v[w-8] != -1) v[w] = 1 + v[w-8];
            else if (w >= 6 && v[w-6] != -1) v[w] = 1 + v[w-6];
        }
        return v[n];
    }
};

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

PizzaDelivery

| 07:29

問題文, SRM 451

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

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

300.00/1000 (4-failed)

][piza[i].second];

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

Stairs

| 13:15

問題文, SRM 177

与えられた条件の階段は何種類作れるか。問題の意味を理解するのに時間がかかった。内側のループは必要ない、ということに他の方のコードを見て気がついた。

177.45/250

class Stairs {
public:
    int designs(int maxHeight, int minWidth, int totalHeight, int totalWidth) {
        int designs = 0;
        for (int h = maxHeight; h >= 1; h--) {
            if (totalHeight%h == 0) {
                int parts = totalHeight/h - 1;
                if (parts == 0) continue;
                for (int w = minWidth; ; w++) {
                    int width = w * parts;
                    if (width > totalWidth) break;
                    if (width == totalWidth) 
                        designs++;
                }

            }
        }
        return designs;
    }
};

MitchellMitchell2011/07/11 00:05Big help, big help. And superlative news of crouse.

veiutvcwcveiutvcwc2011/07/11 02:29TlCswI <a href="http://vjnggvexbwuu.com/">vjnggvexbwuu</a>

zoksriviopzoksriviop2011/07/11 21:51epdS5v , [url=http://gqqjyfaqwssc.com/]gqqjyfaqwssc[/url], [link=http://mbceaafjqxom.com/]mbceaafjqxom[/link], http://qzkaecclvamc.com/

ntetzpntetzp2011/07/13 18:23bYD1yS <a href="http://bgyraruehckt.com/">bgyraruehckt</a>

mxixglmxixgl2011/07/14 00:35GtzmkZ , [url=http://mxgzmwjlggpm.com/]mxgzmwjlggpm[/url], [link=http://xraideylozrg.com/]xraideylozrg[/link], http://jcutzvphyqwn.com/

2009-08-31

StampPads

| 13:51

問題文, SRM 158

欲しい色を全部そろえるには、何種類のスタンプパッドを買えば良いのか。Brute forceで解ける問題だったが、DPで解こうとした。2回タイムアウトで落とされたが、始めにmaskを作る方法に変えたら通った。

150.00/500 (2 failed)

class StampPads {
public:
    int bestCombo(vector <string> pads, vector <string> wishlist) {
        numPads = pads.size();
        pds = vector<vector<string> >(numPads, vector<string>(5));
        for (int i = 0; i < numPads; i++) {
            istringstream iss(pads[i]);
            for (int j = 0; iss >> pds[i][j]; j++) ;
        }
        bitset<32> got;
        numWishes = wishlist.size();
        wishL = wishlist;
        mask = vector<bitset<32> >(numPads);
        for (int i = 0; i < numPads; i++)
            for (int j = 0; j < numWishes; j++)
                mask[i][j] = find(pds[i].begin(),pds[i].end(),wishL[j]) != pds[i].end();
        return go(0, 0, got);
    }
    int numPads;
    vector<vector<string> > pds;
    vector<string> wishL;
    vector<bitset<32> > mask;
    int numWishes;
    int go(const int bought, const int idx, const bitset<32>& got) {
        if (got.count() >= numWishes) return bought;
        if (idx >= numPads) return -1;
        bitset<32> next(got | mask[idx]);
        if (next != got) {
            int retBuy = go(bought+1, idx+1, next);
            int retNot = go(bought, idx+1, got);
            if (retBuy == -1 && retNot == -1) return -1;
            else if (retBuy == -1) return retNot;
            else if (retNot == -1) return retBuy;
            else return min(retBuy, retNot);
        } else {
            return go(bought, idx+1, got);
        }
    }
};

2009-08-29

IsHomomorphism

| 16:05

問題文, SRM 161

同じ答えを返すかどうかを調べる。問題の意味がわかりにくいが、わかれば簡単な問題。

196.13/300

class IsHomomorphism {
public:
    vector <string> numBad(vector <string> source, vector <string> target, vector <int> mapping) {
        vector <string> result;
        for (int i = 0; i < source.size(); i++) {
            for (int j = 0; j < source[0].size(); j++) {
                if (mapping[source[i][j]-'0'] != target[mapping[i]][mapping[j]]-'0') {
                    ostringstream oss;
                    oss << "(" << i << "," << j << ")";
                    result.push_back(oss.str());
                }
            }
        }
        return result;
    }
};