ABC135 E Golf
問題
$ (0, 0)から$ (X,Y)には移動可能でしょうか?
可能な場合には、移動回数が最小になるような移動方法を1つ求めてください。
考察
$ (0, 0)から$ (x, y)へ移動したときの$ x + yの偶奇性に注目して可能かどうかについて考えてみます。 $ Kが偶数ならば
$ x+y=Kも偶数です
移動を繰り返しても偶奇性は変わりません
従って、$ X+Yが奇数の場合には、そのような点に移動することができません
$ Kが奇数ならば
$ x+y=Kは奇数です
$ (0,0)から移動を繰り返すと毎回偶奇が変わります
偶→奇→偶→奇→…
どのような点に移動可能なのか、最初の数回を観察してみます。
1回目では$ |x| + |y| = K上に移動できます
https://gyazo.com/fa9c8aea0c17abc6a71460395a58bb84
2回目では$ |x| + |y| = K上のそれぞれの点について1回目と同様の正方形の範囲に移動できるので、仮に連続であれば$ |x| + |y| <= 2Kの点をすべて掃けることがわかります。
$ |x| + |y| = K上を四角が移動すると考えるとイメージしやすいです
https://gyazo.com/862a7f0245f09007860662ed29c1874b
$ |x| + |y| <= 2K の点$ (a,b)が与えられた時に、2回でその点に移動することができそうですが、実際にどのような移動をすればよいのでしょうか?
簡単のため$ Y \geq X \geq 0で考えます。
はじめにX, Yに以下の変換をします
$ X <0であればX = -X
$ Y<0であればY = -Y
$ X > Yであればswap(X, Y)
逆変換は、した変換を逆順にすればよいです
2回の移動を$ (x_1, y_1), (x_2, y_2)とすると以下が成り立ちます。
1. $ x_1 + y_1 = K
2. $ -x_2 + y_2 = K
3. $ x_1 + x_2 = a
4. $ y_1 + y_2 = b
2の符号は関心ある領域を青い太線のところが掃くことを考えるとわかりやすいです。https://gyazo.com/1a1a8612a07f7108bc4bcc09cf4ef7fc
これを解くと
$ x_1 = K + \frac{a-b}{2}
$ y_1 = - \frac{a-b}{2}
$ x_2 = -K + \frac{a+b}{2}
$ y_2 = \frac{a-b}{2}
$ (x_1, y_1), (x_2, y_2)が格子点であるためには$ a + bが偶数である必要があることがわかります。
$ a + bが奇数であっても$ Kが奇数であれば1度移動することで$ a + bが奇数の場合に帰着することができます。
以上のことから$ X, Yから距離$ 2K以内の点まで移動すれば、後は以下のように$ X, Yへ移動できることがわかりました。
その点が$ X, Yなら終わり
$ (X, Y)への距離が$ Kなら1度移動して終わり
$ (X, Y)への距離が偶数なら
2回移動して終わり
$ (X, Y)への距離が奇数なら
3回移動して終わり
1回移動して距離が偶数の場合へ
距離$ 2K以内になるまで、どのように移動するか考えます
戻るのは損なので、m回の移動で最も遠くまで行ける$ |x| + |y| = mK上を移動していきます
移動先から見た時に$ (X, Y)が$ Y \geq X \geq 0であるように移動したいです
$ xの差が$ Kより大きい間$ (K, 0)移動します
$ yの差が$ 2Kより大きい間$ (0, K)移動します
まだ距離が$ 2Kよりも大きい場合には$ (x座標の差, K - (x座標の差))移動します
緑の領域https://gyazo.com/ab99f2315d1fcb8cee586801b01bef65
もう少しマシな移動の仕方がありそうです
解法
$ Kが偶数かつ$ X + Yが奇数なら不可能なので-1を出力して終了
$ Y \geq X \geq 0に変換
距離$ 2K以下になるまで大きく移動
詰めの移動
逆変換して出力
参考