Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

ReverseMagicalSource

| 12:48

SRM 451 Div2 は250と500を通せて、511.38(245.92+265.46)点だった。Ratingは 1074 から 1119 に上がった。

問題文, SRM 451

 x=10^0s+10^1s+10^2s+\cdots10^is > A \mbox{ } (i \ge 0)を満たす最小の xを求める。

245.92/250

class ReverseMagicalSource {
public:
    int find(int source, int A) {
        int x = source;
        while (x <= A) {
            source *= 10;
            x += source;
        }
        return x;
    }
};

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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/caligue/20091021