■

ややこしすぎて、なんで通ったのか分からない。

#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;
int K,gN;
int E[40];
int G[16][16];
double C[40][40];
double cache[16][1<<16];

void init()
{
	for(int i=0;i<40;i++)
		for(int j=0;j<40;j++)
			if(i<j)
				C[i][j]=0;
			else if(j==0)
				C[i][j]=1;
			else
				C[i][j]=C[i-1][j]+C[i-1][j-1];
	for(int i=0;i<16;i++)
		for(int j=0;j<1<<16;j++)
			cache[i][j]=-2.0;
}

void makeG(vector<string> input)
{
	for(int i=0;i<16;i++)
		for(int j=0;j<16;j++)
			G[i][j]=0;
	gN=1;
	set<int> masaoFriends;
	for(int i=0;i<input.size();i++)
	{
		int a;
		stringstream ss(input[i]);
		vector<int> v;
		while(ss>>a)
			v.push_back(a);
		if(i==0)
		{
			masaoFriends.insert(1);
			for(int j=0;j<v.size();j++)
				masaoFriends.insert(v[j]);
			for(int j=0;j<v.size();j++)
			{
				int p=distance(masaoFriends.begin(),masaoFriends.find(i+1));
				int q=distance(masaoFriends.begin(),masaoFriends.find(v[j]));
				G[p][q]=G[q][p]=1;
			}
		}
		else if(masaoFriends.find(i+1)!=masaoFriends.end())
		{
			gN++;
			for(int j=0;j<v.size();j++)
				if(masaoFriends.find(v[j])!=masaoFriends.end())
				{
					int p=distance(masaoFriends.begin(),masaoFriends.find(i+1));
					int q=distance(masaoFriends.begin(),masaoFriends.find(v[j]));
					G[p][q]=G[p][q]=1;
				}
		}
		E[distance(masaoFriends.begin(),masaoFriends.find(i+1))]=v.size();
	}

	/*printf("masaoFriends =");
	for(set<int>::iterator it=masaoFriends.begin();it!=masaoFriends.end();it++)
		printf("%d ",*it);
	printf("\n");
	for(int i=0;i<gN;i++)
	{
		for(int j=0;j<gN;j++)
			printf("%d ",G[i][j]);
		printf("\n");
	}*/
}

double rec(int pos,int left)
{
	//printf("rec(%d,%d)\n",pos,left);
	double &r=cache[pos][left];
	if(-1.0<r)
		;
	else if(left==0)
		r=1.0;
	else
	{
		r=0.0;
		vector<double> prob;
		for(int i=0;i<gN;i++)
			if(G[pos][i] && ((1<<i)&left))
				prob.push_back(rec(i,left^(1<<i)));
		sort(prob.begin(),prob.end());
		reverse(prob.begin(),prob.end());
		/*printf("prob=");
		for(int i=0;i<prob.size();i++)
			printf("%lf ",prob[i]);
		printf("\n");*/
		if(K<E[pos])
		{
			double p=1.0;
			for(int i=0;i<prob.size();i++)
			{
				r+=(p-C[E[pos]-i-1][K]/C[E[pos]][K])*prob[i];
				p=C[E[pos]-i-1][K]/C[E[pos]][K];
			}
		}
		else if(0<prob.size())
			r+=prob[0];
	}
	return r;
}

class FriendTour 
{
	public:
		double tourProbability(vector<string> input,int _K) 
		{
			K=_K;
			makeG(input);
			init();

			return rec(0,(1<<gN)-1-1);
		}

};