SRM572 Div1 Easy - NewArenaPassword
問題
topcoderのパスワードをsにしていた
ある日「パスワードの最初のk文字と最後のk文字は一致していないといけない」という新ルールが出来た
新ルールを守るようなパスワードに変更するとき、sから変更する文字数の最小値を求めよ
1 <= |s| <= 50
1 <= k <= |s|
解法
sの長さをnとすると、条件は
「i文字目とi+n-k文字目が一致する (0<=i
class NewArenaPassword { public: int minChange(string s, int k) { int n = s.size(), res = 0; rep(i,k) { int a[26] = {}, sz = 1; for (int j=i; j<n; j+=n-k, sz++) a[s[j]-'a']++; res += sz - *max_element(a,a+26); } return res; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12386&rd=15492