Pythonで解く「ボブのゲーム」：全要素を偶数にする最小ターン数を求めるアルゴリズム

ボブのゲーム問題とは

友人のボブは、自分一人で次のようなゲームを楽しんでいます。まず、整数のリスト nums を用意します。各ターンで、ボブはリストから2つの要素を選び、それらを「選んだ2つの数の合計と等しい1つの正の整数」に置き換えます。そして、配列内のすべての数が偶数になった時点で勝利を宣言できるというルールです。

本記事では、ボブが勝利を宣言するまでに必要な最小ターン数を求める方法を解説します。なお、どのように操作してもすべてを偶数にできない場合は -1 を返します。

具体例

入力が [2, 3, 4, 9, 7, 13] の場合を考えてみましょう。このときの出力は 2 になります。手順は次のとおりです。

• まず 3 と 9 を選び、合計の 12 に置き換える
• 次に 7 と 13 を選び、合計の 20 に置き換える

こうすると配列は [2, 4, 12, 20] となり、すべての要素が偶数になります。わずか2ターンで勝利条件を満たせるのです。

解き方のアプローチ

この問題のカギは奇数の個数に着目することです。2つの数を合計して1つに置き換える操作では、1ターンにつき最大で2つの奇数を消去できます。したがって、解法の手順は以下のようになります。

• まず、nums から奇数の要素だけを取り出したリスト a を作成します。

• a の要素数(=奇数の個数)が偶数であれば、len(a) / 2 を返します。奇数同士をペアにして合計(必ず偶数になる)に置き換えていけば、すべての要素を偶数にできるためです。

• 奇数の個数が奇数であれば、どのように組み合わせても1つ余った奇数を消せないため、-1 を返します。

Pythonでの実装例

それでは、理解を深めるために実際のコードを見てみましょう。

class Solution:
    def solve(self, nums):
        a = [x for x in nums if x % 2 == 1]
        if len(a) % 2 == 0:
            return len(a) // 2
        return -1

ob = Solution()
print(ob.solve([2, 3, 4, 9, 7, 13]))

入力

[2, 3, 4, 9, 7, 13]

出力

2

まとめ

この問題は、リスト内包表記で奇数だけを抽出し、その個数の偶奇を判定するだけで答えが求まる、シンプルながら思考力が試される良問です。計算量は O(n) と非常に効率的で、要素数が多いリストでも高速に動作します。