SRM563 Div1 Easy(250) FoxAndHandle - kusano

Hの接頭辞を決めたとき条件を満たすかどうかは、SからHの文字をできるだけ左から選んでいき、各文字について選んだ個数と残りの部分の個数を合わせて、総数の半分に達するかどうかを調べればわかる。これを使って、Hを先頭から順に決めていく。

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool check( string S, string H )
{
    int n = (int)S.size();
    vector<bool> F(n);
    int p = 0;

    //  できるだけ左からHの文字を選んでいく
    for ( int i=0; i<(int)H.size(); i++ )
    {
        while ( p<n && S[p]!=H[i] )
            p++;
        if ( p>=n )
            return false;
        F[p++] = true;
    }

    //  文字aについて、
    //  これまでに選んだaの個数がaの総数の半分超過ならNG
    //  これまでに選んだaの個数とp以降のaの個数の和が総数の半分未満でもNG
    for ( char a='a'; a<='z'; a++ )
    {
        int c = (int)count(S.begin(),S.end(),a);
        int x = 0;
        for ( int i=0; i<p; i++ )
            if ( S[i]==a && F[i] )
                x++;
        int y = 0;
        for ( int i=p; i<n; i++ )
            if ( S[i]==a )
                y++;
        if ( x>c/2 || x+y<c/2 )
            return false;
    }

    return true;
}

class FoxAndHandle{public:
string lexSmallestName( string S )
{
    string H;

    for ( int i=0; i<(int)S.size()/2; i++ )
    {
        char a='a';
        while ( !check(S,H+a) )
            a++;
        H += a;
    }

    return H;
}};