Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-21

SmartElevator

| 13:12

問題文, SRM 156

エレベータが、全ての乗客を運び終えるのにかかる最短の時間を求める。

231.89/550

class SmartElevator {
public:
    int timeWaiting(vector <int> arrivalTime, vector <int> startingFloor, vector <int> destinationFloor) {
        int numPeople = arrivalTime.size();
        string pat(numPeople*2, '0');
        for (int i = 0; i < numPeople; i++)
            pat[i*2] = pat[i*2+1] = i+'0';  
        int minTime = INT_MAX;
        do {
            int floor = 1;
            int time = 0;
            vector<bool> pickedup(numPeople, false);
            for (int i = 0; i < numPeople*2; i++) {
                int e = pat[i]-'0';
                if (pickedup[e]) {
                    int distance = abs(floor-destinationFloor[e]);
                    time += abs(distance);
                    floor = destinationFloor[e];
                } else {
                    int distance = abs(floor-startingFloor[e]);
                    time = max(arrivalTime[e], time+distance);
                    floor = startingFloor[e];
                    pickedup[e] = true;
                }
            }
            minTime = min(minTime, time);
        } while (next_permutation(pat.begin(), pat.end()));
        return minTime;
    }
};

2009-08-16

Masterbrain

| 12:25

問題文

一回だけ嘘をついていいというルールがある数字当てゲーム

203.27/600

class Masterbrain {
    public:
        int possibleSecrets(vector <string> guesses, vector <string> results) {
            const int numGuesses = guesses.size();
            vector<int> blacks(numGuesses), whites(numGuesses);
            for (int i = 0; i < numGuesses; i++)
                sscanf(results[i].c_str(), "%db %dw", &blacks[i], &whites[i]);
            codes.clear();
            string code(4, ' ');
            make_codes(code, 0);
            set<string> possibleCodes;
            for (vector<string>::const_iterator cd = codes.begin(); 
                    cd != codes.end(); cd++) {
                vector<bool> judges(numGuesses);
                for (int i = 0; i < numGuesses; i++)
                    judges[i] = checkCode(*cd, guesses[i], blacks[i], whites[i]);
                if (find(judges.begin(),judges.end(),false) == judges.end())
                    continue;

                for (int f = 0; f < numGuesses; f++) {
                    for (int i = 0; i < numGuesses+1; i++) {
                        if (i == f) {
                            if (judges[i]) break;
                            else continue;
                        }
                        if (i == numGuesses) {
                            possibleCodes.insert(*cd);
                            break;
                        }
                        if (!judges[i]) break;
                    }
                }
            }
            return possibleCodes.size();
        }
    private:
        vector<string> codes;
        const static int CODE_LENGTH = 4;
        const static int MAX_DIGIT = 7;
        void make_codes(string& code, const int p) {
            if (p == CODE_LENGTH) {
                codes.push_back(code);
                return;
            }
            for (char c = '1'; c < '1'+MAX_DIGIT; c++) {
                code[p] = c;
                make_codes(code, p+1);
            }
        }
        bool checkCode(const string& code, 
                const string& guess, int black, int white) {
            vector<int> cgn(MAX_DIGIT, 0); // counter for guessed number
            vector<int> crw(MAX_DIGIT, 0); // counter for remaining whites
            for (int i = 0; i < CODE_LENGTH; i++) {
                if (code[i] == guess[i]) {
                    black--;
                } else {
                    cgn[guess[i]-'1']++;
                    crw[code[i]-'1']++;
                }
            }
            if (black != 0) return false;
            for (int i = 0; i < MAX_DIGIT; i++)
                white -= min(cgn[i], crw[i]);
            return white == 0;
        }
};

JustinJustin2012/07/09 19:31I see, I supospe that would have to be the case.

itwtrmfvceitwtrmfvce2012/07/10 15:227kAAqh <a href="http://zylafgrfzjbl.com/">zylafgrfzjbl</a>

cdweglzcdweglz2012/07/10 21:17xepmZu , [url=http://onfgnghtzitt.com/]onfgnghtzitt[/url], [link=http://nlacaozvfktq.com/]nlacaozvfktq[/link], http://aepzieiyvpsn.com/

hkdwpsqnvkhkdwpsqnvk2012/07/12 17:09QYS2QK , [url=http://toyoaqaciajc.com/]toyoaqaciajc[/url], [link=http://bwrudfijrmmm.com/]bwrudfijrmmm[/link], http://zvmupojzjimj.com/

2009-08-11

FairWorkload

| 13:17

問題文

仕事をなるべく均等になるように割り振る。良問。Level-2の問題より解きやすかった。

532.87/1000 - 00:32:37

class FairWorkload {
    public:
        int getMostWork(vector <int> folders, int workers) {
            amounts = vector<int>(workers, 0);
            maxOptimalAmount = INT_MAX;
            go(folders, 0, workers, 0);
            return maxOptimalAmount;
        }
    private:
        int maxOptimalAmount;
        vector<int> amounts;
        void go(const vector<int>& folders, const int f_id, 
                const int workers, const int w_id) {
            if (f_id == folders.size()) {
                for (int i = 0; i < workers; i++)
                    if (amounts[i] == 0)
                        return;
                maxOptimalAmount = min(maxOptimalAmount, 
                        *max_element(amounts.begin(),amounts.end()));
                return;
            }
            if (maxOptimalAmount <= amounts[w_id]) return;
            if (w_id == workers) return;
            amounts[w_id] += folders[f_id];
            go(folders, f_id+1, workers, w_id);
            amounts[w_id] -= folders[f_id];
            if (w_id+1 == workers) return;
            amounts[w_id+1] += folders[f_id];
            go(folders, f_id+1, workers, w_id+1);
            amounts[w_id+1] -= folders[f_id];
        }
};

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-08

Workshop

| 19:29

問題文

作れる三角形の数を数える。

267.09/300 - 00:10:38

class Workshop {
    public:
        int pictureFrames(vector <int> pieces) {
            int result = 0;
            sort(pieces.begin(), pieces.end());
            const int size = pieces.size();
            for (int i = 0; i < size-2; i++) {
                for (int j = i+1; j < size-1; j++) {
                    for (int k = j+1; k < size; k++) {
                        if (pieces[i]<pieces[j]+pieces[k] &&
                                pieces[j]<pieces[i]+pieces[k] &&
                                pieces[k]<pieces[i]+pieces[j])
                            result++;
                    }
                }
            }
            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-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]);
        }
};

LCMRange

| 18:43

問題文

最小公倍数の問題。

class LCMRange {
    public:
        int lcm(int first, int last) {
            int result = first;
            for (int i = first+1; i <= last; i++) {
                result = lcd(result, i);
            }
            return result;
        }
    private:
        int gcd(int c, int d) {
            int v;
            v = c;
            while (v > 0) {
                v = c % d;
                c = d;
                d = v;
            }
            return c;
        }
        int lcd(int c, int d) {
            return c*d / gcd(c,d);
        }
};

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

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/

2009-07-26

HourGlass

| 11:16

問題文

2つの砂時計を使って測れる時間を求める。Brute-forceで解ける問題だけど、どういう状態を調べれば解けるのかがわからなかった。慣れるしかないか。

class HourGlass {
public:
    vector <int> measurable(int glass1, int glass2) {
        g1 = glass1;
        g2 = glass2;
        times.clear();
        memo = vector<vector<vector<bool> > >(MAX_POSSIBLE_TIME+1, 
                vector<vector<bool> >(g1+1, vector<bool>(g2+1,false)));
        go(0, 0, 0);
        const static int RETURN_VALUES = 10;
        vector <int> result(RETURN_VALUES);
        set<int>::const_iterator itr = times.begin();
        for (int i = 0; i < RETURN_VALUES; i++) {
            itr++;
            result[i] = *itr;
        }
        return result;
    }
private:
    set<int> times;
    int g1, g2;
    const static int MAX_POSSIBLE_TIME = 500;
    vector<vector<vector<bool> > > memo;
    void go(const int sand1, const int sand2, const int time) {
        if (time > MAX_POSSIBLE_TIME) return;
        if (memo[time][sand1][sand2]) return;
        memo[time][sand1][sand2] = true;
        times.insert(time);
        if (sand1==0 || sand2==0) {
            go(g1-sand1, sand2, time);
            go(sand1, g2-sand2, time);
            go(g1-sand1, g2-sand2, time);
        }
        if (sand1>0 && sand2==0) go(0, 0, time+sand1);
        if (sand2>0 && sand1==0) go(0, 0, time+sand2);
        if (sand1>0 && sand2>0) {
            int minSand = min(sand1, sand2);
            go(sand1-minSand, sand2-minSand, time+minSand);
        }
    }
};

2009-07-24

PaternityTest

| 08:29

問題文

子が母と父両方から半分ずつ遺伝情報を受けついでいるかを調べる。初めは母と子が半分一致するパターンを全パターン作るという、最悪の場合で計算量が2^20となる実装を行って提出するも、timeoutされた。それで結局、Editorialを見た。両方にマッチしなかったら除外してよいという事実には気付けなかった。

class PaternityTest {
public:
    vector <int> possibleFathers(string child, string mother, vector <string> men) {
        vector <int> result;
        for (int i = 0; i < men.size(); i++) {
            if (isFather(child, mother, men[i]))
                result.push_back(i);
        }
        return result;
    }
private:
    bool isFather(const string& child, const string& mother,
                  const string& man) {
        const int len = child.length();
        int matches = 0;
        for (int i = 0; i < len; i++) {
            if (child[i] == man[i]) matches++;
            else if (child[i] != mother[i]) return false;
        }
        return matches >= len/2;
    }
};

2009-07-22

PickTeam

| 13:32

問題文

相性が最高なチームを作る。なにか特別な方法があるのかと思ったけど、総当たりで解ける問題だった。

class PickTeam {
public:
    vector <string> pickPeople(int teamSize, vector <string> people) {
        const int n = people.size();
        vector<vector<int> > g(n, vector<int>(n));
        vector<string> names(n);
        for (int i = 0; i < n; i++) {
            istringstream iss(people[i]);
            iss >> names[i];
            for (int j = 0; j < n; j++) {
                iss >> g[i][j];
            }
        }

        maxScore = INT_MIN;
        findMaxScore(bitset<32>(0), 0, 0, teamSize, n, g);
        vector <string> result;
        for (int i = 0; i < n; i++) {
            if (maxSet[i] == 1) {
                result.push_back(names[i]);
            }
        }
        sort(result.begin(), result.end());
        return result;
    }
private:
    int maxScore;
    bitset<32> maxSet;
    void findMaxScore(bitset<32> subset, const int ptr, const int onBits,
            const int teamSize, const int n, const vector<vector<int> >& g) {
        if (onBits == teamSize) {
            int score = 0;
            for (int i = 0; i < n; i++) {
                if (subset[i] != 1) continue;
                for (int j = i+1; j < n; j++) {
                    if (subset[j] != 1) continue;
                    score += g[i][j];
                }
            }
            if (score > maxScore) {
                maxScore = score;
                maxSet = subset;
            }
            return;
        }
        if (ptr == n) return;
        findMaxScore(subset, ptr+1, onBits, teamSize, n, g);
        subset[ptr] = 1;
        findMaxScore(subset, ptr+1, onBits+1, teamSize, n, g);
    }
};