Pythonで色のマージ後に残る最小個数を求めるプログラム

問題概要

赤(R)、緑(G)、青(B)の3種類の色からなるリストを考えます。隣り合う異なる2つの色は、残りの「第3の色」1個に変換(マージ)できます。この変換を好きな順序で何度でも繰り返してよいとき、最終的に残る要素数の最小値を求めるのがこの問題です。

たとえば入力が colors = ["G", "R", "G", "B", "R"] の場合、次のように変換を進めることで最終的に1個まで減らせます。したがって出力は 1 となります。

解き方のアプローチ

一見すると状態探索が必要そうな問題ですが、実はXOR(排他的論理和)を使ったシンプルな判定だけで答えが求まります。手順は以下の通りです。

• n := 色リストの長さ
• リスト内の色が1種類しかない場合は、マージが一度も行えないため n をそのまま返す
• n <= 1 の場合も n をそのまま返す
• x := 0 で初期化し、d := {("R", 1), ("G", 2), ("B", 3)} という対応表を用意する
• colors 内の各色 c について、x := x XOR d[c] を累積計算する
• x が 0 なら 2 を返し、それ以外なら 1 を返す

なぜXORで判定できるのか

R=1(二進数で01)、G=2(10)、B=3(11) と対応させると、同じ色が2回現れるたびにXORが打ち消し合います。つまり x の値は、各色の出現回数が偶数か奇数かという偶奇の情報だけで決まります。

x が 0 になるのは、3色すべての出現回数の偶奇が一致している場合(すべて偶数、またはすべて奇数)です。このケースでは、どんな順序でマージしても最終的に2個残り、それ以上は減らせません。逆に偶奇が一致しない場合は、適切な順序でマージを重ねることで必ず1個まで減らせます。

Pythonでの実装例

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

class Solution:
    def solve(self, colors):
        n = len(colors)
        if len(set(colors)) == 1:
            return n
        if n <= 1:
            return n
        x = 0
        d = {"R": 1, "G": 2, "B": 3}
        for qux in colors:
            x ^= d[qux]
        return 2 if x == 0 else 1

ob = Solution()
colors = ["G", "R", "G", "B", "R"]
print(ob.solve(colors))

入力

["G", "R", "G", "B", "R"]

出力

1