Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2011-04-17

SRM503 Div1

19:06

レーティングが1501なので、黄色を維持するためには負けられない回。

o-- 157.1pts / 438th。

レーティング1501→1503。

250 ToastXToast

250にしては面倒そうな問題だなぁ、と思いつつ紙に書いて考える。書いてみると意外ときれいに分かれるっぽい?

ということで生焼け→焦げの順にかたまりを取っていくコードを書く。最後のケースが通らない。あ、これじゃ最小にならないじゃん。

最小にするには、一番最初の生焼けに全部の焦げを対応させればいいから……あれ、これ答えは高々2じゃね……。

-1のパターンを適当に場合分けしてSubmit。時間かかりすぎ……。

struct ToastXToast {
    int bake(vector <int> undertoasted, vector <int> overtoasted) {
        sort(undertoasted.begin(), undertoasted.end());
        sort(overtoasted.begin(), overtoasted.end());
        if(overtoasted[0] < undertoasted[0]) return -1;
        if(overtoasted.back() < undertoasted.back()) return -1;
        for(int i = 0; i < overtoasted.size(); ++i)
            for(int j = 0; j < undertoasted.size(); ++j)
                if(overtoasted[i] < undertoasted[j]) return 2;
        return 1;
    }
};

500 KingdomXCitiesandVillages

いいかげん慣れたい期待値の問題。

サンプルが弱いのでちょっと考えづらい。どうせ線形性なんだからどこで使えるか……と見ていくと、一つのVillageについて繋ぎ得る道というのは、一番近いCityとの間か、これよりも近いVillageとの間になる。そして、Villageと繋ぐときは自分より前にそのVillageが選ばれている必要がある。

それぞれのVillageは完全に等確率で選ばれるので、あとは計算するだけ……。のはずだけど、Cityより近いVillageに繋ぐ確率が1/2,1/4,1/8……となっていくと勘違いして間に合わず。アルゴリズム分かったのに数学できなくて実装できないのは悔しい……。

 |