概要

2人が無限に長い数直線上のマスに立っており、隣接マスの中身を交換する操作で目標配置にする最小回数を求めます。

ポイントは、2人の左右の順序が最初と最後で同じか、逆になるかで場合分けすることです。

考察

操作には次の2種類があります。

• 人と空きマスを交換する
  → その人が隣に1マス移動する
• 2人が隣り合っているときに交換する
  → 2人の左右関係が入れ替わる

ここで重要なのは、2人の左右関係が変わるのは、2人を直接交換したときだけという点です。

初期位置を小さい順に

\( a < b \)

目標位置を小さい順に

\( c < d \)

とします。

左右関係が変わらない場合

例えば、最初も最後も高橋君が青木君より左にいる場合です。

この場合、2人を直接交換する必要はありません。
単に左にいる人を左の目標位置へ、右にいる人を右の目標位置へ移動させればよいです。

したがって答えは

\( |a-c| + |b-d| \)

です。

2人を直接交換しても、占有されているマスの集合は変わらないため、最短にはなりません。

左右関係が逆になる場合

この場合、どこかで必ず2人を直接交換する必要があります。

2人を交換する操作が、マス \(x\) と \(x+1\) の間で行われたとします。

交換直前には、

• 初めに左にいた人が \(x\)
• 初めに右にいた人が \(x+1\)

にいます。

そこまでの移動コストは

\( |a-x| + |b-(x+1)| \)

です。

その後、2人を直接交換するのでコストが \(1\) かかります。

交換後は左右関係が目標と一致するので、

• 左側の人を \(c\)
• 右側の人を \(d\)

へ動かせばよく、そのコストは

\( |x-c| + |x+1-d| \)

です。

よって、交換位置を \(x\) としたときの総コストは

\( |a-x| + |b-(x+1)| + 1 + |x-c| + |x+1-d| \)

です。

これを整理すると、

\( 1 + |x-a| + |x-(b-1)| + |x-c| + |x-(d-1)| \)

になります。

つまり、以下の4つの値に対する距離の和を最小化すればよいです。

\( a,\ b-1,\ c,\ d-1 \)

4つの値を小さい順に

\( v_0 \leq v_1 \leq v_2 \leq v_3 \)

とすると、

\( |x-v_0| + |x-v_1| + |x-v_2| + |x-v_3| \)

の最小値は

\( (v_3-v_0) + (v_2-v_1) \)

になります。

これは、\(x\) を \(v_1\) から \(v_2\) の間に取ると最小になるためです。

したがって左右関係が逆になる場合の答えは

\( (v_3-v_0) + (v_2-v_1) + 1 \)

です。

アルゴリズム

1. 初期位置 \(A, B\) を小さい順に並べて \(a, b\) とする
2. 目標位置 \(C, D\) を小さい順に並べて \(c, d\) とする
3. 初期状態と目標状態で左右関係が同じか調べる
   • 具体的には \((A < B) = (C < D)\) かを見る
4. 左右関係が同じなら

\( |a-c| + |b-d| \)

を出力する

1. 左右関係が逆なら

   • \(a, b-1, c, d-1\) を配列に入れてソートする
   • ソート後の配列を \(v\) として

   \( (v_3-v_0) + (v_2-v_1) + 1 \)

   を出力する

計算量

• 時間計算量: \(O(1)\)
• 空間計算量: \(O(1)\)

4個の値をソートするだけなので、実質的に定数時間です。

実装のポイント

• 座標は \(10^{18}\) 程度まで大きいので、シミュレーションはできません。
• Python では整数のオーバーフローを気にする必要はありません。
• C++ などで実装する場合は long long を使います。
• 左右関係の判定は、以下のように書けます。

if (A < B) == (C < D):
    ...

• 左右関係が逆の場合に使う値は \(a, b-1, c, d-1\) です。
  \(b-1\) や \(d-1\) が出てくるのは、交換がマス \(x\) と \(x+1\) の間で行われるためです。

  ソースコード

import sys

A, B, C, D = map(int, sys.stdin.readline().split())

a, b = (A, B) if A < B else (B, A)
c, d = (C, D) if C < D else (D, C)

if (A < B) == (C < D):
    ans = abs(a - c) + abs(b - d)
else:
    v = [a, b - 1, c, d - 1]
    v.sort()
    ans = (v[3] - v[0]) + (v[2] - v[1]) + 1

print(ans)

---

この解説は gpt-5.5-high によって生成されました。