SRM458 Div1 Easy(250), Div2 Medium(500) BouncingBalls

TopCoder

BouncingBalls

ボールを区別しなければ反射も透過も同じ動き、とTwitterに書いてあった。初期位置とT秒後の位置で左右が入れ替わっていれば、２つのボールは衝突している。

#include <vector>

using namespace std;

class BouncingBalls
{
public:
    double expectedBounces( vector <int> x, int T );
};

double BouncingBalls::expectedBounces( vector <int> x, int T )
{
    int n = (int)x.size();
    int c = 0;

    for ( int t=0; t<1<<n; t++ )
    {
        for ( int i=0; i<n; i++ )
        for ( int j=i+1; j<n; j++ )
        {
            //  i番目, j番目のボールの初期位置、T秒後の位置
            int fi = x[i];
            int fj = x[j];
            int ti = x[i] + (1-(t>>i&1)*2) * T;
            int tj = x[j] + (1-(t>>j&1)*2) * T;

            //  相対位置の符号が移動前後で異なれば衝突
            if ( fj - fi >= 0  &&  tj - ti <= 0  ||
                 fj - fi <= 0  &&  tj - ti >= 0 )
                c++;
        }
    }

    return (double)c / (1<<n);
}

先輩から2nもループを回す必要は無いと言われた。なるほど。

double BouncingBalls::expectedBounces( vector <int> x, int T )
{
    int n = (int)x.size();
    int c = 0;

    for ( int i=0; i<n; i++ )
    for ( int j=i+1; j<n; j++ )
        if ( abs(x[i]-x[j]) <= 2*T )
            c++;

    return (double)c / 4;
}