P8079 [WC2022] 猜词
zhlzt
·
·
题解
:::info[喜提洛谷当前最优解]{open}
信息熵函数不同于所有题解。
https://www.luogu.com.cn/record/231900101
:::
:::warning[Warning]{open}
猜测的单词不一定要属于答案集。
:::
我们需要最大化猜测一个单词带来的价值。设答案集为 S，考虑计算猜测一个单词所能缩小 |S| 的比率。设计以下熵函数：
E(\text{word})=\sum_{c\in\text{color}(\text{word},S)} P(c)\frac{1}{P(c)}=|\text{color}(\text{word},S)|
其中，\text{color}(\text{word},S) 表示猜测 \text{word}，且答案集为 S 时的可能颜色集。颜色指交互库返回的数组 \text{gold} 和 \text{silver}。
:::success[Tip]{open}
比率基于乘除法意义。故理论上应使用加权几何平均，或取对数后的加权算术平均（也就是分类交叉熵函数）。
但是以上二者分别使用了指数函数和对数函数，计算速度较慢。
采用这里的方法可以避免进行指数，对数和浮点数计算，极大地提高了程序的运行效率。
:::
于是每次猜测只需选择 E(\text{word}) 最大的单词即可。
但是，当 |S| 极小时，所有的 E(\text{word}) 可能是一样的。为了选择 S 中的单词，我们考虑给 S 中单词的 E(\text{word}) 增加额外权值。更改函数为：
E(\text{word})=[\text{word}\in S]\cdot \varepsilon+|\text{color}(\text{word},S)|
由于第一次猜测前计算 E(\text{word}) 太慢了，很难卡过去。
注意到交互库传入了参数 initial_letter。考虑预处理答案的首字母一定时，E(\text{word}) 最大的单词，就不会 TLE 了。
本地测试 1000 局，平均分高达 100.350。
:::success[温馨提示]{open}
代码就不放了，自己写可以提高代码能力。
:::