TopCoderの問題を解く

FryingHamburgers

SRM 159, Div1, Div1 Level-1, Math, cheated, 30% | 11:29

問題文, SRM 159

すべてのハンバーガーを焼くのにかかる時間。解けなくて、さんざん悩んで、Editorialを見て、数学の問題だと気づいた。

75.0/250

class FryingHamburgers {
public:
    int howLong(int panSize, int hamburgers) {
        if (hamburgers == 0) return 0;
        if (hamburgers <= panSize) return 10;
        return 5*(int)ceil(2.0*hamburgers/panSize);
    }
};

ThePriceIsRight

SRM 159, Div2, Div2 Level-3, Div1, Div1 Level-2, Dynamic Programming | 08:46

問題文

Longest increasing sub sequence を求める問題。再帰を使って解く方法は思いついたが、それでは計算量が問題になるとわかり、結局やはりEditorialを見た。dynamic programming による方法で解ける。

class ThePriceIsRight {
public:
    vector <int> howManyReveals(vector <int> prices) {
        const int size = prices.size();
        vector<int> S(size,0), L(size,0);
        vector <int> result(2,0);
        for (int i = 0; i < size; i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                if (prices[j] < prices[i]) 
                    tmp = max(tmp, S[j]);
            }
            for (int j = 0; j < i; j++) {
                if (S[j] == tmp && prices[j] < prices[i])
                    L[i] += L[j];
            }
            if (L[i] == 0) L[i] = 1;
            S[i] = 1 + tmp;
        }
        result[0] = *max_element(S.begin(), S.end());
        for (int i = 0; i < size; i++) {
            if (S[i] == result[0])
                result[1] += L[i];
        }
        return result;
    }
};

Sets

SRM 159, Div2, Div2 Level-2, Math | 18:25

問題文

集合演算。

class Sets {
public:
    vector <int> operate(vector <int> A, vector <int> B, string operation) {
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        if (operation == "UNION") {
            return union_set(A, B);
        } else if (operation == "INTERSECTION") {
            return intersection(A, B);
        } else if (operation == "SYMMETRIC DIFFERENCE") {
            return symmetric_difference(A, B);
        } else {
            return vector<int>();
        }
    }
private:
    vector<int> union_set(const vector<int>& A, const vector<int>& B) {
        set<int> tmp_union;
        for (int i = 0; i < A.size(); i++) tmp_union.insert(A[i]);
        for (int i = 0; i < B.size(); i++) tmp_union.insert(B[i]);
        vector<int> ret;
        for (set<int>::const_iterator itr = tmp_union.begin();
                itr != tmp_union.end(); itr++)
            ret.push_back(*itr);
        return ret;            
    }
    vector<int> intersection(const vector<int>& A, const vector<int>& B) {
        int i=0, j=0;
        vector<int> ret;
        while (i<A.size() && j<B.size()) {
            if (A[i] == B[j]) {
                ret.push_back(A[i]);
                i++; j++;
            } else if (A[i] < B[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ret;
    }
    vector<int> symmetric_difference(const vector<int>& A, const vector<int>& B) {
        vector<int> uni = union_set(A, B);
        vector<int> inter = intersection(A, B);
        vector<int> ret;
        for (int i = 0; i < uni.size(); i++) {
            if (find(inter.begin(),inter.end(),uni[i]) == inter.end())
                ret.push_back(uni[i]);
        }
        return ret;
    }
};

StreetParking

SRM 159, Div2, Div2 Level-1, Simple Search, Iteration, String Manipulation | 18:25

問題文

道に駐車できるかどうか。

class StreetParking {
public:
    int freeParks(string street) {
        const int len = street.length();
        int total = 0;
        for (int i = 0; i < len; i++) {
            if (street[i] != '-') continue;
            if (i+2 < len && street[i+2]=='B') continue;
            if (i+1 < len && 
                (street[i+1]=='B'||street[i+1]=='S')) continue;
            if (i-1 >= 0 && street[i-1]=='S') continue;
            total++;
        }
        return total;
    }
};