Pythonでk個の塔を同じ高さに揃えるために必要な最小レンガ数を求めるプログラム

問題の概要

塔の高さが格納されたリストと正の整数 k が与えられたとします。この中から k 個の塔を選び、レンガを追加してすべて同じ高さに揃えたいと考えます。ただし、使用するレンガの数はできるだけ少なくしたいものです。ここでは、k 個の塔を選んで同じ高さにするときに必要となるレンガの最小数を求める方法を解説します。

たとえば、heights = [5, 8, 32, 15, 41]、k = 3 という入力の場合、出力は 17 になります。これは、高さ 5、8、15 の3つの塔を選び、すべて高さ 15 に揃えると (15−5) + (15−8) + (15−15) = 17 個のレンガが必要になるためです。

解き方のアプローチ

この問題は、次の手順で解くことができます。

• リスト heights を昇順にソートする
• ans を無限大(float("inf"))で初期化する
• s(スライディングウィンドウの合計値)を 0 で初期化する
• リスト内の各インデックス i と値 x について以下を繰り返す:
  • s に x を加算する
  • i >= k の場合、s から heights[i − k] を減算し、ウィンドウサイズを k に保つ
  • i >= k − 1 の場合、ans と (x × k − s) の小さい方を ans に代入する
• 最後に ans を返す

ソート済みのリストに対してスライディングウィンドウを適用することで、各ウィンドウ内の最大値(右端の値 x)に合わせて k 個の塔を揃えたときのコストを効率的に計算できます。x × k は「全塔を高さ x にした場合の総高さ」、s は「現在のウィンドウ内の実際の総高さ」なので、その差がまさに必要なレンガ数になります。

実装例

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

class Solution:
    def solve(self, heights, k):
        heights.sort()
        ans = float("inf")
        s = 0
        for i, x in enumerate(heights):
            s += x
            if i >= k:
                s -= heights[i - k]
            if i >= k - 1:
                ans = min(ans, x * k - s)
        return ans

ob = Solution()
heights = [5, 8, 32, 15, 41]
k = 3
print(ob.solve(heights, k))

入力

[5, 8, 32, 15, 41], 3

出力

17

計算量について

このアルゴリズムの時間計算量は、ソートに O(n log n)、その後のループ処理に O(n) かかるため、全体として O(n log n) となります。また、入力リストをその場でソートする場合、追加の空間計算量は O(1) で済みます。全ての組み合わせを試す非効率な方法と比べ、非常に高速に答えを導き出せるのがポイントです。