Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-24

StripePainter

| 13:03

問題文, SRM 150

最低何回ペンキを塗りつける必要があるか。DP+メモ化で解ける問題。

224.12/500

class StripePainter {
public:
    int minStrokes(string stripes) {
        const int size = stripes.size();
        memo = vector<vector<vector<int> > >(size,vector<vector<int> >(size+1,vector<int>(128,-1)));
        return go(stripes, 0, size, '?');
    }
private:
    vector<vector<vector<int> > > memo;
    int go(const string& stripes, 
            const int left, const int size, const char color) {
        if (size <= 0) return 0;
        if (memo[left][size][color] >= 0) return memo[left][size][color];
        int best = INT_MAX;
        if (stripes[left] == color) {
            best = go(stripes, left+1, size-1, color);
        } else {
            for (int i = 1; i <= size; i++) 
                best = min(best, 1
                        + go(stripes,left+1,i-1,stripes[left])
                        + go(stripes,left+i,size-i,color));
        }
        memo[left][size][color] = best;
        return best;
    }
};

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

HillHike

| 14:33

問題文

採りえる山の形の数を求める。問題は理解できたが、解法が全然思いつかなかった。

470.68/1000

class HillHike {
    public:
        long long numPaths(int distance, int maxHeight, vector <int> landmarks) {
            long long memory[2][52][51];
            memset(memory, 0, sizeof(memory));
            memory[0][0][0] = 1;
            landmarks.push_back(-1);
            for (int i = 1; i < distance; i++) {
                long long cache[2][52][51];
                memset(cache, 0, sizeof(memory));
                for (int h = 1; h <= maxHeight; h++) {
                    int mh = (h == maxHeight) ? 1 : 0;
                    for (int j = 0; j < landmarks.size(); j++)
                        for (int d = -1; d <= 1; d++) {
                            int lm = (h == landmarks[j]) ? j+1 : j;
                            cache[mh][h][lm] += memory[0][h+d][j];
                            cache[ 1][h][lm] += memory[1][h+d][j];
                        }
                }
                memcpy(memory, cache, sizeof(memory));
            }
            return memory[1][1][landmarks.size()-1];
        }
};

TrevonTrevon2011/07/22 14:31What a joy to find such clear thikinng. Thanks for posting!

jknzrlrnojknzrlrno2011/07/22 23:00AjjYSE <a href="http://ixlymfbzzugw.com/">ixlymfbzzugw</a>

yvzbbdyvzbbd2011/07/23 22:15ye8QTD , [url=http://uxgtugxylomn.com/]uxgtugxylomn[/url], [link=http://kqcpcalkwsod.com/]kqcpcalkwsod[/link], http://qqpqjszskcfr.com/

zjjbnlaeddzzjjbnlaeddz2011/07/24 22:34EkvlNg <a href="http://ziovfuvshgpt.com/">ziovfuvshgpt</a>

kredwoskredwos2011/07/26 01:32v3mrNH , [url=http://zmgqozacpuiq.com/]zmgqozacpuiq[/url], [link=http://vvwzqzdemmen.com/]vvwzqzdemmen[/link], http://hmhrbmsipkkf.com/

CamiloCamilo2012/11/16 17:32It's wondeurfl to have you on our side, haha!

amnquhsamnquhs2012/11/16 22:35OOQfVh <a href="http://wykjstupxxmy.com/">wykjstupxxmy</a>

etogorusetogorus2019/05/05 21:25http://mewkid.net/buy-amoxicillin/ - Amoxicillin 500mg Capsules <a href="http://mewkid.net/buy-amoxicillin/">Online Amoxicillin</a> wgo.cyyp.topcoder.g.hatena.ne.jp.sog.xx http://mewkid.net/buy-amoxicillin/

2009-08-13

Lottery

| 15:42

問題文

DIV1の問題を解き始めることにした。この問題から、1問につき1エントリを書く。過去のエントリも近いうちに1問1エントリに変える。

数字を使ったギャンブルで、勝率が高い順に並べる。組み合わせの問題で、解けそうと思いコードを書き始めたが、結局わからなくなり、Editorialを見た。

181.27 / 500 - 01:53:07

bool compValidTicketsNum(const pair<string,long long>& a,
        const pair<string,long long>& b) {
    if (a.second < b.second) {
        return true;
    } else if (a.second > b.second) {
        return false;
    } else {
        return a.first < b.first;
    }
}

class Lottery {
    public:
        vector <string> sortByOdds(vector <string> rules) {
            const int size = rules.size();
            vector <string> result(size);
            if (size == 0) return result;
            vector <pair<string,long long> > name(size);
            vector<int> choices(size), blanks(size);
            for (int i = 0; i < size; i++) {
                int p = find(rules[i].begin(),rules[i].end(),':') - rules[i].begin();
                name[i].first = rules[i].substr(0, p);
                istringstream iss(rules[i].substr(p+1));
                int choices, blanks;
                string sorted, unique;
                iss >> choices >> blanks >> sorted >> unique;
                if (sorted == "F" && unique == "F") {
                    name[i].second = power(choices, blanks);
                } else if (sorted == "T" && unique == "F") {
                    name[i].second = combination(choices+blanks-1, blanks);
                } else if (sorted == "F" && unique == "T") {
                    name[i].second = combination(choices, blanks) * factorial(blanks);
                } else if (sorted == "T" && unique == "T") {
                    name[i].second = combination(choices, blanks);
                }
            }
            stable_sort(name.begin(), name.end(), compValidTicketsNum);
            for (int i = 0; i < size; i++)
                result[i] = name[i].first;
            return result;
        }
    private:
        long long power(const long long x, long long y) {
            long long ret = 1;
            while (y-- > 0) ret *= x;
            return ret;
        }
        long long factorial(long long x) {
            long long ret = 1;
            while (x > 0) {
                ret *= x;
                x--;
            }
            return ret;
        }
        long long combination(long long x, long long y) {
            long long ret = 1;
            for (int i = 0; i < y; i++) {
                ret *= x;
                x--;
            }
            while (y > 1) {
                ret /= y;
                y--;
            }
            return ret;
        }
};

2009-08-10

NumberGuesser

| 19:34

問題文

数字を推測。自力で解けなかった。総当たりで解いたが、数学的な解法もある。

190.54/500 - 01:06:07 (cheated)

class NumberGuesser {
    public:
        int guess(string leftOver) {
            int candidate = 0;
            for (int d = 1; d <= 9; d++) {
                int found = 0;
                for (int i = 0; i < 4; i++) {
                    ostringstream oss;
                    oss << leftOver.substr(0,i) << d << leftOver.substr(i);
                    int z;
                    istringstream(oss.str()) >> z;
                    for (int x = 1; x+z <= 9998; x++) {
                        int y = x + z;
                        if (isDigitMatch(x, y)) {
                            candidate = d;
                            found++;
                            break;
                        }
                    }
                }
                if (found == 4) return d;
            }
            return candidate;
        }
    private:
        bool isDigitMatch(int x, int y) {
            vector<int> ndigits(10, 0);
            while (x > 0) {
                if (x%10 != 0) ndigits[x%10]++;
                x /= 10;
            }
            while (y > 0) {
                if (y%10 != 0) ndigits[y%10]--;
                y /= 10;
            }
            for (int i = 0; i < ndigits.size(); i++) {
                if (ndigits[i] != 0)
                    return false;
            }
            return true;
        }
};

2009-08-07

ShortPalindromes

| 12:58

問題文

与えられた文字列から作られる、最も短くて、辞書順で最初にくる回文を作れ、という問題。再帰+メモ化によって時間内に解ける問題。わからなくてEditorialを見た。思いつきそうでつかない解法だな。こういう問題は慣れれば解けるようになると思った。

572.72/1150 - 00:38:45 (cheated)

class ShortPalindromes {
    public:
        string shortest(string base) {
            memo.clear();
            return go(base);
        }
    private:
        map<string,string> memo;
        string go(const string& s) {
            if (memo.find(s) != memo.end()) 
                return memo[s];
            if (isPalindrome(s)) 
                return s;
            const int len = s.length();
            string ret;
            if (s[0] == s[len-1]) {
                ret = string(1,s[0]) + go(s.substr(1,len-2)) + string(1,s[0]);
            } else {
                ret = minStr(string(1,s[0]) + go(s.substr(1,len-1)) + string(1,s[0]),
                        string(1,s[len-1]) + go(s.substr(0,len-1)) + string(1,s[len-1]));
            }
            memo[s] = ret;
            return ret;
        }
        bool isPalindrome(const string& s) {
            const int len = s.length();
            for (int i = 0; i < len/2; i++)
                if (s[i] != s[len-i-1])
                    return false;
            return true;
        }
        string minStr(const string& a, const string& b) {
            if (a.length() < b.length()) {
                return a;
            } else if (a.length() > b.length()) {
                return b;
            } else if (a < b) {
                return a;
            } else {
                return b;
            }
        }
};

2009-07-26

Gems

| 19:52

ボード中の2つの隣接する宝石を入れ替えた時に、3つ以上宝石が並ぶかどうか。自力で解けると思って実装したが、重複して数えてしまってうまくいかず、結局Editorialを見た。

class Gems {
public:
    int numMoves(vector <string> board) {
        int moves = 0;
        const static int d[DIR_KINDS][2] = {
            { 0, 1}, { 1, 0}, { 0,-1}, {-1, 0} };
        const int h=board.size(), w=board[0].length();
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                const char gem = board[y][x];
                for (int i = 0; i < DIR_KINDS/2; i++) {
                    const int dy = y + d[i][0];
                    const int dx = x + d[i][1];
                    if (!isInRage(dy,dx,h,w)) continue;
                    if (gem == board[dy][dx]) continue;
                    if (isAligned(gem,dy,dx,i,board,h,w) ||
                      isAligned(board[dy][dx],y,x,i+DIR_KINDS/2,board,h,w)) {
                        moves++;
                    }
                }
            }
        }
        return moves;
    }
private:
    const static int DIR_KINDS = 4;
    bool isInRage(const int y, const int x, const int h, const int w) {
        return 0<=y&&y<h && 0<=x&&x<w;
    }
    bool isAligned(const char gem, const int dy, const int dx, const int dir,
              const vector<string>& board, const int h, const int w) {
        const static int CHECK_KINDS = 4;
        const static int check[DIR_KINDS][CHECK_KINDS][2][2] = {
            { {{-1, 0},{ 1, 0}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0, 2},{ 0, 1}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}} },
            { {{-1, 0},{ 1, 0}}, {{ 2, 0},{ 1, 0}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}} },
            { {{ 0,-1},{ 0, 1}}, {{ 0,-2},{ 0,-1}}, {{-2, 0},{-1, 0}}, {{ 0, 2},{ 0, 1}} } };
        for (int j = 0; j < CHECK_KINDS; j++) {
            for (int k = 0; k < 2; k++) {
                const int cy = dy + check[dir][j][k][0];
                const int cx = dx + check[dir][j][k][1];
                if (!isInRage(cy,cx,h,w)) break;
                if (gem != board[cy][cx]) break;
                if (k == 2-1) return true;
            }
        }
        return false;
    }
};

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

WordParts

| 09:31

問題文

問題文が短く、問題の意味は理解できたが、解法が思いつかず、Editorialを見た。メモ化か。慣れない。

class WordParts {
public:
    int partCount(string original, string compound) {
        const int ori_len = original.length();
        len = compound.length();
        dict.clear();
        dict.insert(original);
        for (int i = 1; i < ori_len; i++) {
            dict.insert(original.substr(0,ori_len-i));
            dict.insert(original.substr(ori_len-i));
        }
        memo = vector<int>(len, -1);
        const int parts = minParts(compound, 0);
        if (parts >= INFTY) return -1;
        else return parts;
    }
private:
    int len;
    set<string> dict;
    vector<int> memo;
    const static int INFTY = INT_MAX/2;
    int minParts(const string& compound, const int pos) {
        if (pos == len) return 0;
        if (memo[pos] != -1) return memo[pos];
        memo[pos] = INFTY;
        for (set<string>::const_iterator w = dict.begin();
                    w != dict.end(); w++) {
            const int w_len = (*w).length();
            if (*w == compound.substr(pos, w_len))
                memo[pos] = min(memo[pos], 1+minParts(compound,pos+w_len));
        }
        return memo[pos];
    }
};

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

InterestingDigits

| 18:51

問題文

251.51->499.03

説明が面倒なので無し。

class InterestingDigits {
public:
    vector <int> digits(int base) {
        vector <int> result;
        for (int d = 2; d < base; d++) {
            if (isInterestingDigit(base, d))
                result.push_back(d);
        }
        return result;
    }
private:
    bool isInterestingDigit(const int base, const int d) {
        return base%d == 1;
    }
};

MissyMissy2011/07/22 16:09Now I know who the brainy one is, I'll keep looknig for your posts.

zrwuybrcsgozrwuybrcsgo2011/07/23 22:08xDBJGa , [url=http://ngbsklytunqc.com/]ngbsklytunqc[/url], [link=http://olpwwtwjhupr.com/]olpwwtwjhupr[/link], http://vfyjnrgeopbs.com/

qbqmjjqbqmjj2011/07/24 21:58F1VCcA <a href="http://iyopswirddsc.com/">iyopswirddsc</a>