SRM 249 DIV1 Easy - TableSeating (復習×)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=4616&rd=7224
・テーブルが複数存在する。
・各グループ人数ごとに来店する確率が与えられる。
来店する回数に制限はない。
・グループがきたときに、空いているテーブルにランダムに案内する。
ただし、グループが複数人のときは連続したテーブルに案内しなければならない。
各テーブルには１人席に着く。
このとき、テーブルに着席する人数の期待値を求める。
解き方
全探索では解けないので、ｄｐを利用する。
ｄｐをどう設計するかがポイントで、現在の席の空き状態を引数とすることで解くことができる。
同じグループ人数については何度選択してもよいので、その空き状態に対して全てのグループ数とその座り方について探索する。
こちらのコードを参考にさせていただきました。
http://community.topcoder.com/stat?c=problem_solution&rd=7224&pm=4616&cr=7459326
コード
class TableSeating {
public:
double getExpected(int num, vector<int> probs) {
double dp[(1<<12)]={0};
bool can[15];
FORE(i,1,(1<<num)){
FORE(j,0,probs.size()){
int s=j+1;
double p=probs[j]/100.0;
FORE(k,0,15)can[k]=false;
FORE(k,0,15){
int uu=(1<<(k+s))-(1<<k);
if(k+s<=num && ((i&uu)==uu) )can[k]=true;
}
int cnt=0;
FORE(k,0,15)cnt+=can[k];
p/=(double)cnt;
FORE(k,0,15){
if(!can[k])continue;
int uu=(1<<(k+s))-(1<<k);
dp[i]+=p*(dp[i-uu]+s);
}
}
}
return dp[(1<<num)-1];
}
};
public:
double getExpected(int num, vector<int> probs) {
double dp[(1<<12)]={0};
bool can[15];
FORE(i,1,(1<<num)){
FORE(j,0,probs.size()){
int s=j+1;
double p=probs[j]/100.0;
FORE(k,0,15)can[k]=false;
FORE(k,0,15){
int uu=(1<<(k+s))-(1<<k);
if(k+s<=num && ((i&uu)==uu) )can[k]=true;
}
int cnt=0;
FORE(k,0,15)cnt+=can[k];
p/=(double)cnt;
FORE(k,0,15){
if(!can[k])continue;
int uu=(1<<(k+s))-(1<<k);
dp[i]+=p*(dp[i-uu]+s);
}
}
}
return dp[(1<<num)-1];
}
};
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TableSeating {
public:
double getExpected(int num, vector<int> probs) {
double dp[1<<num];
memset(dp,0,sizeof(dp));
int can[12];
for(int i=0;i<(1<<num);i++)FORE(j,0,probs.size()){
int s=j+1;
double p=probs[j]/100.0;
int cnt=0;
memset(can,0,sizeof(can));
FORE(k,0,12)if(k+s<=num){
int uu=(1<<(k+s))-(1<<k);
if((i&uu)==uu)can[k]=1,cnt++;
}
if(cnt)FORE(k,0,12)if(can[k]){
int uu=(1<<(k+s))-(1<<k);
dp[i]+=(dp[i-uu]+s)*p/cnt;
}
}
return dp[(1<<num)-1];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TableSeating {
public:
double getExpected(int num, vector<int> probs) {
double dp[1<<num];
memset(dp,0,sizeof(dp));
int can[12];
for(int i=0;i<(1<<num);i++)FORE(j,0,probs.size()){
int s=j+1;
double p=probs[j]/100.0;
int cnt=0;
memset(can,0,sizeof(can));
FORE(k,0,12)if(k+s<=num){
int uu=(1<<(k+s))-(1<<k);
if((i&uu)==uu)can[k]=1,cnt++;
}
if(cnt)FORE(k,0,12)if(can[k]){
int uu=(1<<(k+s))-(1<<k);
dp[i]+=(dp[i-uu]+s)*p/cnt;
}
}
return dp[(1<<num)-1];
}
};
