Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2010 Qual. 1A EASY - DNAMatching (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Qualification Round 1A EASY (250pt)
(Qual. 1でサーバー不調でノーゲームとなった回,問題文はArenaから見れます, ホームページには無い)

問題概要

ATCGのみからなる文字列が50個以下与えられる.
文字列を反転させて,AとT,CとGをそれぞれ入れ替えて一致する文字列は一緒とみなす.
異なる文字列が何個あるか求める問題.
元々,全く同じ文字列は入力されない.

解法

実際に反転させて,一致するもの,つまり重複の個数を調べてそれだけ減らす,など.

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 DNAMatching {
public:
int getMaxSize(vector <string> dna) {
  int i,j;
  set<string> s;

  string a,b;
  rep(i,dna.size()){
    a=b=dna[i]; reverse(b.begin(),b.end());
    rep(j,b.size()){
           if(b[j]=='A') b[j]='T';
      else if(b[j]=='T') b[j]='A';
      else if(b[j]=='C') b[j]='G';
      else if(b[j]=='G') b[j]='C';
    }
    if(a<b) s.insert(a); else s.insert(b);
  }

  return s.size();
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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