SRM551 Div1 Easy(250), Div2 Medium(500) ColorfulChocolates
spredを最大にするとき、その色のチョコのうち1個は動かさないことが可能。動かさないチョコを決めて、そのチョコの周りに同色のチョコを何個集められるかを調べる。
あるチョコを持ってくるとき、交換回数は、そのチョコとの間にある違う色のチョコの個数。より内側にあるチョコは交換回数が少ないので、持ってくるチョコは交換回数の少ないものを貪欲に選べば良い。
class ColorfulChocolates{public: int maximumSpread( string chocolates, int maxSwaps ) { int n = (int)chocolates.size(); int ans = 0; for ( int c=0; c<n; c++ ) { vector<int> D(1,0); int t = 0; for ( int i=c-1; i>=0; i-- ) if ( chocolates[i]==chocolates[c] ) D.push_back(t); else t++; t = 0; for ( int i=c+1; i<n; i++ ) if ( chocolates[i]==chocolates[c] ) D.push_back(t); else t++; sort(D.begin(),D.end()); for ( int i=0; i<=(int)D.size(); i++ ) if ( accumulate(D.begin(),D.begin()+i,0) <= maxSwaps ) ans = max( ans, i ); } return ans; }};