Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

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