Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-10-14

OmahaLow

| 14:30

問題文, SRM 206

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

あるトランプゲームにおいて、最善の手を求める。

121.31/250 (cheated)

class OmahaLow {
public:
    string low(string sharedCards, string playersCards) {
        string ret = "";
        sort(sharedCards.rbegin(), sharedCards.rend());
        sort(playersCards.rbegin(), playersCards.rend());
        do {
            do {
                string s = sharedCards.substr(0,3) + playersCards.substr(0,2);
                sort(s.rbegin(), s.rend());
                if (s[0] >= '9') continue;
                int i;
                for (i = 0; i < 4; i++) if (s[i] == s[i+1]) break;
                if (i < 4) continue;
                if (ret == "" || s < ret) ret = s;
            } while (next_permutation(playersCards.rbegin(), playersCards.rend()));
        } while (next_permutation(sharedCards.rbegin(), sharedCards.rend()));
        return ret;
    }
};

2009-09-09

GravityBomb

| 16:40

問題文, SRM 200

テトリスの局面において、隙間をなくすとどうなるか。

421.30/500

class GravityBomb {
    public:
        vector <string> aftermath (vector <string> board) {
            const int H = board.size();
            const int W = board[0].size();
            const static char BLOCK = 'X';
            vector<int> counter(W, 0);
            for (int i = 0; i < H; i++)
                for (int j = 0; j < W; j++)
                    if (board[i][j] == BLOCK)
                        counter[j]++;
            int minBlocks = *min_element(counter.begin(), counter.end());

            vector <string> result(H, string(W, '.'));
            for (int j = 0; j < W; j++)
                for (int i = 0; i < counter[j]-minBlocks; i++)
                    result[H-1-i][j] = BLOCK;
            return result;
        }
};

2009-09-06

BusinessTasks

| 09:12

問題文, SRM 236

Algorithm Tutorials -- How to Find a Solutionから。

円形に並べた仕事をn個飛ばしで選んで処理する。Joseph問題の一種。この問題サイズだったらvectorのeraseを使える。書き終わって気づいた。このプログラムにforループはいらなくて、whileループでいい。

238.23/250

class BusinessTasks {
public:
    string getTask(vector <string> list, int n) {
        int p = 0;
        for (int i = 0; list.size() > 1; i++) {
            p = (p + n-1) % list.size();
            p = list.erase(list.begin()+p) - list.begin();
        }
        return list[0];
    }
};

2009-09-01

| 17:45

問題文, SRM 203

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

使用可能なユーザ名を返す。

242.00/250

class UserName {
public:
    string newMember(vector <string> existingNames, string newName) {
        if (find(existingNames.begin(),existingNames.end(),newName) 
                == existingNames.end())
            return newName;
        for (int i = 1; ; i++) {
            ostringstream nameoss;
            nameoss << newName << i;
            if (find(existingNames.begin(),existingNames.end(),nameoss.str())
                    == existingNames.end())
                return nameoss.str();
        }
        return "";
    }
};

MitchellMitchell2011/07/11 00:05Big help, big help. And superlative news of crouse.

veiutvcwcveiutvcwc2011/07/11 02:29TlCswI <a href="http://vjnggvexbwuu.com/">vjnggvexbwuu</a>

zoksriviopzoksriviop2011/07/11 21:51epdS5v , [url=http://gqqjyfaqwssc.com/]gqqjyfaqwssc[/url], [link=http://mbceaafjqxom.com/]mbceaafjqxom[/link], http://qzkaecclvamc.com/

ntetzpntetzp2011/07/13 18:23bYD1yS <a href="http://bgyraruehckt.com/">bgyraruehckt</a>

mxixglmxixgl2011/07/14 00:35GtzmkZ , [url=http://mxgzmwjlggpm.com/]mxgzmwjlggpm[/url], [link=http://xraideylozrg.com/]xraideylozrg[/link], http://jcutzvphyqwn.com/

2009-08-30

Table

| 14:44

問題文, SRM 157

テーブルの形式を変換。

366.23/500

class Table {
public:
    vector <string> layout(vector <string> tbl) {
        const int rows = tbl.size();
        vector <string> result(rows, string(51, '?'));
        for (int r = 0; r < rows; r++) {
            istringstream iss(tbl[r]);
            int colspan, rowspan;
            char content, pad;
            int c = 0;
            while (iss >> pad >> colspan >> pad >> rowspan 
                     >> pad >> content >> pad) {
                while (result[r][c] != '?') c++;
                for (int rr = r; rr < r+rowspan; rr++)
                    for (int cc = c; cc < c+colspan; cc++)
                        result[rr][cc] = content;
                c = c + colspan;
            }
        }
        const int cols = result[0].find("?");
        for (int r = 0; r < rows; r++)
            result[r] = result[r].substr(0, cols);
        return result;
    }
};

MineField

| 11:43

問題文, SRM 169

マインスイーパ。

225.69/250

class MineField {
public:
    vector <string> getMineField(string mineLocations) {
        const static int SIZE = 9;
        vector <string> result(SIZE,string(SIZE,'0'));
        istringstream iss(mineLocations);
        char pad;
        int y, x;
        while (iss >> pad >> y >> pad >> x >> pad)
            result[y][x] = 'M';
        const static int d[8][2] = {
            {-1,-1}, {-1, 0}, {-1, 1},
            { 0,-1},          { 0, 1},
            { 1,-1}, { 1, 0}, { 1, 1} };
        for (y = 0; y < SIZE; y++)
            for (x = 0; x < SIZE; x++) {
                if (result[y][x] == 'M') continue;
                int counter = 0;
                for (int i = 0; i < 8; i++) {
                    int dy = y + d[i][0];
                    int dx = x + d[i][1];
                    if (0<=dy&&dy<SIZE && 0<=dx&&dx<SIZE 
                            && result[dy][dx] == 'M')
                        counter++;
                }
                result[y][x] += counter;
            }
        return result;
    }
};

UserId

| 11:21

問題文, SRM 164

ユーザIDを決める。

207.86/300

class UserId {
public:
    string id(vector <string> inUse, string first, string middle, string last) {
        first = truncate(first);
        middle = truncate(middle);
        last = truncate(last);
        if ((first == "BAD DATA" || middle == "BAD DATA" || last == "BAD DATA") ||
                first.length() < 2 || last.length() < 2)
            return "BAD DATA";

        string candidate = first[0] + last;
        if (candidate.length() > 8) candidate = candidate.substr(0,8);
        if (find(inUse.begin(),inUse.end(),candidate) == inUse.end())
            return candidate;
        if (middle.length() >= 1) {
            candidate = first[0] + string(1,middle[0]) + last;
            if (candidate.length() > 8) candidate = candidate.substr(0,8);
            if (find(inUse.begin(),inUse.end(),candidate) == inUse.end())
                return candidate;
        }
        for (int i = 1; i <= 99; i++) {
            candidate = first[0] + last;
            if (candidate.length() > 6) candidate = candidate.substr(0,6);
            ostringstream oss;
            oss << candidate << setw(2) << setfill('0') << i;
            candidate = oss.str();
            if (find(inUse.begin(),inUse.end(),candidate) == inUse.end())
                return candidate;
        }
        return "BAD DATA";
    }
private:
    string truncate(const string& s) {
        string ret;
        for (int i = 0; i < s.length(); i++) {
            if (isalpha(s[i])) ret += tolower(s[i]);
            else if (s[i] != '\'' && s[i] != ' ') return "BAD DATA";
        }
        return ret;
    }
};

2009-08-23

CheatCode

| 11:08

問題文, SRM 154

どの裏技コードを入力したかを判定。1回目に出したときは、しょうもないバグがあり、落とされた。

152.30/350

class CheatCode {
public:
    vector <int> matches(string keyPresses, vector <string> codes) {
        vector <int> result;
        const int keyLen = keyPresses.length();
        for (int i = 0; i < codes.size(); i++) {
            const int codeLen = codes[i].length();
            for (int j = 0; j < keyLen; j++) {
                if (codes[i][0] != keyPresses[j]) continue;
                int idx = 1;
                for (int k = j+1; idx < codeLen && k < keyLen; k++) {
                    if (codes[i][idx] == keyPresses[k])
                        idx++;
                    else if (keyPresses[k] != codes[i][idx-1])
                        break;
                }
                if (idx == codeLen) {
                    result.push_back(i);
                    break;
                }
            }
        }
        return result;
    }
};

2009-08-21

CrossWord

| 17:29

問題文, SRM 174

size個だけ連続した横方向の空白が、いくつあるのかを数える。

230.35/250

class CrossWord {
public:
    int countWords(vector <string> board, int size) {
        int count = 0;
        string pat(size, '.');
        pat = "X" + pat + "X";
        for (int i = 0; i < board.size(); i++) {
            board[i] = "X" + board[i] + "X";
            int idx = 0;
            while ((idx = board[i].find(pat,idx)) != string::npos) {
                count++;
                idx += size + 1;
            }
        }
        return count;
    }
};

WordForm

| 17:15

問題文, SRM 173

与えられた文字列は、どのような母音と子音の組み合わせから成るのか。

468.65/500

class WordForm {
public:
    string getSequence(string word) {
        string sequence;
        bool isPreVowel = false;
        for (int i = 0; i < word.length(); i++) {
            const char c = toupper(word[i]);
            bool isVowel = (i!=0 && !isPreVowel && c=='Y') ||
                c=='A' || c=='E' || c=='I' || c=='O' || c=='U';
            if (i == 0 || isVowel != isPreVowel) {
                if (isVowel) sequence += "V";
                else sequence += "C";
                isPreVowel = isVowel;
            }
        }
        return sequence;
    }
};

2009-08-20

ProgressBar

| 17:36

問題文, SRM 173

インストール作業の進捗具合を示すプログレス・バーを表示する。

240.19/250

class ProgressBar {
public:
    string showProgress(vector <int> taskTimes, int tasksCompleted) {
        int total = accumulate(taskTimes.begin(), taskTimes.end(), 0);
        int completed = accumulate(taskTimes.begin(), 
                taskTimes.begin()+tasksCompleted, 0);
        double percent = static_cast<double>(completed) / total;
        string progress(20, '.');
        for (int i = 0; i < floor(percent*20); i++)
            progress[i] = '#';
        return progress;
    }
};

Poetry

| 13:47

問題文, SRM 170

与えられた詩が、どのように音韻を踏んでいるのかを調べる。

377.34/1000

class Poetry {
public:
    string rhymeScheme(vector <string> poem) {
        char label = 'a';
        vector<vector<string> > substrings(poem.size());
        string result(poem.size(), ' ');
        for (int i = 0; i < poem.size(); i++) {
            if (poem[i].length() == 0) continue;
            string s = tolowerString(poem[i]);
            istringstream iss(s);
            string last(""), tmp;
            while (iss >> tmp) last = tmp;
            if (last == "")
                continue;
            const int len = last.length();
            bool isPreVowel = false;
            for (int j = len-1; j >= 0; j--) {
                const char c = last[j];
                bool isVowel = (j!=len-1 && j!=0 && c=='y')
                    || c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
                if (isPreVowel && !isVowel) 
                    substrings[i].push_back(last.substr(j+1));
                isPreVowel = isVowel;
            }
            if (isPreVowel) substrings[i].push_back(last);
            for (int j = 0; j <= substrings[i].size(); j++) {
                if (j == substrings[i].size()) {
                    result[i] = label;
                    label++;
                    if (label > 'z') label = 'A';
                    break;
                }
                for (int k = 0; k < i; k++)  {
                    if (find(substrings[k].begin(), substrings[k].end(), substrings[i][j])
                            != substrings[k].end()) {
                        result[i] = result[k];
                        break;
                    }
                }
                if (result[i] != ' ') break;
            }

        }
        return result;
    }
private:
    string tolowerString(string s) {
        for (int i = 0; i < s.length(); i++)
            s[i] = tolower(s[i]);
        return s;
    }
};

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

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/