かなり手こずった。
https://atcoder.jp/contests/abc135/tasks/abc135_e
問題
２次元座標系における格子点の座標(X,Y)と、正整数Kが与えられる。
今原点に点Pがあったとする。1回で点Pを現在位置からマンハッタン距離がK離れる位置に移動できるとするとき、Pを(X,Y)に移動する最短移動回数とその経路を求めよ。
解法
Editorialとは違う解法。
まず、(X,Y)のパリティが奇数でKが偶数の場合は解なし。
基本的な戦略は、できるだけ全力で目的地に向け移動するが、そうすると移動量が余ってしまう場合、若干経路をたるませてどうにかする。
- Kが偶数の場合
- 目的地までの残りの距離が2K以上の間は、とにかく適当に目的地への距離が毎回K縮まるように移動する。
- 目的地までの残り距離が2K未満のとき、うち距離が0とKの場合は自明。
- この時点で、目的地までの距離は偶数である。よって、両者の中点が存在するので、そこから外側の点を通り2手で移動する。
- イメージは下記の通り。点PからQに移動する際、中点★を求めそこからP-Qを頂点とする矩形の外側に距離Kとなるような点●の位置を求め、P-●-Qの順で移動する。
Ｐ ┃ ┃ ┗━★━━━━Ｑ ┃ ┃ ┃ ┃ ┃ ●
| < |
- Kが奇数の場合
- (X,Y)のパリティが奇数の場合
- まずは初手で全力で目的地に向け移動する。もしもともとの目的地までの距離がK未満の場合、目的地を通り過ぎてもよい。
- そうすると、この時点で(X,Y)までの距離が偶数になるので、あとは以下のパターンに持ち込める。
- (X,Y)のパリティが偶数の場合
- 2手ずつセットで移動することを考える。
- 目的地までの距離が2K以上の場合、目的地に向け2回距離が毎回K縮まるように移動する。
- 目的地までの残り距離が2K未満のとき、上の図と同じパターン。
- (X,Y)のパリティが奇数の場合
int K,X,Y; void solve() { int i,j,k,l,r,x,y; string s; cin>>K>>X>>Y; if(K%2==0 && (abs(X)+abs(Y))%2) { cout<<"-1"<<endl; return; } vector<pair<int,int>> V; if(K%2&&(abs(X)+abs(Y))%2) { V.push_back({X,Y}); x=min(K,abs(X)); if(X>0) X-=x; else X+=x; int lef=K-x; if(Y>0) Y-=lef; else Y+=lef; } while(abs(X)+abs(Y)>=2*K) { FOR(j,1+(K%2)) { V.push_back({X,Y}); int lef=K; if(X>0) { i=min(X,lef); X-=i; lef-=i; } else if(X<0) { i=min(abs(X),lef); X+=i; lef-=i; } if(Y>0) { i=min(abs(Y),lef); Y-=i; lef-=i; } else if(Y<0) { i=min(abs(Y),lef); Y+=i; lef-=i; } } } if(abs(X)+abs(Y)==K) { V.push_back({X,Y}); } else if(X||Y) { V.push_back({X,Y}); if(abs(X)>abs(Y)) { x=(abs(X)+abs(Y))/2; y=K-abs(x); if(X>0) X=x; else X=-x; if(Y>=0) Y=-y; else Y=y; } else { y=(abs(X)+abs(Y))/2; x=K-abs(y); if(Y>0) Y=y; else Y=-y; if(X>=0) X=-x; else X=x; } V.push_back({X,Y}); } reverse(ALL(V)); cout<<V.size()<<endl; FORR(v,V) cout<<v.first<<" "<<v.second<<endl; }
