Hatena::Grouptopcoder

cou929のTopCoder日記

2010-09-02

SRM 480 div1 (リハビリ)

00:16

とても久々なのでとりあえず250をやってみる.

Easy - InternetSecurity

ngワードの辞書が与えられる. ある文章に閾値以上のngワードが含まれていると, その文章は危険と認定される. またその際, その危険な文章の全単語がngワードとして辞書に追加される. これを危険な文章が見つからなくなるまで繰り返し, 検出した危険な文章のセットを返す.

アルゴリズムとしては毎回ふつうに探索しているだけなのですが, なぜかシステムテストが通らない. 赤い人のコードをみてみても大筋では同じことをやっているようにしか見えないので, どこかでしょうもないバグを埋め込んでいるか, なにか問題を勘違いしているのかもしれません.

フラグの立て忘れでした. これは情けない.

class InternetSecurity {
public:
  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold) {
    int i, k;
    int n = address.size();
    vector <string> ret;
    vector <vector <string> > keywords;
    vector <bool> is_danger(n, false);
    vector <int> result_indexes;
    set <string> dangerous_set;

    for (i=0; i<n; i++)
      keywords.push_back(split(keyword[i], " "));

    for (i=0; i<dangerous.size(); i++)
      dangerous_set.insert(dangerous[i]);

    while (1) {
      bool exist = false;

      for (i=0; i<n; i++)
        if (!is_danger[i]) {
          int counter = 0;

          for (set <string>::iterator j=dangerous_set.begin(); j!=dangerous_set.end(); j++)
            if (find(keywords[i].begin(), keywords[i].end(), *j) != keywords[i].end())
              counter++;

          if (counter >= threshold) {
            exist = true;  // このフラグを立て忘れていた
            result_indexes.push_back(i);
            is_danger[i] = true;
            for (k=0; k<keywords[i].size(); k++)
              dangerous_set.insert(keywords[i][k]);
          }
        }

      if (!exist)
        break;
    }

    sort(result_indexes.begin(), result_indexes.end());
    for (i=0; i<result_indexes.size(); i++)
      ret.push_back(address[result_indexes[i]]);

    return ret;
  }
};

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/cou929/20100902