Pythonで解く「フェアキャンディスワップ」問題：アルゴリズムと実装をわかりやすく解説

この記事では、Pythonを使って「フェアキャンディスワップ（公平なキャンディ交換）」問題を解く方法を解説します。数式ベースのシンプルなアプローチとセット（集合）による高速な探索を組み合わせることで、効率よく答えを導き出します。

問題の概要

AさんとBさんは友人同士で、それぞれ異なるサイズのキャンディバーを持っています。ここで、A[i]はAさんが持っているi番目のキャンディバーのサイズ、B[j]はBさんが持っているj番目のキャンディバーのサイズを表します。

二人は友人なので、お互いにキャンディバーを1本ずつ交換し、交換後に両者の持つキャンディの総量（所有するキャンディバーのサイズの合計）が等しくなるようにしたいと考えています。

求めるのは整数配列 ans です。ans[0] にはAさんが交換に出すべきキャンディバーのサイズを、ans[1] にはBさんが交換に出すべきキャンディバーのサイズを格納します。条件を満たす答えが複数存在する場合は、そのうちのどれか1つを返せば問題ありません。

例：A = [1, 2]、B = [2, 3] の場合、出力は [1, 2] となります。

• Aさんの合計：1 + 2 = 3
• Bさんの合計：2 + 3 = 5
• Aが「1」を出し、Bが「2」を受け取ると…A = [2, 2]、B = [1, 3] となり、両者の合計が4で一致します。

解法の考え方

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

• Aの合計値からBの合計値を引いた差を求め、それを2で割った整数部分を diff とします。
• Bをセット（set）に変換して、要素の存在確認をO(1)で行えるようにします。
• Aの各要素 i について以下を判定します。
  • i - diff がBのセットに含まれていれば、[i, i - diff] を返します。

なぜこれで正しいのでしょうか？ 交換後の合計が等しくなるためには、「Aが出すサイズ − Bが出すサイズ ＝ diff」という関係が必要だからです。つまり、Aのあるキャンディ i に対して、B側の候補は必ず i - diff になります。

実装例

それでは、実際のコードを見てみましょう。

class Solution(object):
    def fairCandySwap(self, A, B):
        diff = (sum(A) - sum(B)) // 2
        B = set(B)
        for i in A:
            if i - diff in B:
                return [i, i - diff]

ob1 = Solution()
print(ob1.fairCandySwap([1, 2], [2, 3]))

入力

[1, 2]
[2, 3]

出力

[1, 2]

計算量の分析

• 時間計算量：O(n + m)。ここでnはAの要素数、mはBの要素数です。sumの計算にO(n + m)、セットへの変換にO(m)、Aの走査とセットの参照にO(n)かかります。
• 空間計算量：O(m)。Bをセットとして保持するための追加メモリが必要です。

全ペアを総当たりするO(n × m)の素朴な解法と比べて、この手法は大幅に効率的であり、大きな入力でも高速に動作します。