問題
http://community.topcoder.com/stat?c=problem_statement&pm=12137&rd=15173
解き方
各アルファベットごとに最大の連続数を考え、最大のものを求める。
あるアルファベットについて最大の連続数を考えるとき、
どれか１つのアルファベットの位置は変わらないことを利用する。
よって、すべての位置を起点にして同じアルファベット結合させ、
そのスワップ回数がmaxswap数以下のときの連続数をそれぞれとっていけばよい。
コード
class ColorfulChocolates {
public: int maximumSpread(string chocolates, int maxSwaps) {
int n=chocolates.size();
int ret=0;
for(char ch='A';ch<='Z';ch++){
vector<int> vx;
FORE(i,0,n)if(ch==chocolates[i])vx.push_back(i);
FORE(i,0,vx.size()){
vector<int> tmp;
FORE(j,0,vx.size())tmp.push_back(abs(vx[i]-vx[j]-(i-j)));
sort(all(tmp));
int sum=0,num=0;
FORE(j,0,vx.size()){
if(sum+tmp[j]<=maxSwaps){
num++;
sum+=tmp[j];
}
}
ret=max(ret,num);
}
}
return ret;
}
};
public: int maximumSpread(string chocolates, int maxSwaps) {
int n=chocolates.size();
int ret=0;
for(char ch='A';ch<='Z';ch++){
vector<int> vx;
FORE(i,0,n)if(ch==chocolates[i])vx.push_back(i);
FORE(i,0,vx.size()){
vector<int> tmp;
FORE(j,0,vx.size())tmp.push_back(abs(vx[i]-vx[j]-(i-j)));
sort(all(tmp));
int sum=0,num=0;
FORE(j,0,vx.size()){
if(sum+tmp[j]<=maxSwaps){
num++;
sum+=tmp[j];
}
}
ret=max(ret,num);
}
}
return ret;
}
};