Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-29

QuipuReader

| 14:05

問題文, SRM 155

特殊な数記法で表わされた数を処理。解くのに時間かかり過ぎ。

191.33/450

class QuipuReader {
public:
    vector <int> readKnots(vector <string> knots) {
        const int sz = knots.size();
        const int len = knots[0].length();
        vector<vector<int> > num(sz), start(sz), last(sz);
        for (int i = 0; i < sz; i++) {
            int j = 0;
            while (j < len) {
                while (j < len && knots[i][j] != 'X') j++;
                if (j == len && knots[i][len-1] != 'X') break;
                start[i].push_back(j);
                j++;
                while (j < len && knots[i][j] == 'X') j++;
                num[i].push_back(j-start[i].back());
                last[i].push_back(j-1);
            }
        }

        vector <int> result(sz,0), idx(sz,0);
        int i = 0;
        while (i < len) {
            int s = INT_MAX, l=INT_MAX;
            for (int j = 0; j < sz; j++) {
                if (idx[j] < start[j].size() && start[j][idx[j]] < s) {
                    s = start[j][idx[j]];
                    l = last[j][idx[j]];
                }
            }
            if (s == INT_MAX) break;
            for (int j = 0; j < sz; j++) {
                result[j] *= 10;
                if (idx[j] < start[j].size() &&
                        ((s<=start[j][idx[j]] && last[j][idx[j]]<=l) ||
                        (start[j][idx[j]]<=s && l<=last[j][idx[j]]))) {
                    result[j] += num[j][idx[j]];
                    idx[j]++;
                } 
            }
            i = l + 1;
        }
        return result;
    }
};