Solution -「GLR-R4」芒种

Rainybunny · 2023-02-28 10:55:56 · 题解

\mathscr{Description}

[Link](), 懒得概括题意.jpg

\mathscr{Solution}

Subtask 1 (n,m\le2) 一共只有五种情况, 样例已经给出了三种, 剩下两种自己手玩就行啦!

Subtask 2 (n,m\le8) 奇奇怪怪的状压, 或者忘记记忆化的各色搜索应该都能得到这档.

Subtask 3 (n=m) 观察样例可以发现, 此时也许有 \textit{ans}=n/2, 特别的, 当 n=m=1 时, \textit{ans}=1. 严谨的说, 我们可以证明, 当 n=m>1 时, 双方一开始就会和局.

尝试归纳证明. 假设当 2\le n\le n_0 时, 先手期望得分不低于后手. 现在, 我们来考虑 n=n_0+1 的情况. 此时先手一共只有三种决策:

选择两张未知牌 (未知牌共 2n-m=n=m 张);
选择一张已知牌 (已知牌共 m 张), 一张未知牌;
选择两张已知牌.

对于第一种决策, 因为已知牌中 n 种类型都已经出现, 所以先手不可能拿到相同类型的牌. 此时先手必然结束自己的回合. 而后手可以立马 "捡漏", 将先手翻出的两张牌和已知的两张牌分别配对, 得到 2 分. 接着, 后手变为先手, 面对 n\gets n-2 的情况. 根据归纳假设, 此时的先手期望得分不劣于后手, 所以在这种决策下, 原先手的期望得分低于后手.

对于第二种决策, 类似的, 先手有 1/n 的概率直接拿出一对同类卡牌, 以 (n-1)/n 的概率给后手 "打工", 而二者都会递归到 n\gets n-1 的情况. 设 n\gets n-1 时, 先手期望得分为 x~(x\ge (n-1)/2), 那么原来先手的期望得分为:

\begin{aligned} E &= \frac{1}{n}(1+x)+\frac{n-1}{n}(n-1-x)\\ &= \frac{1}{n}+\frac{(n-1)^2}{n}-\frac{n-2}{n}x\\ &\le \frac{1}{n}+\frac{(n-1)^2}{n}-\frac{(n-1)(n-2)}{2n}\\ &= \frac{2+2n^2-4n+2-n^2+3n-2}{2n}\\ &= \frac{n}{2}-\frac{1}{2}+\frac{1}{n}. \end{aligned}

可见 n\ge2 时都有 E\le\frac{n}{2}, 也即是原先手期望得分低于后手.

于是, 先手选择了第三种决策! 第三种决策没有任何效果, 仅仅是 "摆烂" 地过掉自己回合, 轮到对方操作. 此时对方又面临这三种决策的选择, 他又会 "摆烂" 过掉自己的回合 ... 双方都无法让自己的期望得分高于对方, 那么此时双方都会同意和局! 两人得分 n/2, 我们完成了归纳, 也顺带证明了游戏一开始即和局结束. \square

Subtask 4 (T=1) 大概有什么一次只能求出一个答案的算法?

Subtask 5 来讲正解啦. 在 subtask 3 的证明过程中, 我们已经自然地引入了 "先手得分是否低于后手" 的讨论. 进一步的, 由于双方得分之和一定是 n, 所以我们可以用双方得分之差来刻画先手得分. 令 f(n,m) 表示 n 对牌, m 张已知时, 先手期望得分 - 后手期望得分的值. 还是来做一做同 subtask 3 证明过程中的三种讨论:

先手选择一张已知牌, 一张未知牌, 此时要求 m\ge1, 有转移:
\begin{array}{ccl} f(n,m) & \overset{\max}{\longleftarrow} & \frac{1}{2n-m}(1+f(n-1,m-1))-\frac{m-1}{2n-m}(1+f(n-1,m-1))\\ & & -\frac{2n-2m}{2n-m}f(n,m+1). \end{array}
先手选择两张未知牌, 此时要求 2n-m\ge2, 有转移:
\begin{array}{ccl} f(n,m) & \overset{\max}{\longleftarrow} & \frac{n-m}{\binom{2n-m}{2}}(1+f(n-1,m))-\frac{\binom{m}{2}}{\binom{2n-m}{2}}(2+f(n-2,m-2))\\ & & -\frac{m(2n-2m)}{\binom{2n-m}{2}}(1+f(n-1,m))-\frac{2(n-m)(n-m-1)}{\binom{2n-m}{2}}f(n,m+2). \end{array}
先手选择两张已知牌, 此时要求 m\ge2. 注意这里不是 f(n,m)\overset{\max}{\longleftarrow}-f(n,m), 如果这种决策是优秀的, 双方会直接和局, 所以有:
\begin{array}{ccl} f(n,m) & \overset{\max}{\longleftarrow} & 0. \end{array}

边界为 f(0,0)=0. 转移过程有很多细小情况的讨论, 可能会引入非法状态, 但这些非法状态的转移系数必然为 0, 所以不必过分担心. 直接递推或者记忆化搜索, 就能 \mathcal O(nm) 求出所有 f. 最终答案即为 (n+f(n,m))/2.

\mathscr{Code}

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

typedef double VType;
// typedef long double VType;

template <typename Tp>
inline void chkmin(Tp& u, const Tp& v) { v < u && (u = v, 0); }
template <typename Tp>
inline void chkmax(Tp& u, const Tp& v) { u < v && (u = v, 0); }
template <typename Tp>
inline Tp imin(const Tp& u, const Tp& v) { return u < v ? u : v; }
template <typename Tp>
inline Tp imax(const Tp& u, const Tp& v) { return u < v ? v : u; }

const int MAXN = 5e3;
bool vis[MAXN + 5][MAXN + 5];
VType f[MAXN + 5][MAXN + 5];

inline VType calc(const int n, const int m) {
    if (n <= 0 || m < 0 || n < m) return 0;
    VType& cur = f[n][m];
    if (vis[n][m]) return cur;
    vis[n][m] = true, cur = -1e100;
    if (m >= 1) {
        chkmax(cur, (1 + calc(n - 1, m - 1)
        - (m - 1) * (1 + calc(n - 1, m - 1))
        - 2 * (n - m) * calc(n, m + 1))
        / (2 * n - m));
    }
    if (2 * n - m > 1) {
        chkmax(cur, 2 * ((n - m) * (1 + calc(n - 1, m))
        - m * (m - 1) / 2 * (2 + calc(n - 2, m - 2))
        - 2 * m * (n - m) * (1 + calc(n - 1, m))
        - 2 * (n - m) * (n - m - 1) * calc(n, m + 2))
        / ((2 * n - m) * (2 * n - m - 1)));
    }
    if (m >= 2) chkmax(cur, 0.);
    return cur;
}

int main() {
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        printf("%.12f\n", (n + calc(n, m)) / 2);
    }
    return 0;
}