yukicoder : No.1597 Matrix Sort

ここら辺も典型。
https://yukicoder.me/problems/no/1597

問題

N*Nの行列Eがある。
正整数Pに対し、数列A,Bを用いてE(i,j)=(A[i] + B[j]) mod P で定義される。
Eの各要素を小さい順に並べたとき、K番目にくる値を求めよ。

解法

解を二分探索しよう。
今v以下の値がK個以上あるかを判定する。

A[i]を総当たりするとき、0≦(A[i]+B[j])%P≦v となるjの個数を求めたいわけだが、これはBを事前にソートしておけばAの各要素ごとにO(logN)で求められる。
よって全体でO(Nlog^2N)で済む。

int N;
ll K;
int P;
int A[101010];
int B[201010];

ll num(int v) {
	if(v<0) return 0;
	ll ret=0;
	int i;
	FOR(i,N) {
		int s=(P-A[i])%P;
		ret+=lower_bound(B,B+2*N,s+v+1)-lower_bound(B,B+2*N,s);
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>P;
	FOR(i,N) cin>>A[i];
	FOR(i,N) {
		cin>>B[i];
		B[N+i]=B[i]+P;
	}
	sort(B,B+2*N);
	
	int ma=P-1;
	for(i=30;i>=0;i--) if(num(ma-(1<<i))>=K) ma-=1<<i;
	cout<<ma<<endl;
}

まとめ

ここら辺は典型感強いね。