MemSQL start[c]up 2.0 Round 2 : B. Distributed Join

問題設定が若干ややこしい。
http://codeforces.com/contest/458/problem/B

問題

2つのテーブルA,Bがあり、それぞれN個・M個のパーティションで構成される。
各パーティションにはa[i]個及びb[j]個の行がある。

このパーティション分割された2つのテーブルのdistributed joinを求めたい。

あるパーティションにある行を他のパーティションにコピーする場合、その行分のコストがかかる。
各a[i]とb[j]の対について、どこかのパーティションにa[i]・b[j]両方の行があるようにしたい。
コピーの最小コストを求めよ。

解法

全部のa[i]をBのどこかに移すことを考える。
各a[i]をb[0]～b[M-1]個のパーティション全部にコピーしても良いが、その場合M*(a[0]+a[1]+...+a[N-1])のコストがかかる。
もう少しコストを下げる方法として、b[0]をb[M-1]にコピーしてしまえば、(a[0]+a[1]+...+a[N-1])分をb[0]のパーティションにコピーするコストが不要になる。

上記検討より、以下の手順を取ればよい。
まずa[i]とb[j]を昇順ソートする。
b[j]のうち下位x個をb[M-1]にコピーすることを考えると、総コストは(b[0]+b[1]+...+b[x-1])+(a[0]+a[1]+...+a[N-1])*(M-x)となるので、xを総当たりして最小値を求める。
また、aとbを入れ替えて同様にa[j]のうち下位x個をa[N-1]にコピーするケースを考えて最小値を求めればよい。

最小値計算は事前に累積和を取っておけばO(N+M)で済むので、ソートの方が重くO(NlogN+MlogM)。

int M,N;
unsigned long long A[1000010],B[1000010],AS[1000010],BS[1000010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>N;
	FOR(i,M) cin>>A[i];
	FOR(i,N) cin>>B[i];
	sort(A,A+M);
	sort(B,B+N);
	FOR(i,M) AS[i+1]=AS[i]+A[i];
	FOR(i,N) BS[i+1]=BS[i]+B[i];
	
	unsigned long long mi=1ULL<<63;
	FOR(i,N) mi=min(mi,AS[M]*(N-i)+BS[i]);
	FOR(i,M) mi=min(mi,BS[N]*(M-i)+AS[i]);
	cout << mi << endl;
}

まとめ

確かに言われてみるとjoinしてるな。