SRM551 Div1 Easy - ColorfulChocolates

問題

長さnの文字列sが与えられる
sの隣り合う2文字をswapするという操作を最大k回まで行い、sで同じ文字が連続している部分の長さの最大値を最大化せよ

解法

s[i]を真ん中にして、s[i]と同じ文字をなるべく多く隣まで持ってくることを考えればいい
便宜上、s[i]に隣接するs[i]と同じ文字たちをグループと呼びます
(例えばs=BAABAならs[1]とs[2]は同じグループ)
s[i]より右にある文字s[j]をs[i]と同じグループにするには、(区間(i,j)に存在するs[i]とは異なる文字の個数)回だけswapが必要
s[i]より左にある文字も同様
限られたswap回数でグループの最大化するには、左右は問わず、この値が小さいものから順に引っ張ってくるのが明らかに最善

実装

答えを0で初期化してて1回死んだ

class ColorfulChocolates {
public:
	int maximumSpread(string s, int k) {
		int n = s.size(), res = 1;
		rep(i,n) {
			vector<int> d;
			int c = 0;
			reps(j,i+1,n) {
				if (s[j]==s[i]) d.push_back(c);
				else c++;
			}
			c = 0;
			for (int j=i-1; j>=0; j--) {
				if (s[j]==s[i]) d.push_back(c);
				else c++;
			}
			sort(all(d));
			rep(j,d.size()) {
				if (j) d[j] += d[j-1];
				if (d[j]<=k) chmax(res,j+1);
			}
		}
		return res;
	}
};