【博弈论】leetcode2029. 石子游戏 IX

题目：
Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。

• 如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。
• 如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。
  假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。
  
  
  思路：
  参考【宫水三叶】题解：https://leetcode-cn.com/problems/stone-game-ix/solution/gong-shui-san-xie-fen-qing-kuang-tao-lun-h1oa/
  下面分类讨论：
  1.s=0的石子数量为偶数，等价于没有s=0的石子
  (1)s=1的石子数量为0，只有s=2的石子可选，则A必败，状态序列（AB分别选择石子后的总和余数状态，从0开始计数，偶数位为A，奇数位为B）：2，1，0
  （注：若在此过程中，石子被用光，则B必胜，若未被用光，则B也必胜）
  (2)s=2的石子数量为0，只有s=1的石子可选，则A必败，状态序列：1，2，0
  (3)s=1和s=2均为0，则A必败
  (4)s=1和s=2均不为0，则当两种石子数量均充足时：
• 若A先选s=1的石子，则石子序列为：1，1，2，1，2，1，2，1，…，
  对应的余数状态序列为：1，2，1，2，1，2，1，2，…，
• 若A先选s=2的石子，则石子序列为：2，2，1，2，1，2，1，2，…，
  对应的余数状态序列为：2，1，2，1，2，1，2，1，…，
  最佳策略：A应选择数量较少的那一类石子（若两种石子数量相等，选哪种石子都可以），最终 B 会先进入「只能凑成 3 的倍数」的局面导致失败，即 A 必胜。

2.s=0的石子数量为奇数（可等价于只有一个），先手交换
当两种石子数量均充足时：

• 若先选s=1的石子，则石子序列为：1，0，1，2，1，2，1，2，1，…，
  对应的余数状态序列为：1，1，2，1，2，1，2，1，2，…，
• 若先选s=2的石子，则石子序列为：2，0，2，1，2，1，2，1，2，…，
  对应的余数状态序列为：2，2，1，2，1，2，1，2，1，…，
  （1） 两者数量差不超过 2：此时 B 可以确保自己为必胜态。
  （2）两者数量差超过 2 ：此时A 只要确保第一次选择数量较多的 s，不管 B 是否使用「优先使用 s = 0」的石子，A 都有足够次数数量多 s 来抵消换手（或是在 B 放弃使用 s = 0之后马上使用），最终都是 B 最先遇到「只能凑成 3 的倍数」的局面，即 A 获胜。

解答：

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        n=len(stones)
        #统计stone%3=0,1,2的个数
        cnt=[0]*3
        for stone in stones:
            cnt[stone%3]+=1
        if cnt[0]%2==0:
            if cnt[1]!=0 and cnt[2]!=0:
                return True
            else:
                return False
        else:
            if abs(cnt[1]-cnt[2])<=2:
                return False
            else:
                return True