Topcoder SRM 503 Div2

練習。

250 ToastXRaspberry

まぁ割りきれたらそれでいいけど、割りきれなかった場合にはもう一回余りをやる。

class ToastXRaspberry{
public:
    int apply(int upper_limit, int layer_count){
        if(layer_count % upper_limit == 0){
            return layer_count / upper_limit;
        }else{
            return layer_count / upper_limit + 1;
        }
    }
};

500 ToastXToast

最初にまっくろこげがあったり、最後に生焼けがのこってたらムリ。 それ以外の場合、最後の生焼けと、もう一個生焼けを選べばいいことがわかる。 ただし、コーナーケースに注意。

#define all(X) (X).begin(),(X).end()
class ToastXToast{
public:
    int bake(vector <int> undertoasted, vector <int> overtoasted){
        int U = undertoasted.size();
        int O = overtoasted.size();
        sort(all(undertoasted));
        sort(all(overtoasted));
        if(overtoasted[0] < undertoasted[0] or overtoasted[O-1] < undertoasted[U-1]) return -1;
        int ret = 0;
        vector<int> merged(U+O);
        merge(all(undertoasted),all(overtoasted),merged.begin());
        for(int i=1;i<U+O;i++){
            if(find(all(undertoasted),merged[i-1]) != undertoasted.end()
               and find(all(overtoasted),merged[i]) != overtoasted.end()){
                   ret++;
            }
        }
        if(ret == 1) return ret;
        else return 2;
    }
};

900 KingdomXCitiesandVillagesAnother

最小全域木をやるだけ。

class KingdomXCitiesandVillagesAnother{
public:
    double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY){
        int C = cityX.size();
        int V = villageX.size();
        int N = C+V;
        vector<vector<double> > dist(N,vector<double>(N));
        vector<point> p(C+V);
        for(int i=0;i<C;i++){
            p[i] = point(cityY[i],cityX[i]);
        }
        for(int i=C;i<N;i++){
            p[i] = point(villageY[i-C],villageX[i-C]);
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(i < C and j < C){
                    dist[i][j] = 0;
                }else{
                    dist[i][j] = abs(p[i]-p[j]);
                }
            }
        }

        double ret = 0;
        vector<char> used(N,false);
        priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > >que;
        que.push(make_pair(0,0));
        while(not que.empty()){
            double cost = que.top().first;
            int where = que.top().second;
            que.pop();
            if(used[where]) continue;
            used[where] = true;
            ret += cost;
            for(int i=0;i<N;i++){
                que.push(make_pair(dist[where][i],i));
            }
        }
        return ret;
    }
};