Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-12-26

SRM396 Div1 Easy: DNAString

| 04:46 | SRM396 Div1 Easy: DNAString - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM396 Div1 Easy: DNAString - naoya_t@topcoder SRM396 Div1 Easy: DNAString - naoya_t@topcoder のブックマークコメント

よくわからないままコーディングしてたらTest Case全て通ったので投稿。システムテストも1発。12分前後。

maxPeriod以内の周期pを全て試してみて、各位置 mod pについて出現頻度が最大の文字に置き換える場合の変更字数を数えているだけ。

class DNAString {
public:
  int acgt(int ch) {
    switch(ch) {
    case 'A': return 0;
    case 'C': return 1;
    case 'G': return 2;
    case 'T': return 3;
    }
  }
  int minChanges(int maxPeriod, vector<string> dna) {//42937
    string dnac = ""; tr(dna,it) dnac += *it; int n=dnac.length();
    int minch = INT_MAX;
    for(int p=1;p<=maxPeriod;p++) {
      vector<vector<int> > st(p);
      int changes=0;
      tr(st,it) { it->resize(4); fill(all(*it),0);}
      rep(i,n) st[i%p][acgt(dnac[i])]++;
      rep(i,p) {
        int maxc=0,totc=0;
        rep(j,4) {
          totc+=st[i][j]; if(st[i][j]>maxc) maxc=st[i][j];
        }
        changes+=totc-maxc;
      }
      if (minch>changes)minch=changes;
    }
    return minch;
  }
};