Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-16

CircleGame

| 17:07

問題文

カードの13(King)と隣接したカード数が13になる場合は、それらの数を抜き、最後に残るデッキのカードの数を求める。問題を連続する数が13になる場合に抜くと、読み間違えてしまって、解くのに時間がかかった。

103.92/250

class CircleGame {
    public:
        int cardsLeft(string deck) {
            map<char,int> toNum;
            toNum['A']=1; toNum['2']=2; toNum['3']=3; toNum['4']=4; toNum['5']=5;
            toNum['6']=6; toNum['7']=7; toNum['8']=8; toNum['9']=9; toNum['T']=10;
            toNum['J']=11; toNum['Q']=12; toNum['K']=13;
            while (true) {
                string::size_type p = deck.find('K');
                if (p == string::npos) break;
                deck.erase(p, 1);
            }
            bool changed = true;
            while (changed) {
                changed = false;
                for (int i = 0; i < deck.size(); i++) {
                    int j = (i+1) % deck.size();
                    if (toNum[deck[i]]+toNum[deck[j]] == 13) {
                        changed = true;
                        string next;
                        for (int k = 0; k < deck.size(); k++)
                            if (k!=i && k!=j)
                                next += deck[k];
                        deck = next;
                        break;
                    }
                }
            }
            return deck.size();
        }
};

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/