Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-25

QuiningTopCoder

| 14:09

問題文, SRM 152

自分自身のソースを出力するプログラムかどうかを確認。

150.0/500 (1 failed)

t

2009-07-05

ProblemWriting

| 15:12

問題文

497.42 -> 967.77 / 1000

以下の状態遷移図を基にプログラムすればいい。

f:id:caligue:20090720171507p:image

enum STATES { S0, S1, S2, S3 };

class ProblemWriting {
public:
    string myCheckData(string dotForm) {
        const int len = dotForm.length();
        if (len < 1 || 25 < len) {
            return "dotForm must contain between 1 and 25 characters, inclusive.";
        }
        vector<char> ops;
        ops.push_back('+'); ops.push_back('-');
        ops.push_back('*'); ops.push_back('/');
        int state = S0;
        for (int i = 0; i < len; i++) {
            const char c = dotForm[i];
            bool isError = false;
            switch (state) {
            case S0:
                if (isdigit(c)) 
                    state = S1;
                else 
                    isError = true;
                break;
            case S1:
            case S2:
                if (c == '.') 
                    state = S2;
                else if (find(ops.begin(),ops.end(),c) != ops.end()) 
                    state = S3;
                else 
                    isError = true;
                break;
            case S3:
                if (c == '.') 
                    state = S3;
                else if (isdigit(c)) 
                    state = S1;
                else 
                    isError = true;
                break;
            }
            if (isError) {
                ostringstream oss;
                oss << "dotForm is not in dot notation, check character "
                    << i << ".";
                return oss.str();
            }
        }
        if (state != S1) {
            ostringstream oss;
            oss << "dotForm is not in dot notation, check character "
                << len << ".";
            return oss.str();
        }
        return "";
    }
};

LeaguePicks

| 19:47

問題文

436.29 -> 498.91 / 500

position-th と (2*friends+position+1)-th にあたる pick を取る。簡単な問題。問題文の Examples にヒントが書かれている。

class LeaguePicks {
public:
    vector <int> returnPicks(int position, int friends, int picks) {
        vector <int> result;
        int p = 0;
        while (true) {
            int next = p + position;
            if (next <= picks) result.push_back(next);
            else break;
            next = p + 2*friends - position + 1;
            if (next <= picks) result.push_back(next);
            else break;
            p += 2 * friends;
        }
        return result;
    }
};

FixedPointTheorem

| 19:46

問題文

237.01 -> 248.06 / 250

問題文の通りに、200,001から201,000回目のFの値の範囲(higest value - lowest value)を求めればいい。

class FixedPointTheorem {
public:
    double cycleRange(double R) {
        double X = .25;
        for (int i = 0; i < 200000; i++)
            X = F(R, X);
        vector<double> values(1000);
        for (int i = 0; i < 1000; i++) {
            X = F(R, X);
            values[i] = X;
        }
        return *max_element(values.begin(), values.end())
                - *min_element(values.begin(), values.end());
    }
private:
    double F(const double R, const double X) {
        return R * X * (1-X);
    }
};