問題
http://community.topcoder.com/stat?c=problem_statement&pm=10615&rd=13902
解き方
探索箇所が少ないので全探索可能。
各カードについて既に使ったかどうかの情報が必要なので、
その情報を更新しつつDFSを用いればよい。
コード
int s[]={0,11,2,3,4,5,6,7,8,9,10,10,10,10};
int c[14];
class TheBlackJackDivOne {
public:
double rec(int cur){
if(cur>=21)return 0;
int sum=0;
double ret=0.0;
FORE(i,0,14)sum+=c[i];
FORE(i,0,14)if(c[i]!=0){
c[i]--;
ret+=(1+rec(s[i]+cur))*(c[i]+1)/sum;
c[i]++;
}
return ret;
}
double expected(vector<string> cards) {
int score=0;
FORE(i,0,14)c[i]=4;
c[0]=0;
FORE(i,0,cards.size()){
if(cards[i][0]=='A')c[1]--,score+=11;
else if(cards[i][0]=='T')c[10]--,score+=10;
else if(cards[i][0]=='J')c[11]--,score+=10;
else if(cards[i][0]=='Q')c[12]--,score+=10;
else if(cards[i][0]=='K')c[13]--,score+=10;
else c[cards[i][0]-'0']--,score+=cards[i][0]-'0';
}
return rec(score);
}
};
int c[14];
class TheBlackJackDivOne {
public:
double rec(int cur){
if(cur>=21)return 0;
int sum=0;
double ret=0.0;
FORE(i,0,14)sum+=c[i];
FORE(i,0,14)if(c[i]!=0){
c[i]--;
ret+=(1+rec(s[i]+cur))*(c[i]+1)/sum;
c[i]++;
}
return ret;
}
double expected(vector<string> cards) {
int score=0;
FORE(i,0,14)c[i]=4;
c[0]=0;
FORE(i,0,cards.size()){
if(cards[i][0]=='A')c[1]--,score+=11;
else if(cards[i][0]=='T')c[10]--,score+=10;
else if(cards[i][0]=='J')c[11]--,score+=10;
else if(cards[i][0]=='Q')c[12]--,score+=10;
else if(cards[i][0]=='K')c[13]--,score+=10;
else c[cards[i][0]-'0']--,score+=cards[i][0]-'0';
}
return rec(score);
}
};