Moe's CF Life

Appearance

E1. Game with Marbles (Easy Version) - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 916 (Div. 3) 标签: brute force, games, greedy, sortings 难度: *1400

喵喵，我们来玩游戏吧！ - 题目大意 ​

主人 sama，下午好喵~ 今天我们来玩一个超级有趣的弹珠游戏呐！

Alice 和 Bob 有 n 种不同颜色的弹珠。游戏开始时，Alice 先手，两人轮流操作。

每一次操作，当前玩家可以选择一种颜色 i，前提是 双方都至少有一颗这种颜色的弹珠。然后，操作的玩家丢掉自己的一颗 i 色弹珠，而他的对手则必须丢掉 所有 i 色的弹珠！

当再也找不到任何一种双方都拥有的颜色时，游戏就结束啦。

我们的目标是计算游戏结束时，Alice 剩余的弹珠总数减去 Bob 剩余的弹珠总数。Alice 希望这个分数尽可能高，而 Bob 则希望这个分数尽可能低。假设他们都绝顶聪明，我们来算算最后的分数会是多少吧！

小猫咪的思考过程 - 解题思路 ​

喵呜~ 看到 Alice 和 Bob 玩游戏，一个想最大化，一个想最小化，而且 n 还这么小（n <= 6），是不是感觉体内的算法 DNA 动了呀？这不就是经典的 博弈论 问题嘛！对于这种数据范围很小的问题，我们通常可以考虑搜索所有可能的游戏过程，的说。

状态怎么表示呢？ ​

游戏的核心在于“选择哪种颜色的弹珠”。一个颜色一旦被选过，就不能再选了。所以，游戏进行到某一时刻的状态，完全取决于 还有哪些颜色是可以选择的。

既然 n 这么小，我们可以用一个整数的二进制位来表示所有颜色的可用状态，这就是 状态压缩 喵！我们可以用一个 n 位的二进制数 mask 来表示：

  • 如果 mask 的第 i 位是 1，表示第 i 种颜色还可以被选择。
  • 如果第 i 位是 0，表示这种颜色已经被某一方选择过了。

轮到谁了？ ​

Alice 先手，是第 0 轮操作。Bob 是第 1 轮，Alice 是第 2 轮…… 我们可以通过已经操作过的轮数来判断当前玩家。已经操作过的轮数 = n - mask 中 1 的数量。

  • 如果已操作轮数是偶数，轮到 Alice。
  • 如果已操作轮数是奇数，轮到 Bob。

Minimax 闪亮登场！ ​

这是一个典型的 Minimax（极小化极大） 过程：

  • Alice (Maximizer): 她会审视所有当前可行的选择，并选择那个能导向 最大 最终分数的选项。
  • Bob (Minimizer): 他也会审视所有选择，但会选择那个能导向 最小 最终分数的选项。

我们可以定义一个函数 solve(mask)，它的功能是计算从当前颜色状态 mask 开始，直到游戏结束，所能产生的 分数差。

  1. Alice 的回合: 她会遍历 mask 中所有为 1 的位 i（代表可选择的颜色 i）。 如果她选择颜色 i：

    • Alice 失去一颗 i 色弹珠，Bob 失去所有 i 色弹珠。
    • 这一步对最终分数 (A - B) 的贡献是 (a[i] - 1) - 0 = a[i] - 1。
    • 游戏进入下一个状态，可用颜色变为 mask 去掉第 i 位 (mask' = mask ^ (1 << i))。
    • 从这一步开始的总分数为 (a[i] - 1) + solve(mask')。 Alice 会在所有可能的 i 中，选择一个使得这个总分数最大的。 solve(mask) = max( (a[i] - 1) + solve(mask') ) for all available i.

  2. Bob 的回合: 他同样会遍历所有可行的选择 i。 如果他选择颜色 i：

    • Bob 失去一颗 i 色弹珠，Alice 失去所有 i 色弹珠。
    • 这一步对最终分数 (A - B) 的贡献是 0 - (b[i] - 1) = -(b[i] - 1)。
    • 游戏进入下一个状态 mask'。
    • 从这一步开始的总分数为 -(b[i] - 1) + solve(mask')。 Bob 会在所有可能的 i 中，选择一个使得这个总分数最小的。 solve(mask) = min( -(b[i] - 1) + solve(mask') ) for all available i.

  3. 游戏结束 (Base Case): 当 mask 为 0 时，说明所有颜色都已经被选完，游戏结束。此时不能再产生任何分数，所以 solve(0) = 0。

记忆化搜索！ ​

为了避免重复计算同一个 mask 状态，我们用一个 memo 数组把计算过的 solve(mask) 的结果存起来。下次再遇到同一个 mask，直接返回结果就好啦！这就是 记忆化搜索，一种自顶向下的动态规划实现方式，非常直观喵~

总结一下，我们的策略就是：状态压缩 + 记忆化搜索 + Minimax！

把想法变成代码喵 - 代码实现 ​

cpp
#include <iostream>
#include <vector>
#include <algorithm>

// __builtin_popcount 是 GCC/Clang 的一个内置函数，用来计算一个整数的二进制表示中有多少个 '1'
// 在这道题的环境下是支持的，非常方便喵~
#if defined(__GNUC__) || defined(__clang__)
// 这个内置函数不需要特定的头文件
#else
// 为其他编译器提供一个备用实现，虽然在目标平台上用不到
int __builtin_popcount(unsigned int n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}
#endif

using namespace std;

int n;
vector<long long> a, b;
vector<long long> memo; // 记忆化数组，存储 solve(mask) 的结果
vector<bool> visited;  // 标记某个状态是否已经计算过

long long solve(int mask) {
    // Base Case: 如果 mask 为 0，说明所有颜色都选完了，游戏结束，分数贡献为 0
    if (mask == 0) {
        return 0;
    }
    // 记忆化: 如果这个状态已经计算过，直接返回结果，不用再算啦
    if (visited[mask]) {
        return memo[mask];
    }

    // 计算已经玩过的颜色数量，来判断轮到谁了
    int num_in_mask = __builtin_popcount(mask);
    int num_played = n - num_in_mask;

    long long result;
    if (num_played % 2 == 0) { // 偶数轮 (0, 2, ...), 是 Alice 的回合
        long long max_score = -9e18; // 初始化为一个非常小的值
        // Alice 遍历所有可选的颜色 i
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) { // 检查第 i 位是不是 1，即颜色 i 是否可用
                // Alice 选择颜色 i，她的得分贡献是 a[i]-1，然后递归到下一个状态
                max_score = max(max_score, (a[i] - 1) + solve(mask ^ (1 << i)));
            }
        }
        result = max_score;
    } else { // 奇数轮 (1, 3, ...), 是 Bob 的回合
        long long min_score = 9e18; // 初始化为一个非常大的值
        // Bob 遍历所有可选的颜色 i
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) {
                // Bob 选择颜色 i，他对分数 A-B 的贡献是 -(b[i]-1)，然后递归
                min_score = min(min_score, -(b[i] - 1) + solve(mask ^ (1 << i)));
            }
        }
        result = min_score;
    }

    // 将计算结果存起来
    visited[mask] = true;
    memo[mask] = result;
    return result;
}

void solve_case() {
    cin >> n;
    a.resize(n);
    b.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    // 初始化记忆化数组
    int memo_size = 1 << n;
    memo.assign(memo_size, 0);
    visited.assign(memo_size, false);

    // 初始状态是所有颜色都可用，即 mask 的低 n 位都为 1
    cout << solve((1 << n) - 1) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve_case();
    }
    return 0;
}

跑得有多快呀？ - 复杂度分析 ​

  • 时间复杂度: O(n * 2^n) 的说。 我们总共有 2^n 种不同的状态（mask 的取值）。对于每一种状态，我们都需要遍历 n 种颜色来决定下一步的最佳选择。所以每个测试用例的总时间复杂度就是 O(n * 2^n)。因为这道题 n <= 6，所以 6 * 2^6 = 6 * 64 = 384，这个计算量对于计算机来说是小菜一碟，跑得飞快喵~

  • 空间复杂度: O(2^n) 的说。 我们需要 memo 和 visited 两个数组来存储每个状态的结果和访问信息，它们的大小都是 2^n。所以空间复杂度就是 O(2^n)。

小猫咪的知识总结 - 知识点与总结 ​

这道题真是一个很好的练习题呢！它教会了我们：

  1. 博弈论基础 (Minimax): 当遇到两个玩家、目标相反、信息完全公开的零和游戏时，要想到 Minimax 思想。Alice 总是做出对自己最有利的选择（最大化），而 Bob 总是做出对 Alice 最不利的选择（最小化）。

  2. 状态压缩 DP: 当问题的状态可以由一个小的集合来表示时（比如这道题里的可用颜色集合），就可以用一个整数的二进制位来“压缩”这个状态。这是一种非常强大的技巧，能把看似复杂的状态空间变得可以用数组下标来访问。

  3. 记忆化搜索: 这是实现动态规划的一种优雅方式。它从目标状态出发，自顶向下地解决问题，遇到子问题就去解决，并将子问题的解储存起来。代码结构和我们的递归思考过程非常相似，写起来很自然的说。

  4. 正确建模: 解决问题的关键在于正确定义 solve(mask) 的含义。它代表的是“从当前状态 mask 开始，到游戏结束，双方最优博弈下产生的 分数增量”。理解了这一点，状态转移方程就水到渠成啦！

希望这篇题解能帮助到主人 sama！下次遇到类似的问题，你一定也能像小猫咪一样，敏锐地发现解题的线索的！加油喵~

Released under the MIT License.

Copyright © 2024-present Moe