SRM 572 DIV1 Easy - NewArenaPassword （復習○）
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12386&rd=15492
古いパスワードから新しいパスワードを作りたいが、できるだけ変更したくない。
また、パスワードの最初のＫ文字と最後のＫ文字は一致していないといけない。
古いパスワードが与えられた時、最小の変更文字数を求める。
解き方
正確にシミュレーションしてあげれば解ける問題。
i文字目について、Ｎ-K文字を足した場所とリンクしていることがわかると、
最初からN-Kずつ足していった値に対して、最小のリンク関数を求めてあげればよい。
また、最初からＫもしくはＮ－Ｋまでの操作でよいことがわかる。
コード
class NewArenaPassword {
public: int minChange(string oldPassword, int K) {
int cost=0,n=oldPassword.size();
for(int i=0;i<n&&i<n-K;i++){
int count[26]={},num=0;
for(int j=i;j<n;j+=n-K){
count[oldPassword[j]-'a']++;
num++;
}
cost+=num-*max_element(count,count+26);
}
return cost;
}
};
public: int minChange(string oldPassword, int K) {
int cost=0,n=oldPassword.size();
for(int i=0;i<n&&i<n-K;i++){
int count[26]={},num=0;
for(int j=i;j<n;j+=n-K){
count[oldPassword[j]-'a']++;
num++;
}
cost+=num-*max_element(count,count+26);
}
return cost;
}
};
