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; } };