SRM549 Div.1

結果

o--(+0/-0) 224.08pts 60th
1782->1886(+104)

Highest更新して初の1800台到達！

600 Magical Hats

Medも解けるようになっていかないといけないのでMed Openしてみた。
英文が読みづらい…要はコインが入っている場所を絞り込んでいくみたいだけど
コインが入ってた場合と入っていない場合で候補位置が変わる。

…全然わからん…
30分ちょいぐらい考えて諦めた

250 Pointy Wizard Hats

こっちは割と読みやすかった。
帽子がTop,Bottomの2種類あって、重ねたときに黒魔道士の帽子っぽくなればok。

• TopとBottomの頂点が重なってはいけない
• Topが全て覆いかぶさってはいけない

このとき、作れる帽子の最大個数を求める。

すぐに二部グラフの最大マッチングというのは解るので、
とりあえず蟻本開いて写経しつつ、どういう場合にエッジを張ればいいか考える。

明らかに上の帽子の半径は下の帽子の半径未満でないといけない。
それ以外の場合は帽子の傾きを見て、上の方が大きければ良さそう。
(この辺りはいろんなパターンの絵を書いた)
傾きの誤差が怖いなーと思ったけどdoubleで書く、sample通る、submit。

->passed system test.
前回のにぶたん->条件考えると同じような流れだった。
以下ソース

    int V;
    vector<int> G[MAX_V];
    int match[MAX_V];
    bool used[MAX_V];

    void add_edge(int u, int v){
        G[u].PB(v);
        G[v].PB(u);
    }

    bool dfs(int v){
        used[v] = true;
        for(int i=0;i<(int)G[v].size();i++){
            int u = G[v][i], w = match[u];
            if(w < 0 || (!used[w] && dfs(w))){
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
        return false;
    }

    int max_matching(void){
        int res = 0;
        memset(match, -1, sizeof(match));

        for(int v=0;v<V;v++){
            if(match[v] < 0){
                memset(used, 0, sizeof(used));
                if(dfs(v)) res++;
            }
        }
        return res;
    }

    int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius) {
        int n = topHeight.size();
        int m = bottomHeight.size();

        V = n + m;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(topRadius[i] < bottomRadius[j] && 
                   ((double)topHeight[i]/topRadius[i] - (double)bottomHeight[j]/bottomRadius[j] > EPS)){
                    add_edge(i,n+j);
                }
            }
        }
        return max_matching();
    }

感想

あきばさんがターゲットになった。本当にすごい。
自分も3年以内ぐらいに赤くなれるといいなぁ〜。
(Easyだけでレートはどこまで上がるのか…)