SRM572 Div1 Medium(500) EllysBulls

EllysBulls

半分全列挙。左半分の数字を全て生成して、guessごとに何個正解しているかを数える。次に、右半分を全て生成して、何個正解しているかを数え、足し合わせるとbullsになるような左半分があるかを調べる。mapの引数にvectorはとても重いというイメージがあったけど、そんなことはないのか……。

#include <string>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

class EllysBulls{public:
string getNumber( vector <string> guesses, vector <int> bulls )
{
    int n = (int)guesses.size();
    int m = (int)guesses[0].size();
    int ml = m/2;
    int mr = (m+1)/2;

    //  左半分を列挙し、正解の個数をキーとしてmapに格納する
    map<vector<int>,string> M;
    for ( int i=0; i<(int)pow(10.,ml); i++ )
    {
        char wl[16];
        sprintf( wl, "%0*d", ml, i );

        vector<int> Bl(n);
        for ( int j=0; j<n; j++ )
        {
            int c = 0;
            for ( int k=0; k<ml; k++ )
                if ( guesses[j][k]==wl[k] )
                    c++;
            Bl[j] = c;
        }

        M[Bl] = M.count(Bl)==0 ? wl : "Ambiguity";
    }

    //  右半分を列挙し、対応する左半分が存在するか調べる
    string ans;
    for ( int i=0; i<(int)pow(10.,mr); i++ )
    {
        char w[16];
        sprintf( w, "%0*d", mr, i );

        vector<int> Br(n);
        for ( int j=0; j<n; j++ )
        {
            int c = 0;
            for ( int k=0; k<mr; k++ )
                if ( guesses[j][ml+k]==w[k] )
                    c++;
            Br[j] = c;
        }

        vector<int> Bl(n);
        for ( int i=0; i<n; i++ )
            Bl[i] = bulls[i]-Br[i];

        if ( M.count(Bl)>0 )
        {
            if ( M[Bl]!="Ambiguity" && ans=="" )
                ans = M[Bl]+w;
            else
                ans = "Ambiguity";
        }
    }

    return ans!="" ? ans : "Liar";
}};