SRM458 Div2Med (Div1Easy) BouncingBalls

解法１
先ず蟻本に掲載されている問題(Ants)と同じように、２つのボールの衝突は衝突していないですり抜けると同等であることに気づく。

ボール二者のみについて着目すると、これらは「互いに離れていく」か「両方左に進む」か「両方右に進む」か「互いに近づく」かである。「互いに近づく」ときのみ衝突の場合の数が増える。

あとはビット全探索をする。開始の向きを状態で持ち、それぞれの状態における衝突回数を全ての状態の数(2の要素数乗)で割れば期待値が求まる。

#include <bits/stdc++.h>
using namespace std;

class BouncingBalls {
public:
   double expectedBounces( vector <int> x, int T ) {
     int const N = x.size();
     sort(x.begin(), x.end());
     int cnt = 0;
     for(int S=0; S<(1<<N); S++) {
     	for(int i=0; i<N; i++) {
     		if(!(S>>i & 1)) continue;
     		for(int j=i+1; j<N; j++) {
     			if(S>>j & 1) continue;
     			cnt += x[j]-x[i] <= 2*T;
     		}
     	}
     }
     return cnt / double(1<<N);
   }
};

解法２
「互いに離れていく」か「両方左に進む」か「両方右に進む」か「互いに近づく」かで分析が４パターンになので、ボール二者に対して確率 0.25 ずつだけ期待値が増える。なので要素数分の二重ループで解ける。

#include <bits/stdc++.h>
using namespace std;

class BouncingBalls {
public:
    double expectedBounces( vector <int> x, int T ) {
        int const N = x.size();
        int cnt = 0.;
        sort(x.begin(), x.end());
        for(int i=0; i<N; i++)
            for(int j=i+1; j<N; j++)
                cnt += x[j]-x[i] <= 2*T;
        return cnt * 0.25;
    }
};