Pythonで解く細胞融合問題 ― heapqを使った効率的なアルゴリズム実装

問題の概要

数値のリスト cells があるとします。このリストは、さまざまな細胞のサイズを表しています。

各反復処理において、最も大きい2つの細胞 a と b が次のルールに従って相互作用します。

• a = b の場合: 両方の細胞は死滅します。
• a ≠ b の場合: 2つの細胞は融合し、新しいサイズは floor((a + b) / 3)(小数点以下切り捨て)になります。

最終的に残った細胞のサイズを求めてください。すべての細胞が消滅した場合は -1 を返します。

具体例

入力が [20, 40, 40, 30] の場合、出力は 16 になります。

1. 1回目の反復:最大の2つである 40 と 40 は等しいため、両方とも死滅します。
2. 2回目の反復:残った 20 と 30 が融合し、floor((20 + 30) / 3) = floor(50 / 3) = 16 となります。

結果として、最後の細胞のサイズは 16 です。

解決のためのアプローチ

この問題を解くには、以下の手順に従います。

1. cells の各値を負の値に変換します。
2. 変換したリストでヒープを構築します。
3. ヒープに要素が2つ以上残っている間、以下を繰り返します。
   • ヒープから2つの要素を取り出し、符号を元に戻してそれぞれ first(最大値)、second(2番目に大きい値)とします。
4. first と second が等しくない場合は、floor((first + second) / 3) を再び負にしてヒープへ挿入します。
5. 処理終了後、ヒープに要素が残っていれば -cells[0] を返し、空であれば -1 を返します。

実装例

from heapq import heapify, heappop, heappush

class Solution:
    def solve(self, cells):
        # 各値を負に変換することで最大ヒープとして扱う
        cells = [-x for x in cells]
        heapify(cells)

        while len(cells) > 1:
            # 最大の2つの細胞を取り出す
            first, second = -heappop(cells), -heappop(cells)

            if first != second:
                # 融合後のサイズを計算してヒープに戻す
                heappush(cells, -((first + second) // 3))

        return -cells[0] if cells else -1


ob = Solution()
cells = [20, 40, 40, 30]
print(ob.solve(cells))

入力

[20, 40, 40, 30]

出力

16

計算量について

このアルゴリズムでは、各反復ごとにヒープへの挿入・削除を行います。ヒープ操作の計算量は O(log n) であるため、全体の時間計算量は O(n log n)、空間計算量は O(n) となります。これにより、大量のデータに対しても効率的に処理できます。