Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2011-01-23

SRM494 Div1

20:03

深夜SRM

x-- 0.0pts/536th 1522→1415。青色復帰!

250早解きゲーかと思ったら250も落ちて悲惨なことになった。

250 Painting

セルを与えられたとおりに黒く塗りたい。塗るときは正方形でいっぺんに黒を塗る。このとき使える正方形の最大サイズを求めよ。

あれ?これ最小幅求めて終わりじゃね?

→Challenge Succeeded。互いに干渉しないように白を置いて

BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBWBBBB
BBBWBBBBBB
BBBBBBWBBB
BBBBWBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB

こんな感じにすると、最小幅3だけど真ん中のエリアは3x3で塗れないらしい。

想定解は正方形の大きさを決めて試し塗り。左上座標を決めるのでN**2、塗りつぶしでN**2、ブラシの大きさでNのO(N**5)。Nは50以下なので、だいたい3億ループくらい。あんまり処理が複雑でなければ、TopCoderでは普通に通るレベル。

Practiceで通したコード。

struct Painting {
    int largestBrush(vector <string> picture) {
        int R = picture.size();
        int C = picture[0].size();

        int all = 0;
        for(int r = 0; r < R; ++r)
            for(int c = 0; c < C; ++c)
                if(picture[r][c] == 'B') ++all;

        int ans = 1;
        for(ans = 2; ans <= min(R, C); ++ans) {
            vector<vector<int> > field(R, vector<int>(C, 0));
            int sum = 0;
            for(int r = 0; r <= R-ans; ++r) {
                for(int c = 0; c <= C-ans; ++c) {
                    int cnt = 0;
                    for(int dr = 0; dr < ans; ++dr) {
                        for(int dc = 0; dc < ans; ++dc) {
                            if(picture[r+dr][c+dc] == 'W') goto next;
                            else if(field[r+dr][c+dc] == 0) ++cnt;
                        }
                    }
                    for(int dr = 0; dr < ans; ++dr)
                        for(int dc = 0; dc < ans; ++dc)
                            field[r+dr][c+dc] = 1;
                    sum += cnt;
next:
                    ;
                }
            }
            if(sum != all) break;
        }
        return ans-1;
    }
};

500 AlternatingLane

木を一列に植えて、それぞれの木iは最低low[i]、最高high[i]まで成長する。成長し終わったとき、どの木iの高さhiについても、hi-1 > hi < hi+1かhi-1 < hi > hi+1が成立するように木を取り除く。この後、美しさを∑|hi-1-hi|で求めるとき、美しさの期待値を求めよ。ただし、木を取り除くときは、美しさが最大になるよう取り除く。

苦手な期待値問題。確率と言えば対称性・・・と思って考えても、どこで対称性が効くのか見えない。とりあえずDP式立てようとしても無理ぽい。ということで時間切れ・・・。

解き方。まず、一つのパターンに注目したとき、木を取り除いても美しさは変わらない。なぜなら取り除く必要があるのはhi-1 > hi > hi+1のように単調になっている箇所の中間の木だから、美しさは|hi-1-hi|+|hi-hi+1| = |hi-1-hi+1|。また、中間ではなく終点の木i+1を取り除くと、次の木i+2ではhi < hi+2が成立していないといけないが、それなら木i+1を残しておいたほうが美しさが上がる。よって、木を取り除くことは考えず、隣同士の木の美しさだけで期待値を求めれば良い。

次に、期待値の求め方。関係があるのは2本の木だけなので、(high[i-1]-low[i-1]+1)*(high[i]-low[i]+1)通りのパターンがあるが、1 ≤ low[i],high[i] ≤ 100000なのでまともに回すとTLE。そこで対称性を使う。まずhiを一つ決めると、ひとつ前の木と合わせて得られる美しさは{high[i-1]-hi, high[i-1]-1-hi, ・・・, 1, 1, 2, ・・・, hi-low[i-1]-1, hi-low[i-1]}が一つずつ出てくる(low[i-1] < hi < high[i-1]の場合)。よって、等差数列の和の公式で合計が求められる。hi ≤ low[i-1], hi ≥ high[i-1]の場合も同様。

以下、Practiceで通したコード。

struct AlternatingLane {
    double expectedBeauty(vector <int> low, vector <int> high) {
        double ans = 0;
        int N = low.size();
        for(int i = 1; i < N; ++i) {
            double pat = (high[i-1]-low[i-1]+1.0) * (high[i]-low[i]+1.0);
            for(int h = low[i]; h <= high[i]; ++h) {
                if(h > high[i-1] || h < low[i-1]) {
                    ans += abs(low[i-1]-h + high[i-1]-h) * (high[i-1]-low[i-1]+1.0) / 2.0 / pat;
                }
                else {
                    ans += ((1.0 + high[i-1]-h) * (high[i-1]-h) / 2.0 + (1.0 + h-low[i-1]) * (h-low[i-1]) / 2.0) / pat;
                }
            }
        }
        return ans;
    }
};
 |