ユニークな塔の合計高さを最大化する：Pythonでの貪欲法による解法

ユニークな塔の合計高さを最大化する問題（LeetCode 3301）では、各塔の最大高さが与えられます。すべての塔に、その最大値を超えない正の整数の高さを割り当て、しかもすべての高さを異なるものにする必要があります。可能な合計高さの最大値を返し、それが不可能な場合は -1 を返します。ソート後に貪欲法で解くと O(n log n) で求まります。

問題

配列 maximumHeight が与えられ、maximumHeight[i] は塔 i が取りうる最大の高さを表します。次の条件を満たすように height[i] を選びます。

• 1 <= height[i] <= maximumHeight[i]
• すべての height[i] の値が異なる

可能な合計の最大値を返し、有効な割り当てが存在しない場合は -1 を返します。

例:

考え方

合計を大きくするには、どの塔もできるだけ高くしたいところです。高さは異なる必要があるので、順番を考えます。最も高い最大値を持つ塔に最大の値を割り当て、次の塔にはその次に大きい値を割り当てる、というように進めます。

1. 最大値を降順にソートします。
2. 最初の塔にはその最大値をそのまま割り当てます。
3. 以降の各塔には min(その最大値, 直前の高さ - 1) を割り当てます。
4. 割り当てた高さが 0 以下になったら、有効な割り当ては存在しないので -1 を返します。
5. 高さを合計します。

def maximum_total_sum(maximum_height):
    total = 0
    limit = float("inf")
    for m in sorted(maximum_height, reverse=True):
        h = min(m, limit - 1)
        if h <= 0:
            return -1
        total += h
        limit = h
    return total

[2,3,4,3] で追跡すると、降順にソートすると [4,3,3,2] になります。高さは 4、次に min(3, 3) = 3、次に min(3, 2) = 2、次に min(2, 1) = 1 となります。合計は 10 です。

貪欲法がうまくいく理由

交換論法で示せます。ある最適解が、より大きい最大値を持つ塔により小さい高さを割り当て、より小さい最大値を持つ塔により大きい高さを割り当てているとします。この 2 つの高さを交換しても、どちらも制限内に収まります。大きい最大値を持つ塔は、小さい方の塔が取りうるどんな値でも取れるからです。また合計も変わりません。したがって、ある最適解はソートされた最大値と同じ順序で高さを割り当てています。

順序が決まれば、各塔は自身の最大値を超えられず、また直前の塔より 1 小さい値を超えられません。ちょうどその上限を取るのが最善です。それより低い高さにすると、今の合計が減るだけでなく、後の塔の上限もこの高さに依存するため、後の塔の上限も下がってしまい、助けにはなりません。

また、2,000 個のランダムな小さい配列に対して、すべての割り当てを総当たりで調べる探索とコードを照合したところ、答えは一致しました。

計算量

• 時間: O(n log n)。ソートが支配的です。ループは O(n) です。
• 空間: その場でソートすれば追加は O(1)、ソート済みのコピーを使うなら O(n) です。

別の見方: 値の個数を数える

-1 になるケースを別の角度から見ると、ソートされた最大値を m1 >= m2 >= ... >= mn としたとき、有効な割り当てが存在するのは、各 i について i 番目に大きい最大値が少なくとも n - i + 1 である場合だけです。その値以下で使える異なる正の値がそれだけ必要だからです。ループはこれを進めながら確認しています。

エッジケース

Java や C++ では、大きい最大値を持つ塔が多いと合計が 32 ビットを超えることがあるので、long を使います。

面接での説明の仕方

1. -1 のケースも含めて制約を言い直します。
2. 高い塔を異なる高さで作りたいので、最大値の大きい方から処理すると述べます。
3. ルールを述べます。各高さは、その最大値と直前の高さ - 1 の小さい方です。
4. 理由を説明します。塔の間で高さを交換しても得にならず、各選択は可能な最大値です。
5. 計算量とオーバーフローの注意点を伝えます。
6. [2,2,1]、要素が 1 つの場合、すべて同じ値の場合でテストします。

関連する練習

似た貪欲法とソートの問題には、Assign Cookies や Minimum Number of Arrows to Burst Balloons があります。練習の組み立て方については Blind 75 学習プラン と AI LeetCode チューターガイド を、復習の習慣については コーディング面接アシスタントガイド をご覧ください。

練習するときは、交換論法を声に出して説明しましょう。模擬面接の記録を見れば、理由を述べたのかコードだけだったのかがわかります。実際の評価では、AI ツールに関する雇用主のルールに従ってください。