SRM 572 DIV1 Easy - NewArenaPassword

SRM 572 DIV1 Easy - NewArenaPassword

8:09

問題


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;

}

};

Share this

Google Facebook Twitter More

Related Posts