Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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-05-02

BridgeCrossing

| 18:09

問題文

456.12->950.72->985.42 / 1000

わからなくて Editorial を見た。Brute force な方法で解ける。

class BridgeCrossing {
public:
    int minTime(vector <int> times) {
        n = times.size();
        if (n == 1)
            return times[0];
        int best = 9999999;
        vector<bool> side(n, false);
        go(times, 0, n, side, best);
        return best;
    }
private:
    int n;
    void go(const vector<int>& times, const int tm, const int left,
            vector<bool>& side, int& best) {
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!side[i] && !side[j]) {
                    side[i] = side[j] = true;
                    int new_tm = tm + max(times[i],times[j]);
                    if (left == 2) {
                        best = min(best, new_tm);
                    } else {
                        for (int k = 0; k < n; k++) {
                            if (side[k]) {
                                side[k] = false;
                                go(times, new_tm+times[k], left-1,
                                        side, best);
                                side[k] = true;
                            }
                        }
                    }
                    side[i] = side[j] = false;
                }
            }
        }
    }
};

RectangularGrid

| 18:11

問題文

436.45->498.51 / 500

widht×height のグリッドに含まれる長方形(ただし正方形は除外)の数を求めよ、という問題。解法はすぐに思いついた。

class RectangularGrid {
public:
    long long countRectangles(int width, int height) {
        long long rectangles = 0;
        for (int w = 1; w <= width; w++) {
            for (int h = 1; h <= height; h++) {
                if (w == h) continue;
                rectangles += (width-w+1) * (height-h+1);
            }
        }
        return rectangles;
    }
};

Yahtzee

| 11:48

問題文

245.61->249.76 / 250

極めて簡単な問題。

class YahtzeeScore {
public:
    int maxPoints(vector <int> toss) {
        vector<int> sum(7, 0);
        for (int i = 0; i < toss.size(); i++)
            sum[toss[i]] += toss[i];
        return *max_element(sum.begin(), sum.end());
    }
};