AtCoder Beginner Contest 135：E - Golf

問題
解法
解答

問題

https://atcoder.jp/contests/abc135/tasks/abc135_e

解法

考察をしやすくするため X >= Y >= 0 となるように X, Y を変換してしまう．変換した場合は，答えを出力する際に元の X, Y に当てはまるように再度復元する必要があるので注意．

まず，K が偶数で (X + Y) が奇数であるとき，ボールが到達できるマスは原点からのマンハッタン距離が偶数であるものに限られるので，どのようにボールを操作しても (X, Y) には到達できない．また，(X + Y) == K であるときは自明に 1 回の操作で到達できる．

それ以外である場合，必要な操作の回数 n は ceil( (X + Y) / K ) となる．ただし，n は 2 以上の整数にする必要がある（∵ n = 1 は (X + Y) == K のときしかありえない）．X < K のとき，以下の図のように 3 回かけて移動すればよい．

f:id:babcs2035:20190729225557j:plain

X >= K であるとき，以下の図のように n 回かけて移動すればよい．

f:id:babcs2035:20190729225756j:plain

ここで注意すべきなのは，線分 AB = X でこれは過程より AB >= K であるから線分 OA（O は原点＝スタートの意）上の点から線分 BG（G はゴールの意）上の点まで 1 回で動くことはあり得ないということ．これが保証されていないと，移動する総距離は K になるが，移動の始点から終点のマンハッタン距離が K にならないことになってしまう．また，(n * K - X - Y) が偶数でないと折れ曲がる点の座標が整数とならないから，もし (n * K - X - Y) が奇数であるとき，すなわち，(X + Y) の偶奇と (n * K) の偶奇が異なる場合（(X + Y) が偶数で K が奇数の場合）は，操作回数を 1 回増やしてあげる必要がある．