Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-25

QuiningTopCoder

| 14:09

問題文, SRM 152

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

150.0/500 (1 failed)

class QuiningTopCoder {
public:
    string testCode(string source) {
        string output;
        const static int TIME_LIMIT = 80000;
        stack<int> stk;
        for (int i = 0; i < TIME_LIMIT; i++) stk.push(0);
        int IP=0, D=1, N=source.size();
        int cycle = 0;
        while (source[IP] != '@' && cycle < TIME_LIMIT) {
            const char c = source[IP];
            int DD = D;
            if (isdigit(c)) {
                stk.push(c-'0');
            } else if (c == '$') {
                stk.pop();
            } else if (c == ':') {
                int X = stk.top(); stk.pop();
                stk.push(X); stk.push(X);
            } else if (c == 'W') {
                int A = stk.top(); stk.pop();
                int B = stk.top(); stk.pop();
                stk.push(A); stk.push(B);
            } else if (c == ',') {
                int X = stk.top(); stk.pop();
                output += source[abs(X)%N];
                if (output == source ||
                        output != source.substr(0,output.length())) 
                    break;
            } else if (c == '+') {
                int A = stk.top(); stk.pop(); 
                int B = stk.top(); stk.pop();
                stk.push(A+B);
                if (abs(stk.top()) > 1000000000) break;
            } else if (c == '-') {
                int A = stk.top(); stk.pop(); 
                int B = stk.top(); stk.pop();
                stk.push(A-B);
                if (abs(stk.top()) > 1000000000) break;
            } else if (c == '#') {
                DD *= 2;
            } else if (c == 'R') {
                DD *= -1; D *= -1;
            } else if (c == 'S') {
                int X = stk.top(); stk.pop();
                if (X > 0) stk.push(1);
                else stk.push(-1);
            } else if (c == '_') {
                int X = stk.top(); stk.pop();
                D = DD = X % N;
            } else if (c == 'J') {
                int X = stk.top(); stk.pop();
                IP = abs(X) % N;
            } 
            if (c != 'J')
                IP = (3*N+IP+DD) % N;
            cycle++;
        }
      
        ostringstream res;
        if (source[IP] == '@') {
            res << "BADEND " << cycle;
        } else if (cycle == TIME_LIMIT) {
            res << "TIMEOUT";
        } else if (abs(stk.top()) > 1e+9) {
            res << "OVERFLOW " << cycle;
        } else if (source != output) {
            res << "MISMATCH " << cycle;
        } else {
            res << "QUINES " << cycle;
        }
        return res.str();
    }
};

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