Codeforces #274 Div1 B. Long Jumps

Hackしどころが多くて10個Hackした。
http://codeforces.com/contest/480/problem/B

問題

長さLの定規がある。
この定規はN箇所だけ目盛がついており、その位置はA[i]である。(ただしA[0]==0、A[N-1]==L)

この定規でXとYの長さを測りたい。
長さを正確に測るためには、A[j]-A[i]==Xとなる目盛位置A[j],A[i]及びA[k]-A[l]==Yとなる目盛位置A[k],A[l]が存在しなければならない。

今の目盛で足りない場合、いくつか目盛を足しても良い。
その場合、足さなければならない目盛の数と位置を答えよ。

解法

まず初期状態で条件を満たせるか判定する。
setを使って、A[i]+XやA[j]+Yに相当する目盛があるか探す。

A[i]+XとA[j]+Yがともに存在するなら、それ以上の目盛は不要。
A[i]+XとA[j]+Yの片方が存在するなら、足りない方は目盛位置XまたはYに目盛を１個追加すればよい。

問題はA[i]+XとA[j]+Y両方がない場合である。
最悪XとYの位置に目盛を２個足せば条件を満たせるので、あとは目盛１個追加で条件を満たせるか探索すればよい。
各目盛位置について、A[i]±Xの位置に目盛を追加してみて、その±Yの位置に別の目盛が存在すれば、その目盛位置１か所を追加すればよい。

ll N,L,X,Y;
ll A[100040];
set<ll> S;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>X>>Y;
	FOR(i,N) cin>>A[i];
	FOR(i,N) S.insert(A[i]);
	
	int ok=0;
	ITR(it,S) {
		ll tmp=*it;
		if((tmp+X<=L && S.count(tmp+X)) || (tmp-X>=0 && S.count(tmp-X))) ok|=1;
		if((tmp+Y<=L && S.count(tmp+Y)) || (tmp-Y>=0 && S.count(tmp-Y))) ok|=2;
	}
	
	if(ok==3) return _P("0\n");
	if(ok==1) return _P("1\n%lld\n",Y);
	if(ok==2) return _P("1\n%lld\n",X);
	
	ITR(it,S) {
		FOR(i,2) {
			ll tmp=*it+((i==0)?X:-X);
			if(tmp<=0 || tmp>=L) continue;
			if((tmp+Y<=L && S.count(tmp+Y)) || (tmp-Y>=0 && S.count(tmp-Y)))
				return _P("1\n%lld\n",tmp);
		}
	}
	_P("2\n%lld %lld\n",X,Y);
}

まとめ

シンプルだけどB問題としてはちょうどいい難易度。
適度にコーナーケースあるしね。