Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

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

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

caliguecaligue 2010/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)を増やす処理を実行させてます。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/caligue/20091106