【Python】キャンディー削除ゲームで先手プレイヤーが勝つかどうかを判定するプログラム

問題の概要

数値のリスト candies があるとします。あるプレイヤー（player1）が友人（player2）と対戦するゲームを行います。各ターンで、プレイヤーは「同じ値が隣り合っている2つのキャンディー」を選んで取り除くことができます。そして、キャンディーを取り除けなくなった方の負けです。player1が先手であるとき、player1が勝利するかどうかを判定してください。

例えば、入力が nums = [2, 2, 5] の場合、出力は True になります。player1が先に「2」のペアを取り除けば、残った [5] からは相手が何も取り除けなくなるためです。

解法のアプローチ

この問題の鍵となるのは、「取り除けるペアの総数」はプレイヤーの戦略に関係なく一定だという点です。そこで、スタックを使って隣接する同じ値のペアを数え、その手数（turns）が奇数であれば先手のplayer1が最後の一手を打てるので勝ち、偶数であれば負けると判定できます。

具体的な手順は以下の通りです。

• stack（スタック）を新しく作成する

• turns（手数）を 0 で初期化する

• nums の各要素 num について以下を繰り返す

  • スタックが空でなく、スタックのトップが num と同じ値の場合

    • スタックからポップする

    • turns を 1 増やす

  • それ以外の場合

    • num をスタックにプッシュする

• turns が奇数なら true を、偶数なら false を返す

実装例

class Solution:
    def solve(self, nums):
        stack = []
        turns = 0
        for num in nums:
            if stack and stack[-1] == num:
                stack.pop()
                turns += 1
            else:
                stack.append(num)

        return bool(turns & 1)

ob = Solution()
nums = [2, 2, 5]
print(ob.solve(nums))

入力

[2, 2, 5]

出力

True

コードのポイント

戻り値の bool(turns & 1) は、ビット演算 AND を使って turns の奇偶を判定しています。turns が奇数（最下位ビットが1）の場合に True となり、先手のplayer1の勝利を意味します。このアルゴリズムの計算量は O(n)、空間計算量も O(n) であり、非常に効率的です。