cafelier@SRM

SRM458 250

あとで | 01:41 |

考えたら、2^N 通りの向きを全生成なんてする必要ないですよね。各ペアについて、向きが衝突する向きになる確率は1/4なんだから、「距離2*T以内にあるペアの数 / 4」が答えだ。

class BouncingBalls { public:
   double expectedBounces(vector <int> x, int T) 
   {
      int crashPair = 0;
      for(int i=0; i<x.size(); ++i)
         for(int j=i+1; j<x.size(); ++j)
            if( abs(x[i]-x[j]) <= 2*T )
               crashPair ++;
      return crashPair / 4.0;
   }
};