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;
    }
};

2009-07-24

PaternityTest

| 08:29

問題文

子が母と父両方から半分ずつ遺伝情報を受けついでいるかを調べる。初めは母と子が半分一致するパターンを全パターン作るという、最悪の場合で計算量が2^20となる実装を行って提出するも、timeoutされた。それで結局、Editorialを見た。両方にマッチしなかったら除外してよいという事実には気付けなかった。

class PaternityTest {
public:
    vector <int> possibleFathers(string child, string mother, vector <string> men) {
        vector <int> result;
        for (int i = 0; i < men.size(); i++) {
            if (isFather(child, mother, men[i]))
                result.push_back(i);
        }
        return result;
    }
private:
    bool isFather(const string& child, const string& mother,
                  const string& man) {
        const int len = child.length();
        int matches = 0;
        for (int i = 0; i < len; i++) {
            if (child[i] == man[i]) matches++;
            else if (child[i] != mother[i]) return false;
        }
        return matches >= len/2;
    }
};

BenfordsLaw

| 05:41

問題文

Benford's Law により計算される、期待される取引金額の先頭数字の出現数より、実際の出現数が基準よりずれているかどうかを調べる。

class BenfordsLaw {
public:
    int questionableDigit(vector <int> transactions, int threshold) {
        const int numTrans = transactions.size();
        double expected[10];
        for (int d = 1; d <= 9; d++) {
            expected[d] = log10(1.0l+1.0l/d) * numTrans;
        }
        vector<int> count(10, 0);
        for (int i = 0; i < numTrans; i++) {
            int first = transactions[i];
            while (first >= 10) first /= 10;
            count[first]++;
        }
        for (int d = 1; d <= 9; d++) {
            if (count[d] > threshold*expected[d] 
                  || count[d] < expected[d]/threshold)
                return d;
        }
        return -1;
    }
};

Quipu

| 05:41

問題文

SRM 445 は参加登録はしたが、眠かったので不参加。

特殊な形式の十進数の数を、整数形式に変換。

class Quipu {
public:
    int readKnots(string knots) {
        int result = 0;
        for (int i = 1; i < knots.length()-1; i++) {
            if (knots[i] == 'X') result++;
            else result *= 10;
        }
        return result;
    }
};