yukicoder : No.602 隠されていたゲーム2

落ち着いて考えれば簡単なはずなのに、妙に手間取った。
https://yukicoder.me/problems/no/602

問題

２次元座標上で(0,0)から(x,y)に移動したい。
その際、整数列D[i]が与えられる。
1回でいずれかのD[i]に対し、現在値からマンハッタン距離がD[i]の格子点に移動できるとき、目的地まで2回以内で到達できるか。
できるなら最小回数を求めよ。

解法

(x,y)が原点なら0回だし、abs(x)+abs(y)==D[i]となるD[i]があれば1回。
あとは２回のケースを考えよう。

大きく移動する方D[a]を１回目に行い、２回目をD[b]小さく移動したとする。
この時、移動可能な範囲は原点を中心とした幅のある菱形に含まれる。
より正確には以下のとおりである。

• 原点からのマンハッタン距離をPとする。
  • Pの偶奇が、D[a]+D[b]の偶奇と等しい。
  • D[a]-D[b]≦P≦D[a]+D[b]である。

後者の条件より、D[b]はできるだけ大きい方が良いのが明らかである。
よって、aを総当たりしつつ、bはD[a]+D[b]の偶奇がPと一致するもののうち最大なものを選び、上記の移動可能範囲に(x,y)が含まれるか判定しよう。

int N;
ll D[101010];
ll X;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>D[i];
	cin>>x>>y;
	X=abs(x)+abs(y);
	int d=X%2;
	sort(D,D+N);
	
	int mi=3;
	if(X==0) mi=0;
	
	ll P[2]={-1,-1};
	FOR(i,N) {
		if(D[i]==X) mi=min(mi,1);
		P[D[i]%2]=D[i];
		ll c=P[d^(D[i]%2)];
		if(abs(D[i]-X)<=c) mi=min(mi,2);
	}
	if(mi==3) mi=-1;
	
	
	cout<<mi<<endl;
	
}

まとめ

微妙に判定条件を間違えてWAを繰り返したのだが、結局Nが小さそうなので総当たりでゴリ押ししてしまった。