【题解】P8079 [WC2022] 猜词【乱搞】

题目链接

题意

你要跟交互库玩一游戏。交互库会在词库（\(N=8869\) 个词，长度为 \(5\)，在交互开始前给你）中等概率随机选一个词，告诉你它的首字母，你有 5 次猜词的机会。

每次你要从词库里面选一个词告诉交互库，如果猜错了，交互库会告诉你：

• 哪些字母的位置是正确的
• 哪些字母在待猜单词中出现了但位置是错误的。

用 1~5 次猜测猜对的得分分别为：\(150,120,100,90,85\)。

交互库将与你进行 \(T=1000\) 次游戏，取平均分四舍五入的结果。时限 60 秒，只有一个测试点。

题解

这道题一看就很不正经。联想前一天《IOI 题型与去向分析》中所提到某些 IOI 题目要你“手撸决策树”，我们可以猜测这题可以使用决策树解决。

显然 8869 个词不可能手撸决策树，我们考虑按照如下方法建树：递归到一个结点时：

• 若其只包含一种可能的词，或者这是第五次猜测，结束过程；
• 否则枚举所有 \(N\) 个词，找到“最好”的一个 \(w\)。以 \(w\) 为标准，根据猜测它时返回结果不同，可以将当前节点的词分为若干部分，对于每个部分递归建树。

这样建出 26 棵树。查询时从首字母对应的树根开始，沿返回值对应的树边走。

那么问题在于“最好”的词应该如何衡量。最优的方式肯定是对于每个词都递归建树，取分数最高的一个，但这显然效率过低。感性理解我们可以知道，把当前节点的词分得越多、越均匀，效果越好。由此我们有多种衡量方式（记我们分出了 \(n\) 个部分，每个部分的占比为 \(p_i\)，\(\sum p_i=1\)）：

• \(n\)
• \(-\max p_i\)
• 分类交叉熵函数：\(-\sum p_i\log p_i\)
• 基尼系数：\(1-\sum p_i^2\)

考场上我采用了分类交叉熵函数，得了 97 分。想着与其卡这 3 分不如多想想前面的题，然后离金牌线差了 3 分。

注意到越早猜出来答案，得分越高。于是我们可以猜测以下两件事是有利的：

• 猜测的词本身可能是正确答案；
• \(n\) 很大。

基于以上两个猜测，我们精细调整“最好”的衡量标准，然后不知不觉就能过了。

//期望得分约为 100.07，四舍五入后大概率为 100
//代码中部分迷惑写法/命名是玄学调参的产物
#include
#include"word.h"
using namespace std;

namespace Wallbreaker5th{

const int N=9000;
string s[N];int occ[N];
int n;
mapch[26][N];int gue[26][N];int cnt[26];
mt19937 mt;
double gini(const vector&v){
	double sum=0;for(int i:v)sum+=i;
	double res=v.size()*0.2;
	for(int i:v)if(i)res-=log(i/sum)*(i/sum)*2;
	return res;
}
int res(int x,int ans){
	int r=0;
	for(int i=0;i<5;i++)r|=(s[x][i]==s[ans][i])<>i)&1)continue;
		for(int j=0;j<5;j++)if(!((r>>j)&1)&&s[x][i]==s[ans][j])r|=1<<(i+5);
	}
	return r;
}
double pred_score=0;
int sco[]={-1,150,120,100,90,85};
void build(int x,vectorw,int fi,int dep){
	if(w.size()==1||dep==5){
		gue[fi][x]=w[mt()%w.size()];
		pred_score+=sco[dep];
		if(w.size()>1)cerr<<"> "<>cho;
	for(int i=0;io;
		for(int j:w)o[res(i,j)]++;
		double g=0;
		if(o[31]){
			o[31]=0;
			int sum=0;for(auto i:o)sum+=i.second;
			o[31]=sum/(o.size()-1.);
			g++;
		}
		vectorv;for(auto i:o)v.push_back(i.second);
		g+=gini(v);
		cho.push_back({g,i});
	}
	sort(cho.begin(),cho.end(),greater>());
	int mxi=cho[0].second;

	gue[fi][x]=mxi;
	map>o;
	for(int j:w)o[res(mxi,j)].push_back(j);
	for(auto &i:o){
		if(i.first==31){
			pred_score+=sco[dep];
			continue;
		}
		ch[fi][x][i.first]=++cnt[fi];
		build(cnt[fi],i.second,fi,dep+1);
	}
}
void init(int num_scramble, const char *scramble){
	n=num_scramble;
	for(int i=0;iw[26];
	for(int i=0;i "<