Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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

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

BritishCoins

| 19:21

問題文

コインの数。

242.83/250 - 00:05:05

class BritishCoins {
    public:
        vector <int> coins(int pence) {
            const static int SHILLING = 12;
            const static int POUND = 20 * SHILLING;
            vector <int> result(3);
            result[0] = pence / POUND;
            pence %= POUND;
            result[1] = pence / SHILLING;
            pence %= SHILLING;
            result[2] = pence;
            return result;
        }
};