yukicoder No.240 ナイト散歩

問題はこちら
No.240 ナイト散歩 - yukicoder

解説には「深さ優先探索」「幅優先探索」の練習問題とあったので、とりあえず深さ優先で実装してみる

int x,y,
	a[8]={1,2,2,1,-1,-2,-2,-1},
	b[8]={2,1,-1,-2,-2,-1,1,2};
void f(int p,int q,int n){
	//n回動いて(p,q)にいる状況
	int i;
	if(p==x&&q==y){puts("YES");exit(0);}
	//目的地に着いてるならOK
	if(n==3)return;
	//着いてないのに3回動いてたらダメ
	for(i=0;i<8;i++)f(p+a[i],q+b[i],n+1);
	//2回以下でまだ着けてないなら動く
}
int main(){
	scanf("%d%d",&x,&y);
	f(0,0,0);
	puts("NO");
	return 0;
}

どこに動けるのかよくわからないからとりあえず
書き出してみる

			3		3		3		3			.
		3		3		3		3		3		.
	3		3	2	3	2	3	2	3		3	.
3		3	2	3	2	3	2	3	2	3		3
	3	2	3		1	2	1		3	2	3	.
3		3	2	1	2	3	2	1	2	3		3
	3	2	3	2	3	0	3	2	3	2	3	.
3		3	2	1	2	3	2	1	2	3		3
	3	2	3		1	2	1		3	2	3	.
3		3	2	3	2	3	2	3	2	3		3
	3		3	2	3	2	3	2	3		3	.
		3		3		3		3		3		.
			3		3		3		3			.

上下左右対称なのはもちろん仮定から明らか
真ん中らへんはだいたい動けるけど微妙な空白があって、外周は八角形っぽい感じ
ということで次のようにABCの3つに分けてみる

B

B

B

B

.

B

B

B

B

B

.

B

C

A

C

A

C

A

C

B

.

B

C

A

C

A

C

A

C

A

C

B

B

A

C

C

A

C

C

A

B

.

B

C

A

C

A

C

A

C

A

C

B

B

A

C

A

C

A

C

A

C

A

B

.

B

C

A

C

A

C

A

C

A

C

B

B

A

C

C

A

C

C

A

B

.

B

C

A

C

A

C

A

C

A

C

B

B

C

A

C

A

C

A

C

B

.

B

B

B

B

B

.

B

B

B

B

.

AとCを合わせた集合は「|x|≦4かつ|y|≦4であり(2,2),(4,4)でない」
BとCを合わせた集合は「|x|≦6かつ|y|≦6かつ|x|+|y|≦9」
ということでこれをそのまま書いて

x;
main(y){
	scanf("%d%d",&x,&y);
	x=abs(x);
	y=abs(y);
	x=!puts(x<7&y<7&x+y<10&(x+y)%2|x<5&y<5&(x-y||x%2|!x)?"YES":"NO");
}

縮めて

x;main(y){x=scanf("%d%d",&x,&y)>puts(x<7&y<7&x+y<10&x+y|x<5&y<5&(x-y||x%2|!x)?"YES":"NO",x=abs(x),y=abs(y));}
//(x+y)%2はx+y&1と同じ

109B

どの場所に移動可能かをbitで保存して参照する
そもそも移動可能な場所は「|x|≦6かつ|y|≦6」の範囲にしか存在しないので高々49bitで足りる
(7*x+y)bit目に(x,y)へ移動可能かどうかを保存すれば
0001010 0010101 0101111 1011111 0111011 1011111 0111111　で　44714836291519　となる
（わかりやすさのために7bit毎に区切った）

ということで

x;main(y){x=scanf("%d%d",&x,&y)>puts(1&44714836291519>>x*7+y?"YES":"NO",x=abs(x),y=abs(y));}

92B……といいたいところなんだけど、これは嘘AC
bitshiftにbit長以上の値を与えた時の動作は未定義であり、
ここでは 44714836291519>>x*7+y は 44714836291519>>((x*7+y)&63) と等しい
というわけでX=9,Y=1などのケースで落とされる
正確にはこう

x;main(y){x=scanf("%d%d",&x,&y)>puts(x<7&y<7&44714836291519>>x*7+y?"YES":"NO",x=abs(x),y=abs(y));}

98B