yukicoder No.467 隠されていたゲーム

問題はこちら
No.467 隠されていたゲーム - yukicoder

対称性からx,yは0以上としてよい
・0手で移動可能⇔原点
・1手で移動可能⇔チェビシェフ距離がdiのいずれかと等しい
であることは明らか
それ以外の場合を考える。d=max{di}とする
(★)チェビシェフ距離がXの点に移動するにはceil(X/d)手以上かかる
(☆)2手で移動可能⇔チェビシェフ距離が2d以下
∵⇐：dによる移動のみで(0,0)→(d,y-d)→(x,y)とできる
　⇒：★より
チェビシェフ距離が2dより大きいときは、(0,d),(d,d),(d,0)のいずれかに移動することで目的地までのチェビシェフ距離をd小さくできるので、(☆)より帰納的にceil(X/d)手で移動できることが分かる。(★)よりこれが最小。

#define max(p,q)(p>q?p:q)
int c(int*a,int*b){return*a-*b;}
int main(){
	int n,x,y,i,ans,d[99];
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",d+i);
	qsort(d,n,4,c);
	scanf("%d%d",&x,&y);
	x=max(abs(x),abs(y));

	if(x==0)ans=0;
	else if(x<=2*d[n-1]){
		ans=2;
		for(i=0;i<n;i++)if(x==d[i])ans=1;
	}
	else ans=(x+d[n-1]-1)/d[n-1];
	//ceil(x/d[n-1])=(x+d[n-1]-1)/d[n-1]
	printf("%d",ans);
	return 0;
}

場合分けをぐっと睨むと、ceil(x/d)と一致しないのは、x<dかつx≠0かつdiの中にxと一致するものがないとき、その時に限る。
なので、diの中にxと一致するものがあるかどうかをフラグfに保存すれば、全ての場合をまとめて

(x+d-1)/d+(x<d&&x&&!f)

とあらわすことができる。
いずれにせよ、diの中にmax(|x|,|y|)と一致するものがあるかどうか確認しないといけないので、入力と合わせて2回for文が必要そう……？

a[99],x,d,i;
main(f){
	for(;~scanf("%d",a+i);)x=fmax(abs(a[i++]),abs(a[i-1]));
	for(i-=2;--i;f&=x!=a[i])d=fmax(d,a[i]);
	x=!printf("%d",(x+d-1)/d+(x<d&f&&x));
}

152B

よく考えると、これも後ろから見れば簡単になるやつだから、再帰で書くと短くできそう

x,F,d,i;
f(t){~scanf("%d",&t)?f(),++i>2?d<t?d=t:0,F*=x!=t:x<(t=abs(t))?x=t:0:0;}
main(){x=!printf("%d",(f(gets(&F))&&x<d&&x)+(x+d-1)/d);}
//fの返り値がFになっていることを利用

135B