SRM496 Div1 Medium(500) OneDimensionalBalls

OneDimensionalBalls

速さは高々secondPicture.size()通り。速さを決めたとき、firstPictureとsecondPictureをソートして上下に並べ同一のボールになりうる組み合わせに線を引くと、
／＼／＼……＼／
こんな感じの折れ線に分解できる。
／＼／＼……／＼
ならばfirstとsecondの組み合わせの選び方はこの折れ線が含むsecondの要素数。
／＼／＼……＼／　と　＼／＼／……／＼
なら１通り。
＼／＼／……＼／
なら０通り。これを掛け合わせるとその速さでのボールの組み合わせの総数が得られる。

#include <vector>
#include <set>
using namespace std;

class OneDimensionalBalls{public:
long long countValidGuesses( vector <int> firstPicture, vector <int> secondPicture )
{
    set<int> speed;
    for ( int i=0; i<(int)secondPicture.size(); i++ )
        if ( secondPicture[i] != firstPicture[0] )
            speed.insert( abs(secondPicture[i]-firstPicture[0]) );

    long long ans = 0;

    for ( set<int>::iterator it=speed.begin(); it!=speed.end(); it++ )
    {
        set<int> ball[2] = { set<int>(firstPicture.begin(),firstPicture.end()),
                             set<int>(secondPicture.begin(),secondPicture.end()) };

        long long t = 1;

        while ( !ball[0].empty() || !ball[1].empty() )
        {
            int f;
            
            if ( ball[1].empty() ||
                 !ball[0].empty() && *ball[0].begin() < *ball[1].begin() )
                f = 0;
            else
                f = 1;

            int p = *ball[f].begin();
            int c = 0;
            do
            {
                ball[f].erase(p);
                f = 1-f;
                p += *it;
                c++;
            }
            while ( ball[f].count(p) > 0 );

            if ( f == 0  &&  c%2 == 1 )
                t *= (c+1)/2;   //  ／＼……／＼
            if ( f == 1  &&  c%2 == 1 )
                t *= 0;         //  ＼／……／＼
        }

        ans += t;
    }

    return ans;
}};