SRM549 Div1 Medium(600) MagicalHats

MagicalHats

魔法使いはコインの位置を自由に決められるので、プレイヤーがn枚のコインを獲得できるならば、小さい方から順にn枚になる。プレイヤーが帽子の位置を指定し、魔法使いがその帽子の中にコインがあるかどうかを決める、というゲームだと考える。条件が満たせなくなるようなら魔法使いの負け。

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

int pow(int a,int b){int c=1;while(b--)c*=a;return c;}
struct POS{int x,y;};

vector<string> board;
vector<int> coins;
int numGuesses;
vector<POS> H;      //  帽子の位置
int n;              //  帽子の数
vector<int> T;      //  帽子の状態　-1:開けていない　0:コイン無し　1:コインあり
vector<int> memo;   //  メモ化探索用

int BT1( int d );
bool BT2( int d );

class MagicalHats{public:
int findMaximumReward( vector <string> board, vector <int> coins, int numGuesses )
{
    ::board = board;
    ::coins = coins;
    ::numGuesses = numGuesses;
    H.clear();
    for ( int y=0; y<(int)board.size(); y++ )
    for ( int x=0; x<(int)board[y].size(); x++ )
        if ( board[y][x]=='H' )
            H.push_back(POS()),
            H.back().x = x,
            H.back().y = y;
    n = (int)H.size();
    T = vector<int>(n,-1);
    memo = vector<int>(pow(3,n),-1);

    int r = BT1(0);
    if ( r<=numGuesses )
    {
        sort(coins.begin(),coins.end());
        return accumulate(coins.begin(),coins.begin()+r,0);
    }
    else
    {
        return -1;
    }
}};

//  現在の帽子の状態からプレイヤの得られる最大コイン数を返す
int BT1( int d )
{
    int t = 0;
    for ( int i=0; i<n; i++ )
        t = t*3 + T[i]+1;
    if ( memo[t]>=0 )
        return memo[t];

    if ( d>=numGuesses )
    {
        int c = (int)count(T.begin(),T.end(),1);
        return memo[t] = BT2(d) ? c : numGuesses+1;
    }

    int ans = 0;
    for ( int i=0; i<n; i++ )
    if ( T[i]==-1 )
    {
        T[i] = 0;
        int a1 = BT1(d+1);
        T[i] = 1;
        int a2 = BT1(d+1);
        T[i] = -1;
        ans = max( ans, min(a1,a2) );
    }

    return memo[t] = ans;
}

//  現在の帽子の状態から、条件を満たすようなコインの配置ができるかを返す
bool BT2( int d )
{
    int t = 0;
    for ( int i=0; i<n; i++ )
        t = t*3 + T[i]+1;
    if ( memo[t]>=0 )
        return memo[t]!=0;

    if ( d>=n )
    {
        int c = 0;
        int w = (int)board[0].size();
        int h = (int)board.size();
        vector<int> hc(w);
        vector<int> vc(h);
        for ( int i=0; i<n; i++ )
        {
            hc[H[i].x] += T[i]==1 ? 2 : 1;
            vc[H[i].y] += T[i]==1 ? 2 : 1;
            c += T[i]==1 ? 1 : 0;
        }
        bool f = c==(int)coins.size();
        for ( int x=0; x<w; x++ )
            if ( hc[x]%2!=0 )
                f = false;
        for ( int y=0; y<h; y++ )
            if ( vc[y]%2!=0 )
                f = false;
        memo[t] = f;
        return f;
    }

    int i = 0;
    while ( T[i]!=-1 )
        i++;
    
    T[i] = 0;
    bool f1 = BT2(d+1);
    T[i] = 1;
    bool f2 = BT2(d+1);
    T[i] = -1;

    memo[t] = f1 || f2;
    return f1 || f2;
}