Distributed Code Jam 2017 Round 1 : D. todd_and_steven

ちょっと迷ったけど解けてよかった。
https://code.google.com/codejam/contest/8314486/dashboard#s=p3

問題

奇数だけからなる数列と偶数だけからなる数列があり、いずれも昇順にソート済みである。
また、同じ整数は複数含まれていない。

この2つの整数をマージし、昇順にしたものをXとする。各要素iにおける(X[i] xor i)の総和を求めよ。

解法

Smallに関してはマージソートを行えばよい。

Largeに関してもマージソートを行う。
各ノードでは、先頭から順に全要素の(1/(ノード数))分ずつ計算を担当するものとする。
全要素をN個とし、ノード数をPとすると、(0-originで)i番目のノードはソート後の数列について、[N*i/P,N*(i+1)/P)の範囲に相当する位置の要素を求める必要がある。

ソート後の数列で[N*i/P,N*(i+1)/P)の範囲のindexに格納される整数が[L,R)とする。
元の両数列に対し二分探索を用いることで、L,Rが求まり、かつ[L,R)に対応する元の2数列内の位置が求められる。
あとはそれらに対しマージソートしつつ(X[i] xor i)を計算していく。

int TN,MY;
ll NO,NE;
ll mo=1000000007;

void slow() {
	int i,j,k,l,r,x,y; string s;
	if(MY!=0) return;
	
	x=y=0;
	ll O=(x==NO)?1LL<<60:GetToddValue(x);
	ll E=(y==NE)?1LL<<60:GetStevenValue(y);
	ll ret=0;
	ll id=0;
	while(x<NO || y<NE) {
		if(O<E) {
			(ret += O^id)%=mo;
			x++;
			O=(x==NO)?1LL<<60:GetToddValue(x);
		}
		else {
			(ret += E^id)%=mo;
			y++;
			E=(y==NE)?1LL<<60:GetStevenValue(y);
		}
		id++;
	}
	
	cout<<ret<<endl;
}

int numO(ll v) {
	int num=0;
	for(int i=30;i>=0;i--) if(num+(1<<i) <= NO && GetToddValue(num+(1<<i)-1)<=v) num+=1<<i;
	return num;
}

int numE(ll v) {
	int num=0;
	for(int i=30;i>=0;i--) if(num+(1<<i) <= NE && GetStevenValue(num+(1<<i)-1)<=v) num+=1<<i;
	return num;
}

void fast() {
	ll L=(NO+NE)*MY/TN;
	ll R=(NO+NE)*(MY+1)/TN;
	
	ll v=0;
	for(int i=35;i>=0;i--) if(numO(v+(1LL<<i))+numE(v+(1LL<<i))<=L) v+=1LL<<i;
	
	int x=numO(v), y=numE(v);
	ll ret=0;
	ll O=(x==NO)?1LL<<40:GetToddValue(x);
	ll E=(y==NE)?1LL<<40:GetStevenValue(y);
	for(ll i=L;i<R;i++) {
		if(O<E) {
			(ret += O^i)%=mo;
			x++;
			O=(x==NO)?1LL<<60:GetToddValue(x);
		}
		else {
			(ret += E^i)%=mo;
			y++;
			E=(y==NE)?1LL<<60:GetStevenValue(y);
		}
	}
	
	PutInt(0,ret);
	Send(0);
	if(MY!=0) return;
	
	ret=0;
	int i;
	FOR(i,TN) {
		Receive(i);
		ret += GetInt(i);
	}
	
	cout<<ret%mo<<endl;
	
}

まとめ

E-largeの方が難しくない？