問題はこちら
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); }
144B
17/12/03追記
今までは「できるだけ逆に進んでから目的地へ近づく」としていたが、「目的地に着いてから現地で調整する」とすることで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--?x=1,"<"+!t:">"))y-t&1&&putchar(!y--?y=1,118:94); }
141B