Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-22

Fifteen

| 07:35

問題文, SRM 172

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

言った数の内、3つの数の合計が15になったら勝ちのゲームにおいて、挑戦者(patron)が勝てるかどうか。TutorialにTick-Tack-Toeの変装だと書かれていたので、どのように解くか考えたが、少し強引な方法しか考えつかなかった。

204.31/500

class Fifteen {
public:
    string outcome(vector <int> moves) {
        for (int n = 1; n <= 9; n++) {
            if (find(moves.begin(),moves.end(),n) == moves.end()) {
                vector<int> newMoves(moves);
                newMoves.push_back(n);
                if (isWin(newMoves, true)) {
                    char res[10];
                    sprintf(res, "WIN %d", n);
                    return string(res);
                }
            }
        }
        return "LOSE";
    }
private:
    bool isWin(const vector<int>& moves, const bool isPatron) {
        for (int i = isPatron? 1:0; i < moves.size(); i += 2)
            for (int j = i+2; j < moves.size(); j += 2)
                for (int k = j+2; k < moves.size(); k += 2)
                    if (moves[i]+moves[j]+moves[k] == 15)
                        return true;
        for (int n = 1; n <= 9; n++)
            if (find(moves.begin(),moves.end(),n) == moves.end()) {
                vector<int> newMoves(moves);
                newMoves.push_back(n);
                if (isWin(newMoves, !isPatron))
                    return false;
            }
        return true;
    }
};

2009-08-30

BadClock

| 15:23

問題文, SRM 172

何時間後に2つの時計が同時刻を指すか。

class BadClock {
public:
    double nextAgreement(string trueTime, string skewTime, int hourlyGain) {
        int X = getTime(trueTime);
        int Y = getTime(skewTime);
        if (hourlyGain < 0) {
            hourlyGain = -hourlyGain;
            swap(X, Y);
        }
        while (X < Y) X += 12*60*60;
        return (double) (X - Y) / hourlyGain;
    }
private:
    int getTime(const string& time) {
        int hh, mm, ss;
        sscanf(time.c_str(), "%d:%d:%d", &hh, &mm, &ss);
        return (hh*60 + mm)*60 + ss;
    }
};

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;
    }
};

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/