SRM384 div1 medium

問題要約
ーーーーーーーーーーーー
n人の人が円形に並んでいて、
時計回りの順にボールを任意の他の人に向かって投げる。
ボールがあたった人は円から離脱し、
番号iの人が投げたボールが当たる確率はprobably[i]である。
この時円形に並んでいる人が１人になるまでのボールが投げられる回数の最小の期待値を求めよ。
ーーーーーーーーーーーー
まず、制限の
"Each element of probability will be between 10 and 100, inclusive."
に解法のヒントを見つけた。
10%からということは10000回くらいボールを投げ続けたら
失敗する確率は最悪でも　0.9^10000≒0　に収束する。
それならこの問題は rec(誰が残っている(2^6),誰の番(6),何回目(10000))でメモ化再帰。
つまずいたのはボールを投げるときに誰に向かって投げるかということ。
様々なケースが考えられるので投げられる全員に投げてみて一番期待値が小さいものを選ぶと良い。

#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <climits>
#include <cfloat>

using namespace std;
double cache[(1<<6)+1][6+1][10000+10];

class SchoolTrip 
{
	public:

		int n;
		vector<double> p;

		int popCount(int _mask)
		{
			int r=0;
			for(int i=0;i<28;i++)
				if(_mask & (1<<i))
					r++;
			return r;
		}

		double rec(int left,int turn,int time)
		{
			double &r=cache[left][turn][time];
			if(-1.0<r)
				;
			else if(time==10000 || popCount(left)==1)
				r=0.0;
			else
			{
				r=1.0;
				int ln=popCount(left)-1;
				double minThrow=FLT_MAX;
				for(int hit=turn+1;;hit++)
				{
					hit%=n;
					if(hit==turn)
						break;
					int sleft=left^(1<<hit);
					for(int nTurn=turn+1;;nTurn++)
					{
						nTurn%=n;
						if(sleft&(1<<nTurn))
						{
							minThrow=min(minThrow,p[turn]*rec(sleft,nTurn,time+1));
							break;
						}
					}
				}
				r+=minThrow;
				for(int nTurn=turn+1;;nTurn++)
				{
					nTurn%=n;
					if(left & (1<<nTurn))
					{
						r+=(1.0-p[turn])*rec(left,nTurn,time+1);
						break;
					}
				}
			}
			return r;
		}

		double duration(vector <int> probability) 
		{
			n=probability.size();
			p.clear();
			for(int i=0;i<n;i++)
				p.push_back(probability[i]/100.0);
			for(int i=0;i<(1<<6);i++)
				for(int j=0;j<6;j++)
					for(int k=0;k<10000;k++)
						cache[i][j][k]=-2.0;
			return rec((1<<n)-1,0,0);
		}
};