Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-19

SkipRope

| 17:48

問題文, SRM 172

身長が最も近い2人を選ぶ。コードは全要素をわざわざソートするという無駄な処理を行っている。41.67%と結構Sucess Rateが低い。

228.19/250

bool compDiff(const pair<int,int>& a, const pair<int,int>& b) {
    if (a.second < b.second) {
        return true;
    } else if (a.second > b.second) {
        return false;
    } else {
        return a.first > b.first;
    }
}

class SkipRope {
public:
    vector <int> partners(vector <int> candidates, int height) {
        vector<pair<int,int> > diff(candidates.size());
        for (int i = 0; i < candidates.size(); i++)
            diff[i] = make_pair(candidates[i], abs(candidates[i]-height));
        sort(diff.begin(), diff.end(), compDiff);
        vector <int> result;
        for (int i = 0; i < 2; i++) result.push_back(diff[i].first);
        if (result[0] > result[1]) swap(result[0], result[1]);
        return result;
    }
};

| 14:30

問題文, http://www.topcoder.com/stat?c=round_overview&rd=4550:titel=SRM 149]

Dictionaryに含まれる単語だけで、messageを作れるかどうか。DPで解ける問題だが、見落としが発生しやすい問題。4回もシステムテストで落とされた。

150.0/500

class MessageMess {
    public:
        string restore(vector <string> dictionary, string message) {
            const int len = message.size();
            vector<string> memo(len, "");
            vector<bool> isAmbiguous(len, false);
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < dictionary.size(); j++) {
                    const int wlen = dictionary[j].length();
                    if (i+1 < wlen) continue;
                    if (i-wlen >= 0 && memo[i-wlen] == "") continue;
                    if (message.substr(i-wlen+1,wlen) != dictionary[j]) continue;
                    if (memo[i] != "") isAmbiguous[i] = true;
                    if (i-wlen >= 0) {
                        if (toNospace(memo[i-wlen]) != message.substr(0,i-wlen+1)) continue;
                        if (isAmbiguous[i-wlen]) isAmbiguous[i] = true;
                        memo[i] = memo[i-wlen] + " " + dictionary[j];
                    } else {
                        memo[i] = dictionary[j];
                    }
                }
            }
            if (memo[len-1] == "") return "IMPOSSIBLE!";
            else if (isAmbiguous[len-1]) return "AMBIGUOUS!";
            else return memo[len-1];
        }
    private:
        string toNospace(const string& s) {
            string nospace;
            const int slen = s.length();
            int idx=0, pre=idx;
            while ((idx = s.find(" ", pre)) != string::npos) {
                nospace += s.substr(pre, idx-pre);
                pre = idx+1;
            }
            nospace += s.substr(pre, slen-pre);
            return nospace;
        }
};

Archimedes

| 11:09

問題文, SRM 151

円周率の近似値を求める。どうすれば求められるのかは、すぐに分かった。

230.08/250

class Archimedes {
    public:
        double approximatePi(int numSides) {
            return numSides * sin(M_PI/numSides);
        }
};

RenaRena2011/07/22 11:40Articles like this really grease the shftas of knowledge.

mtosqkksxfnmtosqkksxfn2011/07/22 18:19nGge95 <a href="http://htbsbsjhateo.com/">htbsbsjhateo</a>

vouvotvouvot2011/07/24 22:10AbhEFB <a href="http://udtjnaqmvoon.com/">udtjnaqmvoon</a>

lraetvllraetvl2011/07/25 02:03Ueilew , [url=http://ofkchvqjbqph.com/]ofkchvqjbqph[/url], [link=http://mhzhqovckhxx.com/]mhzhqovckhxx[/link], http://kgxfqnawhoqk.com/