Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

2009-08-03

TennisRallies

| 13:00

このDIV2の問題セットは、初めて時間内に全問を解くことができた。合計1255.1点で、overviewによると部門2位に当たる成績。

問題文

禁止されたショットの連続を含まないラリーを何種類作れるか。最悪のケースが2の18乗(=262144)なので、Brute-forceな方法でも終わる。

class TennisRallies {
    public:
        int howMany(int numLength, vector <string> forbidden, int allowed) {
            count = 0;
            string raly(numLength, ' ');
            go(raly, 0, 0, numLength, forbidden, allowed);
            return count;
        }
    private:
        int count;
        void go(string& raly, int p, int fCount, const int numLength,
                const vector<string>& forbidden, const int allowed) {
            for (int i = 0; i < forbidden.size(); i++) {
                const int fLen = forbidden[i].length();
                if (p >= fLen && raly.substr(p-fLen,fLen) == forbidden[i])
                    fCount++;
            }
            if (fCount >= allowed) return;
            if (p == numLength) {
                count++;
                return;
            }
            raly[p] = 'c';
            go(raly, p+1, fCount, numLength, forbidden, allowed);
            raly[p] = 'd';
            go(raly, p+1, fCount, numLength, forbidden, allowed);
        }
};

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

CardCount

| 18:38

問題文

カード配り。

class CardCount {
    public:
        vector <string> dealHands(int numPlayers, string deck) {
            vector <string> result(numPlayers);
            for (int i = 0; i < deck.size()/numPlayers; i++) {
                for (int j = 0; j < numPlayers; j++) {
                    result[j] += string(1, deck[i*numPlayers+j]);
                }
            }
            return result;
        }
};

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/