Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-21

CityLink

| 20:12

問題文, SRM 170

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

全ての都市をつなげるにはどのぐらいの期間が必要か。Floyd-Warshall法の変形法で解ける。

398.94/550

class CityLink {
public:
    int timeTaken(vector <int> x, vector <int> y) {
        const int n = x.size();
        vector<vector<int> > D(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (x[i] == x[j])
                    D[i][j] = (abs(y[i]-y[j])+1) / 2;
                else if (y[i] == y[j])
                    D[i][j] = (abs(x[i]-x[j])+1) / 2;
                else
                    D[i][j] = max(abs(x[i]-x[j]), abs(y[i]-y[j]));
            }

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    D[i][j] = min(D[i][j], max(D[i][k], D[k][j]));

        int result = 0;
        for (int i = 0; i < n; i++)
            result = max(result, *max_element(D[i].begin(), D[i].end()));
        return result;
    }
};

HonneyHonney2011/08/30 15:59A miunte saved is a minute earned, and this saved hours!

wyemhhwwyemhhw2011/09/01 00:575HxeEE <a href="http://ybnebnwcovjs.com/">ybnebnwcovjs</a>

nibmiiinibmiii2011/09/01 16:45G2F1Yz , [url=http://sawuiwwztonv.com/]sawuiwwztonv[/url], [link=http://afgrzejquery.com/]afgrzejquery[/link], http://qcxtuwjadjsa.com/

yadxlbnejvmyadxlbnejvm2011/09/03 17:37kFklXm <a href="http://cmwvbpywnvnz.com/">cmwvbpywnvnz</a>

miiugpaimiiugpai2011/09/04 02:04wqBYC6 , [url=http://tmkxgkbnxbnf.com/]tmkxgkbnxbnf[/url], [link=http://zmtmrmbpaobv.com/]zmtmrmbpaobv[/link], http://ulmzbcooroqn.com/

IdelIdel2013/02/17 07:36I can aalredy tell that's gonna be super helpful.

2009-08-20

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

RecurrenceRelation

| 12:51

問題文

与えられた漸化式のN番目の値を求める。システムテストで1回落とされた。

298.29/500 - 00:20:58

class RecurrenceRelation {
    public:
        int moduloTen(vector <int> coefficients, vector <int> initial, int N) {
            const int k = coefficients.size();
            for (int i = 0; i < k; i++) 
                initial[i] = myMod(initial[i]);
            cout << endl;
            for (int i = k; i <= N; i++) {
                int x = 0;
                for (int j = i-1; j >= i-k; j--) 
                    x += coefficients[k-(i-j)] * initial[j];
                cout << i << " " << x << endl;
                x = myMod(x);
                initial.push_back(x);
            }
            return initial[N];
        }
    private:
        int myMod(const int x) {
            if (x >= 0) return x % 10;
            else return (10 - ((-x)%10)) % 10;
        }
};

LevelUp

| 19:23

問題文

次のレベルアップまでに必要な経験値を求める。

244.32/250 - 00:04:07

class LevelUp {
    public:
        int toNextLevel(vector <int> expNeeded, int received) {
            for (int i = 0; i < expNeeded.size(); i++)
                if (received < expNeeded[i])
                    return expNeeded[i] - received;
            return 0;
        }
};

JusticeJustice2011/07/09 15:18Created the greatest artclies, you have.

dhumgkuquyrdhumgkuquyr2011/07/10 00:44RBBBkV <a href="http://hjbppmyhkpug.com/">hjbppmyhkpug</a>

oipwdeoipwde2011/07/11 20:03vO7rh7 <a href="http://ampmjgepjkgf.com/">ampmjgepjkgf</a>