先に答え
ABC135 E Golfは、原点から目標の整数座標 (X,Y) へ、毎回ちょうどマンハッタン距離 K だけ移動し、最小手数と通過する座標列を出力する問題です。先に結論を書くと、D=|X|+|Y| と置いたとき、到達できないのは K が偶数で D が奇数 の場合だけです。この判定にGCD条件は使いません。
到達可能なら、D=K は1手、0<D<2K は D の偶奇に応じて2手または3手、D>=2K は ceil(D/K) を出発点にして nK-D が偶数になる最小の n を選びます。残差が大きい間は目標方向へ K 進み、最後だけ1手または2手の補完を作れば、負の座標を含む入力でも同じコードで解けます。
操作、制約、入出力、公式サンプルは AtCoder公式問題文、最小手数と構成の考え方は 公式Editorial PDFで確認できます。以下では、その内容を座標列の検査まで追える形にします。
問題を距離と偶奇に置き換える
現在位置を (cx,cy)、目標を (X,Y) とします。目標までの距離を D=|X|+|Y| とすれば、どの手数が必要かを距離の下限と偶奇で絞れます。1手の移動量を (dx,dy) と書くと、操作条件は |dx|+|dy|=K です。
- 三角不等式から、
n手で届くにはD<=nKが必要です。 - 整数では
|v|とvの偶奇が同じなので、dx+dyの偶奇はKの偶奇と同じです。 - したがって
n手後の座標和の偶奇はnKで決まり、目標へ届くにはnK-Dが偶数でなければなりません。DとX+Yも同じ偶奇です。
K が偶数なら座標和の偶奇は毎手変わらず、原点の偶数から D が奇数の点へ届きません。逆に、K が偶数で D が偶数の場合と、K が奇数の場合は、距離と偶奇が合う手数を選んで後述の構成を使えます。必要条件だけを見てGCDで判定するのではなく、この問題で実際に必要な条件はこの偶奇条件です。
最小手数を決める
まず距離の下限 ceil(D/K) を考え、そこから偶奇条件を満たす最小値を選びます。(X,Y)!=(0,0) なので入力時の D は0ではありません。
D=K：目標そのものへ1手で移動できます。0<D<2K：Dが偶数なら2手です。Dが奇数なら、到達可能なケースではKも奇数なので2手では偶奇が合わず、3手にします。D>=2K：n=ceil(D/K)とし、nK-Dが奇数ならnを1増やします。距離の下限を満たし、偶奇も合う最初の値なので、これが最小手数です。
たとえば K=4、(X,Y)=(9,9) なら D=18 です。ceil(18/4)=5 で、5*4-18=2 は偶数なので、必要な手数は5です。最小手数を先に固定するため、構成した座標列の長さもこの値と一致させます。
残り距離が大きい間はKだけ進む
現在位置から目標までの残差を R=|X-cx|+|Y-cy| とします。R>2K の間は、dx=X-cx、dy=Y-cy として、まずX方向へ min(|dx|,K) だけ目標に近づき、残りの K-min(|dx|,K) をY方向へ目標に近づく向きに割り当てます。残差が十分大きいので、どちらの軸でも目標を通り越しません。
この1手の移動量は、X方向の量とY方向の量の合計が必ず K です。しかも両方とも目標へ向かうため、残差はちょうど K 減ります。この処理を繰り返すと、最後の残差が 2K 以下になります。sgn(dx) と sgn(dy) を掛けているので、目標が負の座標にあっても同じ計算です。
公式サンプル3の K=4、(X,Y)=(9,9) では、(0,0) から (4,0)、(8,0)、(9,3) と進めます。残差は18、14、10、6と減り、ここからは最後の補完に切り替えられます。ここまでの各手のマンハッタン距離はすべて4です。
最後を1手または2手で補完する
残差 R<=2K になったら、次の3通りに分けます。
R=K：目標をそのまま次の座標にします。Rが偶数：h=R/2、away=K-hと置きます。残差のある軸で目標へh進み、別の軸へ目標から離れる向きにaway進んだ中間点を作ります。原点側から中間点までの距離はh+away=K、中間点から目標までの距離も同じKです。R=0の場合も、いったん別軸へKだけ出て戻る2手として成立します。Rが奇数：到達可能なケースではKも奇数です。R>=Kなら目標方向へK進み、残差をR-Kという偶数にします。R<Kなら目標を同じ軸方向へK-Rだけ越える点を1つ置き、目標までの残差をK-Rという偶数にします。その後は上の2手補完を使います。
2手補完では、X方向に半分進める余地がなければY方向を使うようにしています。したがって中間点をどちらの軸に置いても、1手目と2手目の距離は K です。最後に必ず目標 (X,Y) を追加するため、各手の距離だけでなく終点も保証できます。
負の座標を特別扱いしない
コードは目標との差分 dx、dy の符号をそのまま使います。たとえば公式サンプル1の K=11、(X,Y)=(-1,2) では D=3 なので3手です。コードの一例は (-9,2)、(-5,9)、(-1,2) で、原点からの距離、各連続点の距離はすべて11です。公式の座標列と異なっていても、問題の出力条件を満たせば正しい出力です。
完全なPythonコード
入力をそのまま2行で読み、到達不能なら -1、到達可能なら手数と座標列を出力します。assert は、構成した座標列の長さが先に求めた最小手数と一致することを確認するために入れています。
import sys
def sgn(value):
return 1 if value >= 0 else -1
def append_two(path, cx, cy, tx, ty, k):
dx, dy = tx - cx, ty - cy
residual = abs(dx) + abs(dy)
halfway = residual // 2
away = k - halfway
if abs(dx) >= halfway:
px = sgn(dx) * halfway
py = -sgn(dy) * away if dy != 0 else away
else:
py = sgn(dy) * halfway
px = -sgn(dx) * away if dx != 0 else away
path.append((cx + px, cy + py))
path.append((tx, ty))
def solve():
k = int(input())
tx, ty = map(int, input().split())
distance = abs(tx) + abs(ty)
if k % 2 == 0 and distance % 2 == 1:
print(-1)
return
if distance == k:
path = [(tx, ty)]
else:
if distance < 2 * k:
strokes = 2 if distance % 2 == 0 else 3
else:
strokes = (distance + k - 1) // k
if (strokes * k - distance) % 2 == 1:
strokes += 1
path = []
cx = cy = 0
while abs(tx - cx) + abs(ty - cy) > 2 * k:
dx, dy = tx - cx, ty - cy
take_x = min(abs(dx), k)
cx += sgn(dx) * take_x
take_y = k - take_x
if take_y:
cy += sgn(dy) * take_y
path.append((cx, cy))
residual = abs(tx - cx) + abs(ty - cy)
if residual == k:
path.append((tx, ty))
elif residual % 2 == 0:
append_two(path, cx, cy, tx, ty, k)
else:
dx, dy = tx - cx, ty - cy
if residual >= k:
take_x = min(abs(dx), k)
px = sgn(dx) * take_x
take_y = k - take_x
py = sgn(dy) * take_y if take_y else 0
extra_point = (cx + px, cy + py)
else:
extra = k - residual
if dx != 0:
extra_point = (tx + sgn(dx) * extra, ty)
else:
extra_point = (tx, ty + sgn(dy) * extra)
path.append(extra_point)
append_two(path, extra_point[0], extra_point[1], tx, ty, k)
assert len(path) == strokes
print(len(path))
for x, y in path:
print(x, y)
if __name__ == '__main__':
solve()
コードの正しさと計算量
前半のループでは、現在位置から目標方向へ合計 K だけ移動するので、各手のマンハッタン距離は K、残差は K 減ります。残差が 2K 以下になった後は、R=K の直接移動か、偶数残差の2手補完を使います。奇数残差のときだけ追加の1手を置き、その後は偶数残差として同じ補完に入ります。よって列の最後は必ず (X,Y) です。
各手が距離 K なので、n 手の列には合計距離の下限 D<=nK があり、座標和の偶奇から nK-D が偶数である必要があります。コードが選ぶ strokes はこの2条件を満たす最小値で、構成列の長さを assert len(path) == strokes で照合します。
制約は 1<=K<=10^9、-10^5<=X,Y<=10^5 なので D<=200000 です。最小手数と出力する座標数も200000以下です。前半の走査と座標の出力は手数 n に比例して O(n) 時間、path を保存する追加メモリは O(n) です。大きな入力でも、計算量の中心は問題が要求する出力行数そのものです。
公式サンプルは座標列の意味で確認する
この問題では、公式サンプルに書かれた座標列だけが正解ではありません。座標列は複数あり得るため、出力を文字列として完全一致させず、問題文の意味条件で確認します。
| 公式入力 | 手数の判断 | サンプルの読み方 |
|---|---|---|
K=11, (X,Y)=(-1,2) |
D=3、D<2K、D は奇数なので3手 |
公式の3手の座標列は一例です。コードの列が別の点を通っても、各距離と終点を確認します。 |
K=4600, (X,Y)=(52,149) |
D=201 は奇数、K は偶数 |
到達不能条件に一致するため -1 です。 |
K=4, (X,Y)=(9,9) |
D=18、ceil(D/K)=5、5K-D=2 は偶数 |
公式の5手の列は一例です。コードの列 (4,0),(8,0),(9,3),(10,6),(9,9) も同じ条件を満たします。 |
意味検証では、-1 の場合は K が偶数かつ D が奇数であることだけを確認します。到達可能な場合は、先頭の s と続く s 個の座標を読み、行数が一致すること、原点から各点までの連続するマンハッタン距離がすべて K であること、最後の点が (X,Y) であること、s が上で求めた最小手数であることを確認します。これなら公式出力との座標列の違いを誤りと判定せず、問題が要求する構成そのものを検査できます。
