Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-18

CrossCountry

| 11:38

問題文, SRM 171

クロスカントリーの団体戦の順位決め。強引に解いた。

434.52/600

struct Team {
    char id;
    vector<int> ranks;
    int sum;
    Team() {}
    Team(const char id) : id(id), sum(0) {}
    void addMember(const int rank) {
        ranks.push_back(rank);
        if (ranks.size() <= 5)
            sum += rank;
    }
};

bool compTeam(const Team& a, const Team& b) {
    if (a.sum < b.sum) {
        return true;
    } else if (a.sum > b.sum) {
        return false;
    } else {
        if (a.ranks.size() >= 6 && b.ranks.size() >= 6) {
            return a.ranks[5] < b.ranks[5];
        } else if (a.ranks.size() >= 6) {
            return true;
        } else if (b.ranks.size() >= 6) {
            return false;
        } else {
            return a.id < b.id;
        }
    }
}

class CrossCountry {
    public:
        string scoreMeet(int numTeams, string finishOrder) {
            vector<Team> teams;
            for (int i = 0; i < finishOrder.size(); i++) {
                for (int j = 0; j < teams.size()+1; j++) {
                    if (j == teams.size()) {
                        teams.push_back(Team(finishOrder[i]));
                        teams.back().addMember(i+1);
                        break;
                    }
                    if (teams[j].id == finishOrder[i]) {
                        teams[j].addMember(i+1);
                        break;
                    } 
                }
            }
            sort(teams.begin(), teams.end(), compTeam);
            string result;
            for (int i = 0; i < teams.size(); i++) 
                if (teams[i].ranks.size() >= 5)
                    result += string(1, teams[i].id);
            return result;
        }
};

TravonTravon2011/07/22 13:02Thanky Thanky for all this good ifnomratoin!

gupcpicgupcpic2011/07/22 22:31kmdB9M <a href="http://cevhxxxwszda.com/">cevhxxxwszda</a>

veodtbhveodtbh2011/07/23 18:51k7GCNy , [url=http://znpabhftaumk.com/]znpabhftaumk[/url], [link=http://xesvtenonofo.com/]xesvtenonofo[/link], http://mhkeoikkfact.com/

nwckjlffjonnwckjlffjon2011/07/24 22:34Ay0Rwh <a href="http://xydzsizmpqzc.com/">xydzsizmpqzc</a>

ijegpfoijegpfo2011/07/25 02:15l2YNWI , [url=http://cerpmieqmstu.com/]cerpmieqmstu[/url], [link=http://siawcpyjgwzt.com/]siawcpyjgwzt[/link], http://jkowkmsdcydd.com/

2009-08-12

RecurrenceRelation

| 12:51

問題文

与えられた漸化式のN番目の値を求める。システムテストで1回落とされた。

298.29/500 - 00:20:58

class RecurrenceRelation {
    public:
        int moduloTen(vector <int> coefficients, vector <int> initial, int N) {
            const int k = coefficients.size();
            for (int i = 0; i < k; i++) 
                initial[i] = myMod(initial[i]);
            cout << endl;
            for (int i = k; i <= N; i++) {
                int x = 0;
                for (int j = i-1; j >= i-k; j--) 
                    x += coefficients[k-(i-j)] * initial[j];
                cout << i << " " << x << endl;
                x = myMod(x);
                initial.push_back(x);
            }
            return initial[N];
        }
    private:
        int myMod(const int x) {
            if (x >= 0) return x % 10;
            else return (10 - ((-x)%10)) % 10;
        }
};

JusticeJustice2011/07/09 15:18Created the greatest artclies, you have.

dhumgkuquyrdhumgkuquyr2011/07/10 00:44RBBBkV <a href="http://hjbppmyhkpug.com/">hjbppmyhkpug</a>

oipwdeoipwde2011/07/11 20:03vO7rh7 <a href="http://ampmjgepjkgf.com/">ampmjgepjkgf</a>

2009-08-11

Twain

| 19:36

問題文

問題文の通りに文字列を変換する。やるだけの問題だが、書く必要があるコード量が多い。一回目にサブミットしたプログラムはバグがあり、システムテストは通らなかった。

184.88/500 - 00:42:14 (failed)

class Twain {
    public:
        string getNewSpelling(int year, string phrase) {
            vector<char> exceptions;
            exceptions.push_back('a'); exceptions.push_back('e');
            exceptions.push_back('i'); exceptions.push_back('o');
            exceptions.push_back('u');
            for (int y = 1; y <= year; y++) {
                string tmpStr;
                int len;
                switch (y) {
                    case 1:
                        if (phrase[0] == 'x') phrase[0] = 'z';
                        phrase = replaceCharsOfWord(phrase, " x", " z");
                        phrase = replaceCharsOfWord(phrase, "x", "ks");
                        break;
                    case 2:
                        phrase = replaceCharsOfWord(phrase, "y", "i");
                        break;
                    case 3:
                        phrase = replaceCharsOfWord(phrase, "ce", "se");
                        phrase = replaceCharsOfWord(phrase, "ci", "si");
                        break;
                    case 4:
                        do {
                            tmpStr = phrase;
                            phrase = replaceCharsOfWord(phrase, "ck", "k");
                        } while (tmpStr != phrase);
                        break;
                    case 5:
                        if (phrase.substr(0,3) == "sch") 
                            phrase = "sk" + phrase.substr(3);
                        phrase = replaceCharsOfWord(phrase, " sch", " sk");
                        phrase = replaceCharsOfWord(phrase, "chr", "kr");
                        for (char c = 'a'; c <= 'z'; c++) {
                            if (c == 'h') continue;
                            string pattern("c"+string(1,c));
                            string placement("k"+string(1,c));
                            phrase = replaceCharsOfWord(phrase, pattern, placement);
                        }
                        phrase = replaceCharsOfWord(phrase, "c ", "k ");
                        len = phrase.length();
                        if (phrase[len-1] == 'c') phrase[len-1] = 'k';
                        break;
                    case 6:
                        if (phrase.substr(0,2) == "kn")
                            phrase = "n" + phrase.substr(2);
                        phrase = replaceCharsOfWord(phrase, " kn", " n");
                        break;
                    case 7:
                        do {
                            tmpStr = phrase;
                            for (char c = 'a'; c <= 'z'; c++) {
                                if (find(exceptions.begin(),exceptions.end(),c) == exceptions.end()) {
                                    string pattern(2,c);
                                    string placement(1,c);
                                    phrase = replaceCharsOfWord(phrase, pattern, placement);
                                }
                            }
                        } while (tmpStr != phrase);
                        break;
                }
            }
            return phrase;
        }
    private:
        string replaceCharsOfWord(const string& phrase, 
                const string pattern, const string placement) {
            string result;
            string::size_type pos = 0;
            string::size_type pre_pos = 0;
            string::size_type pat_len = pattern.length();
            while ((pos = phrase.find(pattern,pos)) != string::npos) {
                result.append(phrase, pre_pos, pos-pre_pos);
                result.append(placement);
                pos += pat_len;
                pre_pos = pos;
            }
            result.append(phrase, pre_pos, phrase.length()-pre_pos);
            return result;
        }
};

OliviaOlivia2011/07/09 22:49Ppl like you get all the birans. I just get to say thanks for he answer.

cganpmvkaacganpmvkaa2011/07/10 00:21ozUmeq <a href="http://pjfcqeeeqmnr.com/">pjfcqeeeqmnr</a>

gkbfwfvcbgkbfwfvcb2011/07/10 21:09Bo1aDa , [url=http://xrkdnugczyzj.com/]xrkdnugczyzj[/url], [link=http://sbngsfqxhlpy.com/]sbngsfqxhlpy[/link], http://safjlfwoassi.com/

uxpnpunauxpnpuna2011/07/11 20:32crHIwv <a href="http://fodsgqzsvyim.com/">fodsgqzsvyim</a>

mhhaaumhhaau2011/07/12 21:58da56vU , [url=http://tqvvgrxdnlwt.com/]tqvvgrxdnlwt[/url], [link=http://ofcuaexemicz.com/]ofcuaexemicz[/link], http://shzifphpejdh.com/

2009-08-10

NumberGuesser

| 19:34

問題文

数字を推測。自力で解けなかった。総当たりで解いたが、数学的な解法もある。

190.54/500 - 01:06:07 (cheated)

class NumberGuesser {
    public:
        int guess(string leftOver) {
            int candidate = 0;
            for (int d = 1; d <= 9; d++) {
                int found = 0;
                for (int i = 0; i < 4; i++) {
                    ostringstream oss;
                    oss << leftOver.substr(0,i) << d << leftOver.substr(i);
                    int z;
                    istringstream(oss.str()) >> z;
                    for (int x = 1; x+z <= 9998; x++) {
                        int y = x + z;
                        if (isDigitMatch(x, y)) {
                            candidate = d;
                            found++;
                            break;
                        }
                    }
                }
                if (found == 4) return d;
            }
            return candidate;
        }
    private:
        bool isDigitMatch(int x, int y) {
            vector<int> ndigits(10, 0);
            while (x > 0) {
                if (x%10 != 0) ndigits[x%10]++;
                x /= 10;
            }
            while (y > 0) {
                if (y%10 != 0) ndigits[y%10]--;
                y /= 10;
            }
            for (int i = 0; i < ndigits.size(); i++) {
                if (ndigits[i] != 0)
                    return false;
            }
            return true;
        }
};

2009-08-08

Animation

| 19:40

問題文

粒子の動き。強引に解きすぎて、バグが増え、時間がかかった。

150.00/500 - 00:57:22

class Animation {
    public:
        vector <string> animate(int speed, string init) {
            const int len = init.length();
            const static char RIGHT = '1';
            const static char LEFT = '2';
            string pre(init);
            for (int i = 0; i < len; i++) {
                if (pre[i] == 'R') pre[i] = RIGHT;
                else if (pre[i] == 'L') pre[i] = LEFT;
                else pre[i] = 0;
            }
            vector <string> result;
            while (true) {
                string s(toX(pre));
                result.push_back(s);
                if (find(s.begin(),s.end(),'X') == s.end())
                    break;
                s = string(len, 0);
                for (int i = 0; i < len; i++) {
                    int d;
                    switch (pre[i]) {
                    case RIGHT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        break;
                    case LEFT:
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    case RIGHT+LEFT:
                        d = i + speed;
                        if (d < len) s[d] += RIGHT;
                        d = i - speed;
                        if (d >= 0) s[d] += LEFT;
                        break;
                    }
                }
                pre = s;
            }
            return result;
        }
    private:
        string toX(const string& s) {
            string ret(s.length(), '.');
            for (int i = 0; i < s.length(); i++)
                if (s[i] != 0)
                    ret[i] = 'X';
            return ret;
        }
};

BinaryCardinality

| 19:29

問題文

立っているビット数が少ない順にソート。300の問題よりこっちの方が解きやすかった。提出した後に気づいたことだけど、比較関数の中でbitsetを使えば、余計なvector配列を使う必要がないな。

453.99/500 - 00:09:18

bool compBinary(const bitset<32>& a, const bitset<32>& b)
{
    if (a.count() < b.count()) {
        return true;
    } else if (a.count() > b.count()) {
        return false;
    } else {
        return a.to_ulong() < b.to_ulong();
    }
}

class BinaryCardinality {
    public:
        vector <int> arrange(vector <int> numbers) {
            const int size = numbers.size();
            vector<bitset<32> > binaries(size);
            for (int i = 0; i < size; i++)
                binaries[i] = numbers[i];
            sort(binaries.begin(), binaries.end(), compBinary);
            vector <int> result(size);
            for (int i = 0; i < size; i++)
                result[i] = static_cast<int>(binaries[i].to_ulong());
            return result;
        }
};

ewnfzgewnfzg2011/02/28 00:358HHlV6 <a href="http://nfypkepkeych.com/">nfypkepkeych</a>, [url=http://azgnisbcmhab.com/]azgnisbcmhab[/url], [link=http://jedmlehhrowo.com/]jedmlehhrowo[/link], http://pqvizwthqdkq.com/

2009-08-07

ParallelSpeedup

| 19:21

問題文

何基のコンピュータを使って、並列処理させた場合が一番速いのかを求める。

388.73/500 - 00:16:33

class ParallelSpeedup {
    public:
        int numProcessors(int k, int overhead) {
            long long minTime = k;
            for (int p = 2; p <= k; p++) {
                const long long time = overhead*calcCommCount(p) 
                    + static_cast<long long>(ceil(static_cast<double>(k)/p));
                if (time >= minTime) 
                    return p-1;
                minTime = time;
            }
            return k;
        }
    private:
        long long calcCommCount(const int p) {
            return static_cast<long long>(p) * (p-1) / 2;
        }
};

2009-08-06

PartySeats

| 19:16

問題文 PartySeats

席順決め。

class PartySeats {
    public:
        vector <string> seating (vector <string> attendees) {
            multiset<string> boys, girls;
            for (int i = 0; i < attendees.size(); i++) {
                string name, gender;
                istringstream iss(attendees[i]);
                iss >> name >> gender;
                if (gender[0] == 'b') boys.insert(name);
                else girls.insert(name);
            }
            vector<string> result;
            if (boys.size() != girls.size() || boys.size()%2 == 1)
                return result;
            multiset<string>::const_iterator bItr = boys.begin();
            multiset<string>::const_iterator gItr = girls.begin();
            result.push_back("HOST");
            for (int i = 0; i < attendees.size()/2; i += 2) {
                result.push_back(*gItr); gItr++;
                result.push_back(*bItr); bItr++;
            }
            result.push_back("HOSTESS");
            for (int i = attendees.size()/2; i < attendees.size(); i += 2) {
                result.push_back(*bItr); bItr++;
                result.push_back(*gItr); gItr++;
            }
            return result;
        }
};

NathalieadsonNathalieadson2012/07/10 00:48Unparaellled accuracy, unequivocal clarity, and undeniable importance!

qumvofqumvof2012/07/10 15:55k9l8Kn <a href="http://ffbnrpylucxq.com/">ffbnrpylucxq</a>

kxvfpogrvtkxvfpogrvt2012/07/10 21:52DUrnSr , [url=http://odqnuvepnfcs.com/]odqnuvepnfcs[/url], [link=http://gllexsagvhok.com/]gllexsagvhok[/link], http://ctntvviqpnwt.com/

ahphkwegfjvahphkwegfjv2012/07/12 12:12jHPHB5 <a href="http://wujnvnxoozdt.com/">wujnvnxoozdt</a>

2009-08-05

CalendarRecycle

| 19:09

問題文

次にカレンダーを使いまわせる年を求める。

class CalendarRecycle {
    public:
        int useAgain(int year) {
            int day = 0;
            const pair<bool,int> yearPair = make_pair(isLeapYear(year),day);
            for (int y = year+1; ; y++) {
                if (isLeapYear(y-1)) day = (day+366) % 7;
                else day = (day+365) % 7;
                if (yearPair == make_pair(isLeapYear(y),day))
                    return y;
            }
            return -1;
        }
    private:
        bool isLeapYear(const int year) {
            return (year%4 == 0 && year%100 != 0) || year%400 == 0;
        }
};

2009-08-04

PaperFold

| 18:43

問題文

8回以下の回数だけ紙を折ることで、箱にその紙を納められるか。

class PaperFold {
    public:
        int numFolds(vector <int> paper, vector <int> box) {
            box.push_back(0);
            queue<vector<int> > Q;
            Q.push(box);
            while (!Q.empty()) {
                vector<int> b = Q.front(); Q.pop();
                if (b[2] > 8) continue;
                if (isFit(paper, b)) return b[2];
                b[2]++;
                b[0] *= 2; Q.push(b);
                b[0] /= 2; b[1] *= 2; Q.push(b);
            }
            return -1;
        }
    private:
        bool isFit(const vector<int>& paper, const vector<int>& box) {
            return (paper[0] <= box[0] && paper[1] <= box[1]) ||
                (paper[0] <= box[1] && paper[1] <= box[0]);
        }
};

2009-08-03

StringTrain

| 18:38

問題文

電車の連結。PrefixとSuffixの問題。

class StringTrain {
    public:
        string buildTrain(vector <string> cars) {
            string train = cars[0];
            for (int i = 1; i < cars.size(); i++) {
                const int len_train = train.length();
                const int len_car = cars[i].length();
                for (int j = len_car-1; j >= 1; j--) {
                    if (len_train <= j) continue;
                    if (train.substr(len_train-j,j) == cars[i].substr(0,j)) {
                        train = train + cars[i].substr(j);
                        break;
                    } 
                }
            }
            set<char> appeared;
            ostringstream oss;
            for (int i = train.length()-1; i >= 0; i--) {
                if (appeared.find(train[i]) == appeared.end()) {
                    oss << train[i];
                    appeared.insert(train[i]);
                }
            }
            string strAfterRemv(oss.str());
            reverse(strAfterRemv.begin(), strAfterRemv.end());
            ostringstream resoss;
            resoss << train.length() << " " << strAfterRemv;
            return resoss.str();
        }
};

DennysDennys2012/07/10 08:54There's a trefriic amount of knowledge in this article!

ptkxkwfiufxptkxkwfiufx2012/07/11 08:32rW3Q5y <a href="http://lvoddmvsamev.com/">lvoddmvsamev</a>

ssurmbuvpsmssurmbuvpsm2012/07/11 21:20GnFEME , [url=http://jcvsaeuskkgr.com/]jcvsaeuskkgr[/url], [link=http://iseogblgtggc.com/]iseogblgtggc[/link], http://nsaattulsfhk.com/

xtmpsysmfgnxtmpsysmfgn2012/07/12 13:058VKorp <a href="http://qspzckisagzz.com/">qspzckisagzz</a>

ueblizedjueblizedj2012/07/12 18:376GmZzo , [url=http://rtmucgtfbosq.com/]rtmucgtfbosq[/url], [link=http://dzmpwnhervlx.com/]dzmpwnhervlx[/link], http://trmherritlub.com/