题解：AT_xmascon18_d Devilish Dice

· · 题解

这么水的题竟然没有题解。

步入正轨

::::success[题意]{open} 给定 n 个 k 面的骰子，首先，你需要在每个骰子的每个面上填写 0 到 10^9 之间的整数。然后，对手先选择一个骰子，接着你从剩下的骰子中选择一个。两人同时掷出所选骰子，点数大的一方获胜；如果点数相同，则对手获胜。双方都采取最优策略以最大化自己的胜率。

你需要给出一种填写骰子的方案，使得在你的填写之后，当双方都最优操作时，你的胜率尽可能大。 ::::

设你填写的 n 个骰子为 D_1, D_2, \dots, D_n，对手先选择骰子 D_i，你选择了骰子 D_j 来和对手对抗，你的胜率为 P(D_j > D_i)，而对手会选择 D_i 来最小化你的胜率，所以你的胜率为

\min\limits_{i} \max\limits_{j \ne i} P(D_j > D_i)

你的目标是设计这个骰子，使上式最大化。

考虑构造两种类型的骰子：

将这两种骰子交错排列，可以证明，在这种构造下，对于任意对手选择的骰子，你都可以选择一个相邻的骰子（常数与平衡相邻）使得你的胜率至少为 \frac{1}{2}（当 k 为偶数时恰好为 \frac{1}{2}，当 k 为奇数时接近 \frac{1}{2}）。对手为了最小化你的胜率，会选择那个使你最大胜率最小的骰子，而这个最小值至少为 \frac{1}{2}。因此，你的最终胜率至少为 \frac{1}{2}。

按照上面的思路编写代码即可。