Pythonで方程式 yi + yj + |xi − xj| の最大値を求めるプログラム

2次元平面上の座標点を格納した配列 points があるとします。各要素は points[i] = (x_i, y_i) という形式で表され、点は x 座標の昇順にソートされているため、すべての 1 <= i < j <= 点数 について x_i < x_j が成り立ちます。さらに、整数値 k も与えられます。

このとき、|x_i - x_j| <= k かつ 1 <= i < j <= 点数 を満たすすべての組み合わせの中から、方程式 y_i + y_j + |x_i - x_j| の最大値を求めるのが目的です。

たとえば、入力が points = [[2,4],[3,1],[6,11],[7,-9]]、k = 1 の場合、出力は 6 になります。最初の2つの点は条件 |x_i - x_j| <= 1 を満たしており、方程式に代入すると 4 + 1 + |2 - 3| = 6 となります。同様に、3番目と4番目の点も条件を満たしますが、11 + (-9) + |6 - 7| = 3 しか得られないため、最大値は 6 になります。

解法のアプローチ

この問題は、左右2つのポインタ（インデックス）を使った「スライディングウィンドウ」的な手法で効率的に解くことができます。手順は以下の通りです。

• left := 0、right := 1 で初期化する

• max_value := -inf（負の無限大）で初期化する

• right が points のサイズ未満である間、以下を繰り返す:

  • (xl, yl) := points[left]

  • (xr, yr) := points[right]

  • diff := |xr - xl| を計算する

  • left == right の場合: right := right + 1

  • diff <= k の場合:

    • m := yl + yr + diff を計算する

    • max_value := max(max_value, m) で最大値を更新する

    • yl >= yr - diff の場合: right := right + 1

    • それ以外の場合: left := left + 1

  • それ以外（diff > k の場合）: left := left + 1

• 最後に max_value を返す

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def solve(points, k):
   left, right = 0, 1
   max_value = float('-inf')

   while right < len(points):
      xl, yl = points[left]
      xr, yr = points[right]

      diff = abs(xr - xl)
      if left == right:
         right += 1
      elif diff <= k:
         m = yl + yr + diff
         max_value = max(max_value, m)
         if yl >= yr - diff:
            right += 1
         else:
            left += 1
      else:
         left += 1

   return max_value

points = [[2,4],[3,1],[6,11],[7,-9]]
k = 1
print(solve(points, k))

入力

[[2,4],[3,1],[6,11],[7,-9]], 1

出力

6