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-07-23

SuperRot

| 05:33

問題文

暗号化された文字列を復号。

class SuperRot {
public:
    string decoder(string message) {
        setToTable('A', 'M', 'N');
        setToTable('N', 'Z', 'A');
        setToTable('a', 'm', 'n');
        setToTable('n', 'z', 'a');
        setToTable('0', '4', '5');
        setToTable('5', '9', '0');
        for (int i = 0; i < message.length(); i++) {
            if (isalnum(message[i]))
                message[i] = table[message[i]];
        }
        return message;
    }
private:
    char table[256];
    void setToTable(const char l, const char h, const char s) {
        for (int i = l; i <= h; i++) table[i] = s+(i-l);
    }
};

2009-05-03

CCipher

| 18:28

問題文

245.71->249.80 / 250

文字列をシフトする。Aの次はZ。

class CCipher {
public:
    string decode(string cipherText, int shift) {
        for (int i = 0; i < cipherText.length(); i++) {
            cipherText[i] -= shift;
            if (cipherText[i] < 'A')
                cipherText[i] += 26;
        }
        return cipherText;
    }
};

ljgwenjuqljgwenjuq2011/02/28 11:40tFpXps <a href="http://cnqanfqzjpsf.com/">cnqanfqzjpsf</a>, [url=http://ecxrxcimgfag.com/]ecxrxcimgfag[/url], [link=http://buchmiybjeag.com/]buchmiybjeag[/link], http://qsgnzwnfmeyn.com/

NalerneNalerne2012/07/09 23:11That's a sharp way of tihnikng about it.

sgpszksgpszk2012/07/10 15:50uVoDFm <a href="http://zcpgsuoedxnr.com/">zcpgsuoedxnr</a>

nkfxqknkfxqk2012/07/10 21:46Oe4QRT , [url=http://mkqciqvhhsmq.com/]mkqciqvhhsmq[/url], [link=http://ljixvhzrjcar.com/]ljixvhzrjcar[/link], http://hxxtbrctakiz.com/

zqmlzhnitzuzqmlzhnitzu2012/07/12 12:05jEMaC7 <a href="http://cxlnhmsvwfmv.com/">cxlnhmsvwfmv</a>

xavvxxpsxavvxxps2012/07/12 17:37XLQaD8 , [url=http://xjwqjiilrtmr.com/]xjwqjiilrtmr[/url], [link=http://wibefrqdjint.com/]wibefrqdjint[/link], http://kgupbzwtdngh.com/

2009-04-04

BinaryCode

| 15:56

問題文

221.33->540.49 / 550

最後の数が 0 かどうかを確認する必要がある。

class BinaryCode {
public:
    vector <string> decode(string message) {
        const int len = message.length();
        vector <string> result;
        for (int i = 0; i <= 1; i++) {
            vector<int> p(len+2, 0);
            p[1] = i;
            for (int j = 0; ; j++) {
                int q = (message[j]-'0')-p[j]-p[j+1];
                if (q == 0 || q == 1) {
                    p[j+2] = q;
                    if (j == len-1) {
                        if (q == 0) {
                            result.push_back(string(len,'0'));
                            for (int k = 0; k < len; k++)
                                result.back()[k] += p[k+1];
                        } else
                            result.push_back("NONE");
                        break;
                    }
                } else {
                    result.push_back("NONE");
                    break;
                }
            }
        }
        return result;
    }
};