TopCoder SRM 734 Div1 Medium CardCounter

うーん。
https://community.topcoder.com/stat?c=problem_statement&pm=14021

問題

トランプのブラックジャックを考える。
プレイヤーは初期に配られた２枚のカードを知っている。
ディーラーは２枚のカードを持っており、１枚はプレイヤーに知られているが１枚は不明である。

元々デッキのうち、既知の３枚のカードを除くとどんなカードがあるかプレイヤーは知っている。
プレイヤーがディーラーがデッキからカードを引くと、残されたカードのうち１枚が等確率で引くものとする。
プレイヤーが最適手を取ったとき、勝率を求めよ。

解法

デッキのカード枚数が高々16枚なのでbitmaskを用いてDFSする。
まずプレイヤーの手札と残されたカードでDFSし、そのつどもう１枚引くかもう引かないかを考えて勝率の上がる方を選べばよい。

double memo1[22][2][1<<16];
vector<double> memo2[22][2][1<<16];


class CardCounter {
	public:
	int deal;
	vector<int> D;
	vector<double> get_dealer(int sum,int ace,int mask) {
		vector<double> R(22,0);
		if(sum>21) {
			R[0]=1;
		}
		else if(sum+10*ace>=17 && sum+10*ace<=21) {
			R[sum+10*ace]=1;
		}
		else if(sum>=17 && sum<=21) {
			R[sum]=1;
		}
		else {
			if(memo2[sum][ace][mask].size()) return memo2[sum][ace][mask];
			int num=__builtin_popcount(mask);
			int i,j;
			FOR(i,D.size()) if(mask&(1<<i)) {
				auto R2=get_dealer(sum+D[i],ace|(D[i]==1),mask^(1<<i));
				FOR(j,22) R[j]+=R2[j]*1.0/num;
			}
			memo2[sum][ace][mask] = R;
		}
		int i;
		return R;
	}
	
	double hoge(int sum,int ace,int mask) {
		double end=0;
		if(sum>21) return 0;
		if(memo1[sum][ace][mask]<0) {
			vector<double> op=get_dealer(deal,deal==1,mask);
			int cur=sum;
			if(ace&&sum+10<=21) cur+=10;
			int i;
			FOR(i,cur) end+=op[i];
			
			double take=0;
			FOR(i,D.size()) if(mask&(1<<i)) take += hoge(sum+D[i],ace | (D[i]==1),mask^(1<<i));
			memo1[sum][ace][mask] = max(end,take/__builtin_popcount(mask));
		}

		return memo1[sum][ace][mask];
		
		
	}
	
	double winningChance(vector <int> deck, int dealer, vector <int> player) {
		deal = dealer;
		D.clear();
		int i,j,k;
		FOR(i,deck.size()) while(deck[i]--) D.push_back(i+1);
		
		FOR(i,22) FOR(j,2) FOR(k,1<<16) memo1[i][j][k]=-1,memo2[i][j][k].clear();
		
		return hoge(player[0]+player[1],(player[0]==1)|(player[1]==1),(1<<D.size())-1);
		
	}
}

まとめ

面倒なだけであまり面白味もないし、まぁ400ptでしょうがないかな。