HackerRank HourRank 24 : D. Kth Minimum

なぜ気づかなかったのか…。
https://www.hackerrank.com/contests/hourrank-24/challenges/kth-minimum

問題

２つの整数列A,Bと整数xにより、以下の数列を生成する。　

procedure generate_list(A, B, x):

    let n = length of A
    let m = length of B
    let L = an empty list

    for i from 1 to min(n, m - x), inclusive:
        for j from (i + x) to m, inclusive:
            Append (A[i]*B[j]) to the end of L

    return L

この数列を昇順ソートしたとき、k番目に来るものは何か答えよ。

解法

二分探索で解く。
二分探索で探索中の解をvとする。
数列の生成式を見ると、A[i]に対しBのsuffixのうちA[i]*B[j]≦vとなるjの数を求めたい。
幸いBの数の範囲は大きくないので、BITを使いB[j]≦v/A[i]となるjを数え上げよう。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,21> bt;


int N,M,X;
ll K;
int A[202020],B[202020];

ll hoge(ll v) {
	ZERO(bt.bit);
	ll num=0;
	int i,j;
	
	for(i=N-1;i>=0;i--) {
		if(i+X>=M) continue;
		if(i==N-1) {
			for(j=i+X;j<M;j++) bt.add(B[j],1);
		}
		else {
			bt.add(B[i+X],1);
		}
		
		ll v2=abs(v)/abs(A[i]);
		if(A[i]>0) {
			if(v<0) {
				v2=-v2;
				if(abs(v)%abs(A[i])) v2--;
			}
			v2=max(-1LL<<18,min(1LL<<18,v2))+(1<<19);
			num+=bt(v2);
		}
		else {
			if(v>=0) {
				v2=-v2;
				v2=max(-1LL<<18,min(1LL<<18,v2))+(1<<19);
				num+=bt((1<<20)-2)-bt(v2-1);
			}
			else {
				if(abs(v)%abs(A[i])) v2++;
				v2=max(-1LL<<18,min(1LL<<18,v2))+(1<<19);
				num+=bt((1<<20)-2)-bt(v2-1);
				
			}
		}
	}
	return num;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>X>>K;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>B[i], B[i]+=1<<19;
	
	ll ret=1LL<<40;
	for(i=41;i>=0;i--) {
		if(hoge(ret-(1LL<<i))>=K) ret-=1LL<<i;
	}
	cout<<ret<<endl;
}

まとめ

本番は方針はあっていたが、BITより重いデータ構造を使ってしまいTLEした。