概要

1次元の数直線上で、高橋君と青木君をそれぞれ目標の地点まで最小手数で移動させる問題です。隣接する2マスの「交換」操作を用いて、一方が移動する、あるいは二人が位置を入れ替わることで目標を目指します。

考察

この問題の鍵は、「高橋君と青木君の左右の位置関係が入れ替わる必要があるか」という点にあります。

1. 位置関係が変わらない場合

初期位置が \(A < B\) かつ目標位置が \(C < D\) の場合（またはその逆）、二人は一度もすれ違うことなく目標地点に到達できます。 このとき、高橋君は \(A \to C\)、青木君は \(B \to D\) へ最短距離で移動すればよいため、必要な操作回数はそれぞれの移動距離の和になります。 $\(\text{操作回数} = |A - C| + |B - D|\)$

2. 位置関係が入れ替わる場合

初期位置が \(A < B\) なのに目標位置が \(C > D\) である場合（またはその逆）、二人は必ずどこかのタイミングで「すれ違う（入れ替わる）」必要があります。

隣接するマス \(x\) と \(x+1\) で二人が入れ替わる状況を考えます。 1. 高橋君がマス \(x\)、青木君がマス \(x+1\) に移動する。 2. マス \(x\) と \(x+1\) を交換する（操作回数 1）。 3. 入れ替わった後、高橋君が \(x+1 \to C\)、青木君が \(x \to D\) へ移動する。

このとき、高橋君が \(A < B\) の位置にいたとすると、合計の操作回数は以下のようになります： $\(\text{コスト} = |x - A| + |(x+1) - B| + 1 + |C - (x+1)| + |D - x|\)\( これを整理すると： \)\(\text{コスト} = |x - A| + |x - (B-1)| + |x - (C-1)| + |x - D| + 1\)$

この式を最小にする整数 \(x\) を見つける必要があります。これは、数直線上の4つの点 \(\{A, B-1, C-1, D\}\) からの距離の総和を最小化する問題（中央値を求める問題のバリエーション）に帰着されます。

アルゴリズム

1. 位置関係の判定: \((A < B) == (C < D)\) が真ならば、入れ替わりは不要です。
   • 答えは \(|A - C| + |B - D|\) です。
2. 入れ替わりが必要な場合:
   • 4つの値 \(\{A, B-1, C-1, D\}\) を用意します（\(A > B\) の場合は \(B+1, C+1\) になるよう適切に調整するか、一般化して考えます）。
   • コード上では、入れ替わりが発生する際の「左側の位置」を基準にするため、以下の4点をソートして \(a_0 \leq a_1 \leq a_2 \leq a_3\) とします。
     • \(A\) と \(C\) のうち、入れ替わり前に左側にくるべき方と、入れ替わり後に左側にくるべき方。
     • 具体的には、\(A < B\) のとき \(\{A, B-1, C-1, D\}\)、 \(A > B\) のとき \(\{A-1, B, C, D-1\}\) のようになります。
   • 4点からの距離の総和の最小値は \((a_3 + a_2) - (a_1 + a_0)\) で求められます。
   • これに交換自体のコスト \(1\) を加えたものが答えです。

計算量

• 時間計算量: \(O(1)\)
  • 数値の比較、ソート（要素数4）、基本的な算術演算のみであるため、定数時間で終了します。
• 空間計算量: \(O(1)\)
  • 変数数個分のメモリしか使用しません。

実装のポイント

• 64bit整数型: 座標が \(10^{18}\) に達するため、C++では long long 型、Pythonでは通常の整数型を使用する必要があります。

• 絶対値の計算: 距離を求める際に負の数にならないよう、絶対値関数 abs() を使用するか、大きい方から小さい方を引くように注意します。

• 4点の選び方: 入れ替わりが必要な場合の4点は、一方の座標を \(-1\) する（あるいはもう一方を \(+1\) する）ことで、「隣接した2マスにいる状態」を数学的に扱いやすくしています。

  ソースコード

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

/**
 * Problem Summary:
 * Two people, Takahashi (T) at A and Aoki (A) at B, want to move to C and D respectively.
 * The operation allows swapping contents of adjacent cells x and x+1.
 * This operation can move one person (if only one is present) or swap their positions 
 * (if both are present). Each operation costs 1.
 * 
 * Logic:
 * 1. If the relative order of Takahashi and Aoki remains the same ((A < B) == (C < D)):
 *    The minimum operations required is simply the sum of their individual distances:
 *    |A - C| + |B - D|. They can reach their targets without ever needing to pass 
 *    through each other's cell.
 * 
 * 2. If the relative order of Takahashi and Aoki must change ((A < B) != (C < D)):
 *    They must swap positions an odd number of times. To minimize operations, 
 *    they should swap exactly once.
 *    Suppose they swap at positions x and x+1.
 *    - To swap, they must first move to x and x+1.
 *    - After swapping, they move from x+1 and x to their respective targets.
 *    The total operations would be:
 *    (Steps for T to reach x and A to reach x+1) + 1 (swap) + (Steps for T from x+1 to C and A from x to D)
 *    = |x - A| + |(x+1) - B| + 1 + |C - (x+1)| + |D - x|
 *    = |x - A| + |x - (B-1)| + |x - (C-1)| + |x - D| + 1
 * 
 *    To minimize this, x should be the median of the set {A, B-1, C-1, D}.
 *    For four points a1 <= a2 <= a3 <= a4, the minimum value of sum(|x - ai|) 
 *    is (a4 + a3 - a2 - a1).
 *    Thus, the minimum operations is (a4 + a3 - a2 - a1) + 1.
 */

typedef long long ll;

int main() {
    // Optimize standard I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll A, B, C, D;
    if (!(cin >> A >> B >> C >> D)) return 0;

    // Check if the relative order of the two people is the same at the start and end
    if ((A < B) == (C < D)) {
        // Case 1: No relative order change needed
        ll diffAC = (A > C ? A - C : C - A);
        ll diffBD = (B > D ? B - D : D - B);
        cout << diffAC + diffBD << endl;
    } else {
        // Case 2: Relative order must change (exactly one swap is optimal)
        ll a[4];
        // The points are the start/end positions adjusted for the swap adjacency
        a[0] = (A < B ? A : B);
        a[1] = (A < B ? B : A) - 1;
        a[2] = (C < D ? C : D);
        a[3] = (C < D ? D : C) - 1;
        
        // Sort the four points to find the median range [a[1], a[2]]
        sort(a, a + 4);
        
        // The minimum sum of distances to four points a1, a2, a3, a4 is a4 + a3 - a2 - a1
        ll min_dist_sum = a[3] + a[2] - a[1] - a[0];
        cout << min_dist_sum + 1 << endl;
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。