Pythonでk個の数値を削除した後に隣接する値の最大差を最小化する方法

問題の概要

昇順にソートされた数値リスト nums が与えられます。このリストから k 個の値を削除し、残った要素における隣接する2つの値の差の最大値ができるだけ小さくなるようにします。そして、その最小化された最大差を求めるのが目的です。

入力例

たとえば、nums = [15, 20, 30, 400, 1500]、k = 2 の場合を考えてみましょう。[400, 1500] を削除すると、残りのリストは [15, 20, 30] になります。このとき隣接する値の差は 5 と 10 であり、最大差は 10 です。これが求める出力となります。

解法の考え方

この問題は、動的計画法(DP)を用いて解くことができます。具体的な手順は以下の通りです。

• abs_diff の作成: nums 内の連続する各要素同士の差を計算し、リストとして保存します。
• 再帰関数 dp(i, j, cnt) の定義: 範囲 [i, j] に含まれる差の中から、さらに cnt 個の差を取り除いたときの最大差を返します。
• cnt が 0 の場合(これ以上削除できない場合):
  • m := 0 で初期化します。
  • i から j までの範囲でループを行い、m := max(m, abs_diff[k]) を計算します。
  • 最終的な m を返します。
• cnt が 0 より大きい場合は、dp(i + 1, j, cnt - 1) と dp(i, j - 1, cnt - 1) のうち小さい方を返します。これは、範囲の左端または右端の差を取り除いた2通りのケースを比較することを意味します。
• メイン処理では、dp(0, len(abs_diff) - 1, k) を返すことで答えを得ます。

Pythonでの実装例

以下のコードは、上記のアルゴリズムを実際に実装したものです。

class Solution:
    def solve(self, nums, k):
        abs_diff = [nums[i] - nums[i - 1] for i in range(1, len(nums))]

        def dp(i, j, cnt):
            if cnt == 0:
                m = 0
                for k in range(i, j + 1):
                    m = max(m, abs_diff[k])
                return m
            return min(dp(i + 1, j, cnt - 1), dp(i, j - 1, cnt - 1))

        return dp(0, len(abs_diff) - 1, k)

ob = Solution()
nums = [15, 20, 30, 400, 1500]
k = 2
print(ob.solve(nums, k))

入力

[15, 20, 30, 400, 1500], 2

出力

10

まとめ

この記事では、ソート済みリストから k 個の値を削除したときに、隣接する値の最大差を最小化する問題を Python で解く方法を紹介しました。連続する要素間の差を事前に計算しておき、再帰的なDPによって削除する位置の組み合わせを探索することで、効率的に答えを求めることができます。