2029. 石子游戏 IX : 分情况讨论博弈题

题目描述

这是 LeetCode 上的 2029. 石子游戏 IX ，难度为 中等。

Tag : 「博弈论」

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

如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 33 整除，那么该玩家就 输掉游戏 。 如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。 假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。

示例 1：

输入：stones = [2,1]
输出：true
解释：游戏进行如下：
- 回合 1：Alice 可以移除任意一个石子。
- 回合 2：Bob 移除剩下的石子。 
已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。
复制代码

示例 2：

输入：stones = [2]
输出：false
解释：Alice 会移除唯一一个石子，已移除石子的值总和为 2 。 
由于所有石子都已移除，且值总和无法被 3 整除，Bob 获胜。
复制代码

示例 3：

输入：stones = [5,1,2,4,3]
输出：false
解释：Bob 总会获胜。其中一种可能的游戏进行方式如下：
- 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
- 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。
- 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。
- 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.
- 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.
Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜。
复制代码

提示：

• 1 <= stones.length <= 10^51<=stones.length<=105
• 1 <= stones[i] <= 10^41<=stones[i]<=104

分情况讨论博弈

为了方便，我们用 A 来代指 Alice，用 B 带代指 Bob。

A 只有一种获胜方式，是使得 B 在选石子时凑成 33 的倍数；而 B 除了能够通过让 A 凑成 33 的倍数以外，还能通过让游戏常规结束来获胜。

因此整个游戏过程，我们只需要关心「已被移除的石子总和」和「剩余石子个数/价值情况」即可。

更进一步的，我们只需关心已被移除的石子总和是否为 33 的倍数，以及剩余石子的价值与已移除石子总和相加是否凑成 33 的倍数即可。

所以我们可以按照石子价值除以 33 的余数分成三类，并统计相应数量。

不失一般性考虑，某个回合开始前，已移除的石子总和状态为 xx（共三种，分别为除以 33 余数为 00、11 和 22，其中当状态为 00，且非首个回合时，说明凑成 33 的倍数，游戏结束），剩余石子价值除以 33 的余数 ss 分别为 00、11 和 22。

首先如果当前 x = 1x=1 时，不能选择 s = 2s=2 的石子，否则会导致凑成总和为 33 的倍数而失败；同理 x = 2x=2 时，不能选择 s = 1s=1 的石子；而选择 s = 0s=0 的数字，不会改变 xx 的状态，可看做换手操作。

同时成对的 s = 0s=0 的等价于没有 s = 0s=0 的石子（双方只需要轮流选完这些 s = 0s=0 的石子，最终会回到先手最开始的局面）；而选择与 xx 相同的 ss 会导致 xx 改变（即 x = 1x=1 时，选择 s = 1s=1 的石子，会导致 x = 2x=2；而 x = 2x=2 时，选 s = 2s=2 的石子，会导致 x = 1x=1）。

明确规则后，是分情况讨论的过程：

• s = 0s=0 的石子数量为偶数：此时等价于没有s = 0s=0的石子，我们只需要关心s = 1s=1和s = 2s=2即可：

• s = 1s=1 的石子数量为 00： 这意味着 A 开始选择的只能是 s = 2s=2，此时交给 B 的局面为「x = 2x=2、剩余石子只有 s = 2s=2」，此时 B 只能选 s = 2s=2 的石子，由于 x = 2x=2 且选择的石子 s = 2s=2，因此交由回 A 的局面为「x = 1x=1，剩余是在只有 s = 2s=2」，因此游戏继续的话 A 必败，同时如果在该过程的任何时刻石子被取完，也是 B 直接获胜，即 A 仍为必败；
  
• s = 2s=2 的石子数量为 00：分析同理，A 只能选 s = 1s=1，此时交给 B 的局面为「x = 1x=1、剩余石子只有 s = 1s=1」，此时 B 只能选 s = 1s=1 的石子，由于 x = 1x=1 且选择的石子 s = 1s=1，因此交由回 A 的局面为「x = 2x=2，剩余是在只有 s = 1s=1」，因此游戏继续的话 A 必败，同时如果在该过程的任何时刻石子被取完，也是 B 直接获胜，即 A 仍为必败；
  
• s = 1s=1 和 s = 2s=2 的石子数量均不为 00：A 选数量不是最多的一类石子，B 下一回合只能选择相同类型的石子（或是无从选择导致失败），然后游戏继续，最终 B 会先进入「只能凑成 33 的倍数」的局面导致失败，即 A 必胜。
  

• s = 0s=0 的石子数量为奇数：此时等价于有一次换手机会，该换手机会必然应用在「对必败局面进行转移」才有意义，因此只有s = 1s=1和s = 2s=2的石子数量差大于22，A的先手优势不会因为存在换手机会而被转移：

• 两者数量差不超过 22：此时B可以利用「对方凑成33的倍数必败」规则和「优先使用s = 0s=0石子」权利来进入确保自己为必胜态：

• 举个 🌰，当 s = 1s=1 和 s = 2s=2 的石子数量相等，虽然有 s = 0s=0 的石子，A 先手，但是 A 的首个回合必然不能选 s = 0s=0，否则马上失败结束，因此 A 只能选 s = 1s=1 或 s = 2s=2，此时 B直接选择 s = 0s=0 的石子，交由给 A 的局面 xx 没有发生改变，A 只能选择与首个回合相同的 ss 游戏才能继续，因此局面会变为「B 先手、s = 1s=1 和 s = 2s=2 的石子数量差为 22」，游戏继续，最终 A 会先遇到「只能凑成 33 的倍数」的局面，即 B 必胜。
  
• 两者数量差不超过 22：此时无论 A 选择数量较少或较多的 s，B 都在第二回合马上使用 s = 0s=0 的石子进行换手，A 只能继续选与第一回合相同类型的的石子，游戏才能进行，最终 A 会先遇到「只能凑成 33 的倍数」或「石子被取完」的局面，即 B 必胜。
  

• 两者数量差超过 22 ：此时即使 A 只要确保第一次选择数量较多的 ss，不管 B 是否使用「优先使用 s = 0s=0」的石子，A 都有足够次数数量多 ss 来抵消换手（或是在 B 放弃使用 s = 0s=0 之后马上使用），最终都是 B 最先遇到「只能凑成 33 的倍数」的局面，即 A 获胜。
  

代码：

class Solution {
    public boolean stoneGameIX(int[] stones) {
        int[] cnts = new int[3];
        for (int i : stones) cnts[i % 3]++;
        return cnts[0] % 2 == 0 ? !(cnts[1] == 0 || cnts[2] == 0) : !(Math.abs(cnts[1] - cnts[2]) <= 2);
    }
}
复制代码

• 时间复杂度：O(n)O(n)
• 空间复杂度：O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2029 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。