ゲーム木探索知った勢いでコーディングしてみた。
したこと
①現在のビットと使った個数を持っておけば、何を使ったかを復元できる(一意に定まらないことがあっても問題ない)
②そのために[何番目まで使ったか][ビット状態][使った個数]で、使ったアイテムを記録するDPして、復元表を作っておく。
③その上でさらにメモ化ゲーム木探索する。
#include <iostream> #include <algorithm> #include <vector> using namespace std; #define rep(i,n) for(int i = 0 ; i < n ; i++) int n; vector<int> item; long long dp[51][512][51]; char memo[51][512]; int f(int used,int bit){ if(~memo[used][bit]) return memo[used][bit]; long long c = dp[n][bit][used]; rep(i,n){ if(!(c >> i & 1)){ if((bit|item[i]) == 511) continue; if( !f(used+1,bit | item[i]) ) return memo[used][bit] = true; } } return memo[used][bit] = false; } class FiveHundredEleven { public: string theWinner(vector <int> cards) { n = cards.size(); rep(k,51)rep(i,512)rep(j,51) dp[k][i][j] = -1; dp[0][0][0] = 0; for(int x = 0 ; x < n ; x++){ for(int i = 0 ; i < 512 ; i++){ for(int j = 0 ; j <= x ; j++){ if(dp[x][i][j] == -1) continue; dp[x+1][i][j] = dp[x][i][j]; dp[x+1][i|cards[x]][j+1] = (1ll<<x) | dp[x][i][j]; } } } memset(memo,-1,sizeof(memo)); item = cards; return f(0,0) ? "Fox Ciel" : "Toastman" ; } };