Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-19

| 14:30

問題文, http://www.topcoder.com/stat?c=round_overview&rd=4550:titel=SRM 149]

Dictionaryに含まれる単語だけで、messageを作れるかどうか。DPで解ける問題だが、見落としが発生しやすい問題。4回もシステムテストで落とされた。

150.0/500

class MessageMess {
    public:
        string restore(vector <string> dictionary, string message) {
            const int len = message.size();
            vector<string> memo(len, "");
            vector<bool> isAmbiguous(len, false);
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < dictionary.size(); j++) {
                    const int wlen = dictionary[j].length();
                    if (i+1 < wlen) continue;
                    if (i-wlen >= 0 && memo[i-wlen] == "") continue;
                    if (message.substr(i-wlen+1,wlen) != dictionary[j]) continue;
                    if (memo[i] != "") isAmbiguous[i] = true;
                    if (i-wlen >= 0) {
                        if (toNospace(memo[i-wlen]) != message.substr(0,i-wlen+1)) continue;
                        if (isAmbiguous[i-wlen]) isAmbiguous[i] = true;
                        memo[i] = memo[i-wlen] + " " + dictionary[j];
                    } else {
                        memo[i] = dictionary[j];
                    }
                }
            }
            if (memo[len-1] == "") return "IMPOSSIBLE!";
            else if (isAmbiguous[len-1]) return "AMBIGUOUS!";
            else return memo[len-1];
        }
    private:
        string toNospace(const string& s) {
            string nospace;
            const int slen = s.length();
            int idx=0, pre=idx;
            while ((idx = s.find(" ", pre)) != string::npos) {
                nospace += s.substr(pre, idx-pre);
                pre = idx+1;
            }
            nospace += s.substr(pre, slen-pre);
            return nospace;
        }
};

RenaRena2011/07/22 11:40Articles like this really grease the shftas of knowledge.

mtosqkksxfnmtosqkksxfn2011/07/22 18:19nGge95 <a href="http://htbsbsjhateo.com/">htbsbsjhateo</a>

vouvotvouvot2011/07/24 22:10AbhEFB <a href="http://udtjnaqmvoon.com/">udtjnaqmvoon</a>

lraetvllraetvl2011/07/25 02:03Ueilew , [url=http://ofkchvqjbqph.com/]ofkchvqjbqph[/url], [link=http://mhzhqovckhxx.com/]mhzhqovckhxx[/link], http://kgxfqnawhoqk.com/

2009-05-05

Pricing

| 07:49

問題文

652.34->985.81 / 1000

最大利益を求める問題。全てのケースを試せばよい。

class Pricing {
public:
    int maxSales(vector <int> price) {
        int maxSales = 0;
        int size = price.size();
        sort(price.begin(), price.end());
        for (int i = 0; i < size; i++) {
            for (int j = i; j < size; j++) {
                for (int k = j; k < size; k++) {
                    for (int l = k; l < size; l++) {
                        int sales = 0;
                        for (int m = 0; m < size; m++) {
                            if (price[m] >= price[l]) {
                                sales += price[l];
                            } else if (price[m] >= price[k]) {
                                sales += price[k];
                            } else if (price[m] >= price[j]) {
                                sales += price[j];
                            } else if (price[m] >= price[i]) {
                                sales += price[i];
                            }
                        }
                        maxSales = max(maxSales, sales);
                    }
                }
            }
        }
        return maxSales;
    }
};

BigBurger

| 18:40

問題文

451.11->498.43 / 500

ハンバーガ店で、一番待たなければならない客の待ち時間を求めよ、という問題。

class BigBurger {
public:
    int maxWait(vector <int> arrival, vector <int> service) {
        int maxWaitTime = 0;
        int time = arrival[0] + service[0];
        for (int i = 1; i < arrival.size(); i++) {
            time = max(time, arrival[i]);
            maxWaitTime = max(maxWaitTime, time-arrival[i]);
            time += service[i];
        }
        return maxWaitTime;
    }
};

FormatAmt

| 18:41

問題文

75.0->246.97->248.61 / 250

DIV2 の easy にしては難しい問題。右側から作って、最後にリバースする。

class FormatAmt {
public:
    string amount(int dollars, int cents) {
        ostringstream os, os2;
        os << cents%10 << cents/10 << ".";
        os2 << dollars;
        string dStr(os2.str());
        for (int i = dStr.length(); i >= 1; i -= 3) {
            if (i <= 3) {
                string t(dStr.substr(0, i));
                reverse(t.begin(), t.end());
                os << t;
            } else {
                string t(dStr.substr(i-3, 3));
                reverse(t.begin(), t.end());
                os << t << ",";
            }
        }
        os << "$";
        string result(os.str());
        reverse(result.begin(), result.end());
        return result;
    }
};

EthanaelEthanael2011/07/22 23:14Ppl like you get all the brains. I just get to say thanks for he asewnr.

nwuzwsnwuzws2011/07/23 17:24hyvJcw <a href="http://snkjtvdtsudq.com/">snkjtvdtsudq</a>

tumzkdcbtumzkdcb2011/07/23 22:087LifN6 , [url=http://qcpqtmgyqoyx.com/]qcpqtmgyqoyx[/url], [link=http://aubgoopyvcjc.com/]aubgoopyvcjc[/link], http://wsyiiftrtiox.com/

jijaysgrhiqjijaysgrhiq2011/07/25 21:508QsglD <a href="http://gpbtdukulkdq.com/">gpbtdukulkdq</a>