Kodamanと愉快な仲間たち : R - Three Girls

なぜ女装という設定にしたのだろう。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/three-girls

問題

3整数A,B,Cと、整数列Gが与えられる。
整数列から3要素Gx,Gy,Gzを選んだ時、A+Gx ＜ B+Gy ＜ C+Gzとなるような(x,y,z)の組は何通りか。
ただしx,y,zは互いに異なること。

解法

Gを昇順に並べておく。
yを総当たりしつつ、尺取り法でxやzの取りうる範囲を更新していこう。
基本的にはyに対し(xの組み合わせ)*(zの組み合わせ)を足しこんでいくのだが、x==y・y==z・x==zになってしまうケースもあるのでそれは律儀に取り除こう。

int N;
ll A,B,C;
ll G[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>C;
	FOR(i,N) cin>>G[i];
	sort(G,G+N);
	ll ret=0;
	ll L=-1,R=0;
	FOR(i,N) {
		while(L<N-1 && G[L+1]+A<G[i]+B) L++;
		while(R<N && G[R]+C<=G[i]+B) R++;
		
		ret+=(L+1)*(N-R);
		if(L>=i) ret-=(N-R);
		if(R<=i) ret-=(L+1);
		if(L>=R) ret-=(L-R+1);
		if(L>=i && R<=i) ret+=2;
	}
	cout<<ret<<endl;
}

まとめ

尺取り法の良い練習。