SRM448 div1 easy

再帰

  double expected(vector  cards) {
    char rank[6] = "AKQJT";
    rem = 52;
    //Init
    for(int i = 2; i < 10; i++) {
      table[i] = 4;
    }
    table[10] = 4*4; table[11] = 4;

    int sum = 0;
    for(int i = 0, len = cards.size(); i < len; i++) {
      char ch = cards[i][0]; int num = 0;
      if(ch == rank[0]) {
	num = 11;
      } else {
	for(int i = 1; i < 5; i++) {
	  if(ch == rank[i]) num = 10;
	}
	if(ch >= '2' && ch <= '9') {
	  num = ch - '0';
	}
      }
      sum += num;
      table[num]--;
      rem--;
    }
    return go(0, sum, 1.0);	
  }
};

double TheBlackJackDivOne::go(int cnt, int sum, double prob) {
  double ans = 0;

  if(sum >= 21) return prob*cnt;
  for(int i = 2; i <= 11; i++) {
    int newsum = i + sum;
    int cardnum = table[i];
    table[i]--; rem--;
    ans += go(cnt+1, newsum, prob*(cardnum*1.0/(rem+1) ) );
    table[i]++; rem++;
  }
  return ans;
}

dpと連動させることによっても実現できそう．