読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

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