Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2010-01-30

TeXLeX

| 22:45

問題文, SRM 178

'^' のみが特別な入力である入力文字列のASCII値を返せ、という問題。この '^' をどのように処理するかが問題の肝。

この問題を解くには適宜文字列を変換ルールにしたがって1文字目から変換していく必要がある。基本的には変換ルールのとおりに機能を実装すればいい。注意する点としてはルール1を適用すると、値がchar型ではオーバーフローする場合があるので、それ対応する必要がある(僕は気づけなかったために、システムテストで落とされた。

238.78/600 (1 failed)

class TeXLeX {
public:
    vector <int> getTokens(string input) {
        vector <int> result;
        const int len = input.length();
        for (int i = 0; i < len; i++) {
            if (input[i] == '^') {
                if (i >= len-2) {
                    result.push_back('^');
                } else if (input[i+1] != '^') {
                    result.push_back('^');
                } else if (i < len-3 && isHex(input[i+2]) && isHex(input[i+3])) {
                    unsigned int c;
                    sscanf(input.substr(i+2,2).c_str(), "%x", &c);
                    if (c >= 128) {
                        result.push_back(c);
                        i += 3;
                    } else {
                        input[i+3] = (char) c;
                        i += 2;
                    }
                } else if (input[i+2] > 63) {
                    input[i+2] -= 64;
                    i += 1;
                } else {
                    input[i+2] += 64;
                    i += 1;
                }
            } else {
                result.push_back(input[i]);
            }
        }
        return result;
    }
private:
    bool isHex(const char c) {
        return ('0'<=c && c<='9') || ('a'<=c && c<='f');
    }
};

CamiCami2011/08/31 01:54Hey hey hey, take a gaednr at what' you've done

ifhwgxmyifhwgxmy2011/09/01 01:26IyxF2c <a href="http://zzvvdkadzyzw.com/">zzvvdkadzyzw</a>

vsyaesivsyaesi2011/09/03 20:20bbeGDx <a href="http://xqcimzgfyxjv.com/">xqcimzgfyxjv</a>

2010-01-29

SimpleCalculator

| 19:13

久しぶりに解いた。最近解いてなかったのは英語力の強化を重視していて、英語力が充分ついてから解くのを再開しようかと思っていたから。しかし、思ったよりも時間がかかりそうで(頑張っても1年はかかる)、問題を解く感覚が鈍りそうなので、1日1時間程度をアルゴリズム系の問題を解く時間かそのための勉強に当てようと思います。1時間だと難しめの問題を解くのは時間的に厳しいので、解く問題はDiv2のLevel-1,2とDiv1のLevel-1の問題を中心にします。

問題文, SRM 178

四則演算だけのシンプルな計算機。今度からはしっかり解説を付けたいなと思ったのに、何も語ることがない。この問題はどのように入力値を文字列から得るかだと思うが、それも istringstream か sscanf を使えば実現できるので、やはり語ることがない。

248.39/250

class SimpleCalculator {
public:
    int calculate(string input) {
        int a, b;
        char c;
        istringstream(input) >> a >> c >> b;
        if (c == '+') return a + b;
        else if (c == '-') return a - b;
        else if (c == '*') return a * b;
        else return a / b;
    }
};

MaheshMahesh2012/11/14 15:48Furrealz? That's marovelusly good to know.

mrmqezkqxwmrmqezkqxw2012/11/15 11:52s6bK06 <a href="http://gcchvukbnzox.com/">gcchvukbnzox</a>

spsrxxspsrxx2012/11/16 10:14TvaJTu , [url=http://eciyaqdchfxo.com/]eciyaqdchfxo[/url], [link=http://ttwirdzyever.com/]ttwirdzyever[/link], http://mnxmkjngbida.com/

lewoklxfgxlewoklxfgx2012/11/17 00:38yuecsC <a href="http://lqhnazvgbvem.com/">lqhnazvgbvem</a>

gflffsgflffs2012/11/17 10:45N1Z2Z1 , [url=http://vngcyqvvvmgl.com/]vngcyqvvvmgl[/url], [link=http://dkarqzmcxylp.com/]dkarqzmcxylp[/link], http://zzwhaounqels.com/

2009-10-26

OldestOne

| 05:33

問題文, SRM 177

最年長の人の名前を答える。

380.52/500

class OldestOne {
public:
    string oldest(vector <string> data) {
        string oldestName;
        int oldestAge = -1;
        for (int i = 0; i < data.size(); i++) {
            for (int j = 1; j < data[i].length(); j++) {
                if (isdigit(data[i][j])) {
                    int age;
                    sscanf(data[i].substr(j).c_str(), "%d", &age);
                    if (oldestAge < age) {
                        oldestAge = age;
                        oldestName = data[i].substr(0, j);
                    }
                    break;
                }
            }
        }
        string result;
        for (int i = 0; i < oldestName.length(); i++)
            if (isalpha(oldestName[i])) {
                result = oldestName.substr(i);
                break;
            }
        for (int i = result.length()-1; i >= 0; i--)
            if (isalpha(result[i])) {
                result = result.substr(0, i+1);
                break;
            }
        return result;
    }
};

2009-10-21

BoredPhilosophers

| 12:48

問題文, SRM 451

教室にN人の哲学者がいます。彼らはとても退屈なので、本から抜粋した適当なテキスト使ってゲームを始めました。1番目の哲学者はテキスト中の語の種類数を言います。2番目の哲学者は2個の連続する語からなるセンテンスの種類数を言います。同様にi番目の哲学者はi個の連続する語からなるセンテンスの種類数を言います。このゲームはN人全ての哲学者が発言した後に終了します。

テキストとして vector<string> が与えられます。このvectorの要素を結合(concatenate)し、テキストを完成させ、N個の要素からなる vector<int> を返しなさい(i番目の要素にはi人目の哲学者が言った数を入れる)。テキスト中の語はシングルスペースで区切られています。

問題文中のconcatenateの意味を理解するのに時間がかかった。意味が理解できれば実装は難しくない。

265.46/500

class BoredPhilosophers {
public:
    vector <int> simulate(vector <string> text, int N) {
        string T;
        for (int i = 0; i < text.size(); i++)
            T += text[i];
        vector<string> words;
        istringstream iss(T);
        string s;
        while (iss >> s) words.push_back(s);
        vector <int> result;
        for (int d = 1; d <= N; d++) {
            set<string> difWords;
            for (int i = 0; i < words.size()-d+1; i++) {
                string t(words[i]);
                for (int j = i+1; j < i+d; j++)
                    t += " " + words[j];
                difWords.insert(t);
            }
            result.push_back(difWords.size());
        }
        return result;
    }
};

ivcbmcaeivcbmcae2011/02/28 07:41NZm68y <a href="http://ilbauxmjluym.com/">ilbauxmjluym</a>, [url=http://xbddmcdppokz.com/]xbddmcdppokz[/url], [link=http://sjwaelhpgvzy.com/]sjwaelhpgvzy[/link], http://uddhrwxfjfig.com/

2009-10-04

MassiveNumbers

| 20:07

SRM 236, 問題文

どっちの数が大きいか。

227.54/250

class MassiveNumbers {
public:
    string getLargest(string numberA, string numberB) {
        double m = getNum(numberA);
        double n = getNum(numberB);
        return (m > n) ? numberA : numberB;
    }
private:
    double getNum(const string& num) {
        double x, y;
        sscanf(num.c_str(), "%lf^%lf", &x, &y);
        return y * log10(x);
    }
};

CindyCindy2011/08/30 03:53This airtlce went ahead and made my day.

mdemxwxbqmdemxwxbq2011/08/30 17:43Zd89Ez <a href="http://fqdhttbozbbl.com/">fqdhttbozbbl</a>

cdffsucdffsu2011/09/01 16:14krcrX4 , [url=http://wlwbmerglolk.com/]wlwbmerglolk[/url], [link=http://ifpjtmfiwmtu.com/]ifpjtmfiwmtu[/link], http://naygcnbbnajf.com/

glfkghywcuglfkghywcu2011/09/04 01:35tQqNlZ , [url=http://gdtojpngtbre.com/]gdtojpngtbre[/url], [link=http://imxqbkfrlcqs.com/]imxqbkfrlcqs[/link], http://skhdkbgwnwib.com/

2009-09-06

BusinessTasks

| 09:12

問題文, SRM 236

Algorithm Tutorials -- How to Find a Solutionから。

円形に並べた仕事をn個飛ばしで選んで処理する。Joseph問題の一種。この問題サイズだったらvectorのeraseを使える。書き終わって気づいた。このプログラムにforループはいらなくて、whileループでいい。

238.23/250

class BusinessTasks {
public:
    string getTask(vector <string> list, int n) {
        int p = 0;
        for (int i = 0; list.size() > 1; i++) {
            p = (p + n-1) % list.size();
            p = list.erase(list.begin()+p) - list.begin();
        }
        return list[0];
    }
};

2009-09-03

NoOrderOfOperations

| 12:44

問題文, SRM 200

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

式を左から右に評価。

243.45/250

class NoOrderOfOperations {
public:
    int evaluate(string expr) {
        int result = expr[0]-'0';
        for (int i = 1; i < expr.length(); i += 2) {
            switch (expr[i]) {
                case '+':
                    result += expr[i+1]-'0';
                    break;
                case '-':
                    result -= expr[i+1]-'0';
                    break;
                case '*':
                    result *= expr[i+1]-'0';
                    break;
            }
        }
        return result;
    }
};

2009-08-29

IsHomomorphism

| 16:05

問題文, SRM 161

同じ答えを返すかどうかを調べる。問題の意味がわかりにくいが、わかれば簡単な問題。

196.13/300

class IsHomomorphism {
public:
    vector <string> numBad(vector <string> source, vector <string> target, vector <int> mapping) {
        vector <string> result;
        for (int i = 0; i < source.size(); i++) {
            for (int j = 0; j < source[0].size(); j++) {
                if (mapping[source[i][j]-'0'] != target[mapping[i]][mapping[j]]-'0') {
                    ostringstream oss;
                    oss << "(" << i << "," << j << ")";
                    result.push_back(oss.str());
                }
            }
        }
        return result;
    }
};

QuipuReader

| 14:05

問題文, SRM 155

特殊な数記法で表わされた数を処理。解くのに時間かかり過ぎ。

191.33/450

class QuipuReader {
public:
    vector <int> readKnots(vector <string> knots) {
        const int sz = knots.size();
        const int len = knots[0].length();
        vector<vector<int> > num(sz), start(sz), last(sz);
        for (int i = 0; i < sz; i++) {
            int j = 0;
            while (j < len) {
                while (j < len && knots[i][j] != 'X') j++;
                if (j == len && knots[i][len-1] != 'X') break;
                start[i].push_back(j);
                j++;
                while (j < len && knots[i][j] == 'X') j++;
                num[i].push_back(j-start[i].back());
                last[i].push_back(j-1);
            }
        }

        vector <int> result(sz,0), idx(sz,0);
        int i = 0;
        while (i < len) {
            int s = INT_MAX, l=INT_MAX;
            for (int j = 0; j < sz; j++) {
                if (idx[j] < start[j].size() && start[j][idx[j]] < s) {
                    s = start[j][idx[j]];
                    l = last[j][idx[j]];
                }
            }
            if (s == INT_MAX) break;
            for (int j = 0; j < sz; j++) {
                result[j] *= 10;
                if (idx[j] < start[j].size() &&
                        ((s<=start[j][idx[j]] && last[j][idx[j]]<=l) ||
                        (start[j][idx[j]]<=s && l<=last[j][idx[j]]))) {
                    result[j] += num[j][idx[j]];
                    idx[j]++;
                } 
            }
            i = l + 1;
        }
        return result;
    }
};

Iditarod

| 10:30

問題文, SRM 160

所要時間の平均を求める。

212.31/250

class Iditarod {
public:
    int avgMinutes(vector <string> times) {
        int total = 0;
        for (int i = 0; i < times.size(); i++)
            total += getTime(times[i]);
        return (int)((double) total / times.size() + 0.5);
    }
private:
    int getTime(string& time) {
        int hh, mm, n;
        char apm;
        sscanf(time.c_str(), "%d:%d %cM, DAY %d", &hh, &mm, &apm, &n);
        if (hh == 12) hh = 0;
        if (apm == 'P') hh += 12;
        return 24*(n-1)*60 + hh*60 + mm - 8*60;
    }
};

2009-07-26

BaseMystery

| 09:14

問題文

n進数を採用したとき、等式を満たすかどうか。見落としが多く、2回システムテストで落とされ、3回目で通った。

class BaseMystery {
public:
    vector <int> getBase(string equation) {
        vector <int> result;
        vector<string> nums(3); 
        nums[0] = string(equation.begin(), 
                find(equation.begin(),equation.end(),'+'));
        nums[1] = string(equation.begin()+nums[0].length()+1, 
            find(equation.begin()+nums[0].length()+1,equation.end(),'='));
        nums[2] = string(equation.begin()+nums[0].length()+nums[1].length()+2,
                equation.end());
        int maxDigit = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < nums[i].length(); j++) {
                maxDigit = max(maxDigit, getIntDigit(nums[i][j]));
            }
        }
        for (int p = max(2,maxDigit+1); p <= 20; p++) {
            if (toBase10(nums[0],p)+toBase10(nums[1],p)
                                    == toBase10(nums[2],p))
                result.push_back(p);
        }
        return result;
    }
private:
    int getIntDigit(const char c) {
        if (isdigit(c)) return c - '0';
        else return 10 + c - 'A';
    }
    int toBase10(const string& s, const int p) {
        int d = 0;
        for (int i = 0; i < s.length(); i++) {
            d *= p;
            d += getIntDigit(s[i]);
        }
        return d;
    }
};

Salary

| 09:09

問題文

給料を計算。

class Salary {
public:
    int howMuch(vector <string> arrival, vector <string> departure, int wage) {
        double amount = 0;
        for (int i = 0; i < arrival.size(); i++) {
            const static int NIGHT_END = calcTime(6, 0, 0);
            const static int EVENING_START = calcTime(18, 0, 0);
            const static double SEC_PER_HOUR = 60 * 60;
            int hh, mm, ss;
            sscanf(arrival[i].c_str(), "%d:%d:%d", &hh, &mm, &ss);
            int aTime = calcTime(hh, mm, ss);
            sscanf(departure[i].c_str(), "%d:%d:%d", &hh, &mm, &ss);
            int dTime = calcTime(hh, mm, ss);
            if (aTime < NIGHT_END) {
                if (dTime < NIGHT_END) {
                    amount += 1.5 * wage * (dTime-aTime)/SEC_PER_HOUR;
                    dTime = aTime;
                } else {
                    amount += 1.5 * wage * (NIGHT_END-aTime)/SEC_PER_HOUR;
                    aTime = NIGHT_END;
                }
            }
            if (dTime > EVENING_START) {
                if (aTime >= EVENING_START) {
                    amount += 1.5 * wage * (dTime-aTime)/SEC_PER_HOUR;
                    aTime = dTime;
                } else {
                    amount += 1.5 * wage * (dTime-EVENING_START)/SEC_PER_HOUR;
                    dTime = EVENING_START;
                }
            }
            amount += wage * (dTime-aTime)/SEC_PER_HOUR;
        }
        return static_cast<int>(floor(amount));
    }
private:
    int calcTime(const int h, const int m, const int s) {
        return (h*60 + m) * 60 + s;
    }
};

2009-07-24

Quipu

| 05:41

問題文

SRM 445 は参加登録はしたが、眠かったので不参加。

特殊な形式の十進数の数を、整数形式に変換。

class Quipu {
public:
    int readKnots(string knots) {
        int result = 0;
        for (int i = 1; i < knots.length()-1; i++) {
            if (knots[i] == 'X') result++;
            else result *= 10;
        }
        return result;
    }
};