SRM511 Div1 Medium(500), Div2 Hard(1000) FiveHundredEleven

FiveHundredEleven

現在のターン数とメモリの値でどちらが勝つかが決まる。なぜならば、メモリの寝ているビットのうち少なくとも１個が立っているカードは必ず残っているし、メモリの寝ているビットが全て寝ているカードは同一視できるから。ターン数とメモリの値で勝敗を覚えておいて、メモ化探索。

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

int N;
vector<int> card;
vector<vector<int> > memo;

int BT( int t, int m )
{
    if ( t==N )  return -1;
    if ( memo[t][m] != 0 )  return memo[t][m];

    int ans = -1;
    int c = 0;

    for ( int i=0; i<N; i++ )
    if ( ~m & card[i] )
    {
        if ( (m|card[i]) != 511 )
            ans = max( ans, -BT(t+1,m|card[i]) );
        c++;
    }
    if ( c < N-t )
        ans = max( ans, -BT(t+1,m) );

    return memo[t][m] = ans;
}

class FiveHundredEleven{public:
string theWinner( vector <int> cards )
{
    N = (int)cards.size();
    card = cards;
    memo = vector<vector<int> >( N, vector<int>(511) );

    return BT(0,0)>0 ? "Fox Ciel" : "Toastman";
}};