TopCoder SRM 396 Div1 Easy DNAString

問題

長さlの文字列sが、p周期であるとは、
すべての0≦i＜l-pなるiについて、s[i+p]=s[i]を満たすことを言う。

A,C,G,Tからなる文字列が与えられる。
この文字列をmaxPeriod以下の周期を持つように書き換えたい。
最低でいくつの文字を書き換えなければならないか、求めよ。

制約条件

文字列の長さ≦2500
maxPeriod≦文字列の長さ

方針

O(長さ^2)で解ければよい。
maxPeriod以下の全てのperiodについて、その周期にするために必要な書き換え回数を求め、
その中の最小値を答える。

元の文字列から周期pをもつ文字列に書き換えるには、
周期でi番目の文字をそれぞれ集め、一番多い文字にその他の文字を全部書き換えてやるのが最善。

ソースコード

class DNAString {
  public:
  int minChanges(int maxPeriod, vector <string> dna) {
    int num[256];
    num['A']=0; num['C']=1; num['G']=2; num['T']=3;
    
    string str=accumulate(all(dna),string());
    int n=str.size(),ans=inf;
    for(int p=1;p<=maxPeriod;p++){
      int tmp=0;
      rep(i,p){
        int cnt[4]={};
        for(int j=i;j<n;j+=p)cnt[num[str[j]]]++;
        sort(cnt,cnt+4);
        tmp+=cnt[0]+cnt[1]+cnt[2];
      }
      ans=min(ans,tmp);
    }
    return ans;
  }
};