Hatena::Grouptopcoder

yaottiの日記

2010-03-11

SRM 156 DIV2続き

| 16:24

hard

TopCoder Statistics - Problem Statement

greedyに一致させていくと最適にならないケース(問題のsample5)にどう対処すればいいのかわからない…

例えば

original: ABABCDC

compound: ABABABC

だと,greedyにやるとABAB+AB+Cで3になるけど,うまくやればAB+ABABCで2になる.

後者の方が良いと知る方法はあるのかな.全部試すしかない気がする…

class WordParts {
public:
    int partCount(string original, string compound) {
        int result = 0;
        int idx = 0;
        int len = compound.size();
        while (idx < len) {
            int i = 0;
            for (; i < (int)original.size(); i++) {
                if (original[i] != compound[idx+i]) break;
            }
            int j = 0;
            int maxj = 0;
            for (int idxj = 1; idxj < (int)compound.size()-idx+1; idxj++) {
                string s = compound.substr(idx,idxj); // 残っているcompoundから切り取っていく
                // 文字列が見付からないならそこで終了
                if (original.find(s, 1) == string::npos) break;
                int pos = 1;    // 検索開始位置,最後尾の物を得る
                while (original.find(s, pos) != string::npos) {
                    j = original.find(s, pos);
                    pos++;
                }
                // 末尾に一致しなければ,失敗
                if (j + idxj != (int)original.size()) {
                    continue;
                }
                maxj = max(idxj, maxj);
            }
            if (i == 0 && maxj == 0) return -1;
            result++;
            idx += max(i,maxj);
        }
        return result;
    }
}

editorial

17:04

Login - TopCoder Wiki

なにこれ超やさしい…いままで解いた問題のやつざっと見直してみよう.

SRM 156 DIV2再び

| 23:14

hard

Editorial読んでもう一度挑戦.というかそのままコードにしただけ.

memoize!

class WordParts {
public:
    string orig;
    string cmp;
    vector <string> dict;
    int memo[100];
    int minParts(int pos) {
        if (memo[pos] != -1) return memo[pos];
        if (pos == (int)cmp.size()) return 0;
        int ret = 10000;
        LP(dict) {
            if (cmp.substr(pos, dict[i].size()) == dict[i]) { // prefix
                ret = min(ret, 1+minParts(pos+dict[i].size()));
            }
        }
        memo[pos] = ret;
        return ret;
    }
    void setUpDict() {
        // prefix
        dict.clear();
        for (int i = 1; i < (int)orig.size(); i++) {
            dict.push_back(orig.substr(0, i));
        }
        for (int i = 1; i < (int)orig.size(); i++) {
            dict.push_back(orig.substr(i));
        }
        dict.push_back(orig);
    }
    int partCount(string original, string compound) {
        cmp = compound;
        orig = original;
        setUpDict();
        memset(memo, -1, sizeof(memo));
        int ret = minParts(0);
        return  ret < 1000 ? ret : -1;
    }
}