TopCoder SRM 496 Div1 Medium OneDimensionalBalls

問題

n個のボールの座標が与えられる。
ボールはそれぞれ、数直線上を左または右に、同じ速さで動いている。

ここにいくつかボールを足し、時間が経った後でのボールの座標が与えられる。

最初と最後のボールの対応の組み合わせとしてありうるものは何通りあるか求めよ。

制約条件

最初のボールの個数≦50
最後のボールの個数≦50
ボールの座標≦10^8

方針

ボールの速度を一つ決める。
すると、対応しうるボールとボールの関係がグラフになる。

このグラフは二部グラフであり、更に全ての頂点の次数が2以下で、
ループを持たないということが言える。

なので、連結成分ごとにつながり方が何通りあるかを数えて掛け合わせれば、
その速度でのボールの対応関係の場合の数が求まる。
これを全ての速度に対して足し合わせればよい。

連結成分ごとにつながり方が何通りあるかであるが、
上に述べたグラフの性質から、
最初のボールk個と最後のボールl個が連結成分になっているとすると、
k=lまたはk+1=lまたはk=l+1になっている。
k=lのとき対応関係は1通り、
k+1=lのとき、対応関係はl通り、
k=l+1のとき対応関係は0通りである。

ソースコード

int n,m;
bool e[100][100];
bool v[100];
int L,R;
void rec(int c){
	v[c]=1;
	if(c<n)L++; else R++;
	rep(i,n+m)if(e[c][i]&&!v[i])rec(i);
}
ll calc(){
	memset(v,0,sizeof(v));
	ll ret=1;
	rep(i,n)if(!v[i]){
		L=R=0; rec(i);
		if(L>R)return 0;
		if(L<R)ret*=R;
	}
	return ret;
}

class OneDimensionalBalls {
	public:
	long long countValidGuesses(vector <int> a, vector <int> b) 
	{
		n=a.size(); m=b.size();
		memset(e,0,sizeof(e));
		set<int> s;
		rep(i,n)rep(j,m)s.insert(abs(a[i]-b[j]));
		s.erase(0);
		ll ans=0;
		fr(it,s){
			rep(i,n)rep(j,m)e[i][j+n]=e[j+n][i]=abs(a[i]-b[j])==*it;
			ans+=calc();
		}
		return ans;
	}
};