Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1577-51dfe638
この記事にトラックバックする(FC2ブログユーザー)

SRM480 DIV1 EASY/DIV2 MEDIUM - InternetSecurity (この記事を編集する[管理者用])

Source

TopCoder SRM480 DIV1 EASY (250pt)
TopCoder SRM480 DIV2 MEDIUM (500pt)
Problem Statement
SRM480 DIV1 自分の参加記録

問題概要

50個以下のwebサイトのアドレスと含まれてる単語のリストが与えられる.
また,NGワードのリストが与えられる.
与えられた閾値の数より以上の数のNGワードを含まれてるwebサイトは危険サイトとして,また危険サイトに含まれてる単語はすべてNGリストに追加される.
危険なwebサイトのリストを求める問題.

解法

実装問題.実装するだけだけど,サンプルが弱く,ちゃんと気をつけて実装しなければいけない.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class InternetSecurity {
public:
vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold) {
  int i,j,k,n,st;
  vector <string> res;
  int chk[1000];
  set<string> dame;
  string str;
  vector< vector<string> > word;

  rep(i, dangerous.size()) dame.insert(dangerous[i]);

  n=address.size();
  rep(i,n) chk[i]=0;

  rep(i,n){
    st=0;
    vector<string> add;
    str = "";
    for(;;){
      if(st==keyword[i].size() || keyword[i][st]==' '){
        add.push_back(str); str = "";
      }
      if(st==keyword[i].size()) break;
      if(keyword[i][st]!=' ') str += keyword[i][st];
      st++;
    }
    word.push_back(add);
  }

  for(;;){
    int fg=0;
    rep(i,n) if(!chk[i]){
      k=0;
      rep(j,word[i].size()) if( dame.count(word[i][j]) ) k++;
      if(k >= threshold){
        chk[i]=1;
        rep(j,word[i].size()) dame.insert(word[i][j]);
        fg=1;
      }
    }
    if(!fg) break;
  }

  rep(i,n) if(chk[i]) res.push_back(address[i]);

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1577-51dfe638
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。