問題
http://community.topcoder.com/stat?c=problem_statement&pm=10726&rd=14180
１直線上に複数のボールが置かれている。
ボールの置かれている位置はあらかじめわかっている。
各ボールを同時に、それぞれ左右のどちらかに転がしたとき
T秒後にボールが衝突した回数の期待値を求める。
解き方
ボールが衝突した時に左右に移動することは考えず、
すり抜けると考えることができる。
このとき、各ボールが左右に動くすべての場合に対し、
ボールのペアすべてに対し衝突しているかどうかカウントしていけばよい。
別解として、ボールのペアそれぞれについてカウントすることになるので
左右に動くすべての場合を求めずとも、
各ペアについて衝突する可能性があるなら０．２５を足していけば求められる。
コード
class BouncingBalls {
public: double expectedBounces(vector<int> x, int T) {
int n=x.size();
sort(all(x));
double ret=0;
for(int mask=0;mask<(1<<n);mask++){
FORE(i,0,n)FORE(j,i+1,n){
if( (mask&(1<<i)) && !(mask&(1<<j)) && x[j]-x[i]<=2*T){
ret++;
}
}
}
return ret/(double)(1<<n);
}
};
public: double expectedBounces(vector<int> x, int T) {
int n=x.size();
sort(all(x));
double ret=0;
for(int mask=0;mask<(1<<n);mask++){
FORE(i,0,n)FORE(j,i+1,n){
if( (mask&(1<<i)) && !(mask&(1<<j)) && x[j]-x[i]<=2*T){
ret++;
}
}
}
return ret/(double)(1<<n);
}
};