SRM516 Div2 Hard(1000)

NetworkXMessageRecovery

先頭から順に元のメッセージを決定していく。いずれかのmessagesの中で2文字目以降に表れる文字は使用できないので、それ以外で辞書順最小の文字を選択する。

たとえば、Example 0の場合、

{acd,bce}　aとbを比較してaの方が小さいのでaを選択。　a

{cd,bce}　cは2個目の文字列の2文字目に表れるので選べない。bを選択。　ab

{cd,ce}　cを選択。　abc

{d,e}　dの方が小さいのでdを選択。　abcd

{,e}　eを選択。　abcde

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

class NetworkXMessageRecovery{public:
string recover( vector <string> messages )
{
    int n = (int)messages.size();

    set<char> S;
    for ( int i=0; i<n; i++ )
        S.insert( messages[i].begin(), messages[i].end() );

    string ans;
    while ( !S.empty() )
    {
        string C;
        for ( set<char>::iterator c=S.begin(); c!=S.end(); c++ )
        {
            bool f = true;
            for ( int i=0; i<n; i++ )
                for ( int j=1; j<(int)messages[i].length(); j++ )
                    if ( *c==messages[i][j] )
                        f = false;
            if ( f )
                C += *c;
        }
        sort( C.begin(), C.end() );

        S.erase(C[0]);
        for ( int i=0; i<n; i++ )
            if ( messages[i].length() > 0  &&
                 messages[i][0] == C[0] )
                messages[i].erase(messages[i].begin());
        ans += C[0];
    }

    return ans;
}};