問題
①大文字のアルファベットの配列が与えられる。
②任意の要素をスワップことができるが、スワップ回数の上限も与えられる。
③このとき、同じアルファベットが隣り合う最大の数を求める。
解き方
最初に全探索をイメージすると、各アルファベットごとに最大の数を求めることがイメージできます。
次に、スワップについての全探索のイメージを浮かべるのが難しかったです。
スワップの操作について全探索を考えるのではなく、
スワップ後の「最終形をイメージ」すると、
隣り合うアルファベットのサブセット最大数は
一番左の要素番号ごとに一意に求められることがわかります。
さらに、並べるのに使うアルファベットも「連続している」ということがわかれば、
最初に使うアルファベットの数も最も左のものから一つずつインクリメントしていくことで、全探索することができます。
コード
class ColorfulChocolates {
public: int maximumSpread(string chocolates, int maxSwaps) {
int ans=0,n=chocolates.size();
for(char C='A';C<='Z';C++){
FORE(i,0,n){
FORE(j,0,n){
int left=i,cur=j;
int swaps=0;
while(left<n && cur<n){
while(cur<n && chocolates[cur]!=C)cur++;
if(cur>=n)break;
int tmp=abs(cur-left);
if(swaps+tmp>maxSwaps)break;
swaps+=tmp;
left++;
cur++;
}
ans=max(ans,left-i);
}
}
}
return ans;
}
};
public: int maximumSpread(string chocolates, int maxSwaps) {
int ans=0,n=chocolates.size();
for(char C='A';C<='Z';C++){
FORE(i,0,n){
FORE(j,0,n){
int left=i,cur=j;
int swaps=0;
while(left<n && cur<n){
while(cur<n && chocolates[cur]!=C)cur++;
if(cur>=n)break;
int tmp=abs(cur-left);
if(swaps+tmp>maxSwaps)break;
swaps+=tmp;
left++;
cur++;
}
ans=max(ans,left-i);
}
}
}
return ans;
}
};