SRM512 Div2 Hard(1024) DoubleRoshambo

DoubleRoshambo

2点となる手の組み合わせを選ばないほうが点数が高くなるということはないので、点数が高くなる手の組み合わせを貪欲に取っていけばよい。

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

int game( string a, string e )
{
    bool w[2];
    for ( int i=0; i<2; i++ )
        w[i] = a[i]=='R' && e[i]=='S' ||
               a[i]=='P' && e[i]=='R' ||
               a[i]=='S' && e[i]=='P';

    if ( w[0] && w[1] )
        return 2;
    if ( a[0]==e[0] && w[1] )
        return 1;
    return 0;
}

class DoubleRoshambo{public:
int maxScore( vector <string> A, vector <string> E )
{
    int n = (int)A.size();

    vector<bool> Af(n), Ef(n);

    int ans = 0;

    for ( int p=2; p>0; p-- )
    {
        for ( int i=0; i<n; i++ )
        if ( !Af[i] )
            for ( int j=0; j<n; j++ )
            if ( !Ef[j] )
                if ( game(A[i],E[j])==p )
                {
                    ans += p;
                    Af[i] = Ef[j] = true;
                    break;
                }
    }
    
    return ans;
}};