naoya_t@topcoder

SRM396 Div1 Easy: DNAString

過去問, 練習 | 04:46 |

よくわからないままコーディングしてたらTest Case全て通ったので投稿。システムテストも１発。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;
  }
};