SRM551 Div1 Easy(250), Div2 Medium(500) ColorfulChocolates

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