読者です 読者をやめる 読者になる 読者になる

SRM Div1 511 Medium FiveHundredEleven

ゲーム木探索知った勢いでコーディングしてみた。

したこと

①現在のビットと使った個数を持っておけば、何を使ったかを復元できる(一意に定まらないことがあっても問題ない)

②そのために[何番目まで使ったか][ビット状態][使った個数]で、使ったアイテムを記録する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" ;
	}
};