PythonでサイズNのリング上の任意の点からA・Bまでの距離の合計を最小化する方法

問題概要

1からNまでの整数が円環状に並んだリングがあるとします。さらに、2つの整数 A と B が与えられます。ここで、リング上の任意の位置(これを X とします)に立ち、X から A までの距離と X から B までの距離の合計(Z = X から A への距離 + X から B への距離)を考えます。この合計 Z を最小化するような位置 X を選び、その値を返すのが目的です。ただし、X は A および B と同じ位置であってはならないという制約がある点に注意してください。

例えば、入力が N = 30、A = 10、B = 20 の場合、出力は 10 になります。これは、X = 15 を選ぶと、X から A までの距離が 5、X から B までの距離も 5 となり、合計距離は 5 + 5 = 10 になるためです。

解法アプローチ

この問題は、A と B の間の2つの経路(時計回りと反時計回り)の距離を比較することで解くことができます。手順は以下の通りです。

• a > b の場合、a と b を入れ替えます(a < b となるように整えます)。
• 時計回りの距離(clock_wise_dist)は「b - a」で求まります。
• 反時計回りの距離(counter_clock_wise_dist)は「(a - 1) + (n - b + 1)」で求まります。
• minimum_dist を clock_wise_dist と counter_clock_wise_dist の小さい方とします。
• minimum_dist が 1 と等しい場合(A と B が隣接している場合)、間に入る位置が存在しないため、3 を返します。
• それ以外の場合は minimum_dist を返します。

実装例

以下のPythonコードで実際の動作を確認できます。

def get_min_z(n, a, b):
    if (a > b):
        a, b = b, a
    clock_wise_dist = b - a
    counter_clock_wise_dist = (a - 1) + (n - b + 1)
    minimum_dist = min(clock_wise_dist, counter_clock_wise_dist)
    if (minimum_dist == 1):
        return 3
    return minimum_dist

n = 30
a = 10
b = 20
print(get_min_z(n, a, b))

入力

30, 10, 20

出力

10

まとめ

このアルゴリズムは、リング上の2点間の最短距離を時計回りと反時計回りの両方向で計算し、小さい方を採用するシンプルな手法です。計算量は O(1) であり、非常に効率的です。また、A と B が隣接している特殊なケースでは、間に立つことができないため、答えが 3 になる点にも注意しましょう。