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

メモ

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

yukicoder No.232 めぐるはめぐる (2)

問題はこちら
No.232 めぐるはめぐる (2) - yukicoder

右方向を第一軸(x軸)、上方向を第ニ軸(y軸)とする座標で表す
目的地の座標は(B,A)である(逆になっていることに注意(1WA))
まずYES,NOを判別する
(x,y)にt回"以下"の移動で辿りつけない⇔t<x or t<y である
また、ちょうど1回の移動でたどり着ける場所にはちょうど2回の移動でたどり着くことができるので、"1回以上"t回以下の移動でたどり着くことができる場所にはちょうどt回の移動でたどり着くことが可能。
よって結局まとめると
(x,y)にちょうどt回の移動で辿りつけない⇔t<x or t<y or (t=1 and x=0 and y=0)
(原点にはちょうど1回の移動では辿りつけない)

実際の動き方を考える
左右の移動と上下の移動は独立に考えることができる
最初に逆方向に可能な限り進み、その後で正しい方向へ進む、とすることで可能な限り移動量を増やし空き時間をなくすことを目論む
ただしこのままだと、例えばt=5で(0,0)に行くとき、左右方向は←←→→、上下方向は↓↓↑↑となり、単純に前から埋めていくと最後の1回が空きになってしまう
空きになってしまう可能性があるのは最後の1回だけだから、必要なら上下移動の始まりを1回遅らせることでうまくいく

int main(){
	int t,y,x;
	scanf("%d%d%d",&t,&y,&x);
	if(t<x|t<y||t+x+y==1)puts("NO");
	else{
		puts("YES");
		while(t){
			//自分は常に原点にいて目的地の方が動くと考え、(t,x,y)を(t-1,x',y')に更新していく
			if(x<t-1){putchar('<');x++;}
			else if(x!=0){putchar('>');x--;}
			if(y%2==t%2){
			//yとtの偶奇が一致しないなら、最初から移動を始めると最後の1回が空きになってしまう
			//ひとたび一致すれば、その後は移動し続ける限り一致したままになる
				if(y<t-1){putchar('v');y++;}
				else if(y!=0){putchar('^');y--;}
			}
			putchar('\n');
			t--;
		}
	}
	return 0;
}

縮める

t,y;
main(x){
	scanf("%d%d%d",&t,&y,&x);
	for(puts(t<x|t<y|t+x+y==1?t=0,"NO":"YES");t--;puts(""))
		//tのdecが先に行われるので、ループ内の条件式が上とは1ずれている
		x<t?putchar(60),x++:x--&&putchar(62),
		y%2-t%2&&putchar(y<t?y++,118:(y--,94));
}

もうちょっと縮めたい

//y座標の方は簡単
y%2-t%2&&putchar(y<t?y++,118:(y--,94))
y-t&1&&putchar(y--<t?y+=2,118:94)

//x座標の方はputcharが2回あるのが気になる
x<t?putchar(60),x++:x--&&putchar(62)
putchar(x<t?x++,60:x--?62:0)
//これだと\0が入ってWAになってしまう
puts(x<t?x++,"<":x--?">":"")
//よく考えたら後ろにputsが余っていたのでそれとくっつけることでうまくいった

ということでまとめて

t,y;
main(x){
	scanf("%d%d%d",&t,&y,&x);
	for(puts(t<x|t<y|t+x+y==1?t=0,"NO":"YES");t--;puts(x<t?x++,"<":x--?">":""))y-t&1&&putchar(y--<t?y+=2,118:94);
}

147B

16/07/23追記
自明な3B更新

t,y;
main(x){
	scanf("%d%d%d",&t,&y,&x);
	for(puts(t<x|t<y|t+x+y<2?t=0,"NO":"YES");t--;puts(x<t?x++,"<":">"+!x--))y-t&1&&putchar(y--<t?y+=2,118:94);
}

146B