题解：P8079 [WC2022] 猜词（民间数据）

· · 题解

信息论

每次猜词，必然是要选择能获得的“信息”最多的词。但我们如何衡量信息的多少呢？

举个例子。扔一个骰子，下面有三个随机事件：

这三个事件的信息量大小如何？相信凭直觉也知道，信息量依次增大。

来想想信息的作用是什么，信息的作用是消除不确定性。所以消除不确定性的多少，决定了一件事带来信息的多少，这就是一个随机事件的信息量。

事件一必然发生，所以它没带来任何信息。事件二有 \frac{1}{2} 概率发生，我们可以确定骰子的点数只能是 1,2,3. 事件3只有 \frac{1}{6} 概率发生，我们可以确定骰子点数为 6.于是可以大致确定信息量随着概率的减小增大。

信息量和概率的具体关系又是什么样的呢？假设现在有 m 个小球，你从中抽取一个小球，你只能通过传输信号的方式将结果告诉我，每次传递信号，只能向我发送一个 0 或 1，那么你需要传递几次信号才能让我知道？显然，用 \log_2m 次信号即可。信息量为 I(抽中某个小球)=\log_2m（这些信号组成二进制数，代表小球编号）进一步考虑，对于随机事件 x，它可以看成是在 \frac{1}{P(x)} 个小球之中抽取。那么信息量公式就是

I(x)=\log_2\frac{1}{P(x)}=-\log_2 P(x)

但是，我们猜一个单词，所获得的结果可能是不一样的，可能获取不同的信息量。此时就需要信息熵，简单地说它表示信息量的期望。根据期望的计算方法可以得到信息熵。

H(x)=- \sum_{x_i\in x} P(x_i)\log P(x_i)

主要思路

于是我们获得了一个想法。对于每个 word 中的单词 S，枚举 ans 中的 T，计算以 T 作为答案时猜测 S 获得的评测结果。开一个桶 num ，对于每个评测结果，存储有多少个 T 是答案的时候，猜测 S 对应的评测结果结果是它。这样就可以计算出每个 S 的信息熵。（以猜测 S，并获取某个评测结果作为一个随机事件考率）

\sum \frac{\log(num_i)}{num_i}

每次猜信息熵最大的词即可。

优化

第一次猜的单词需要打表，否则时间复杂度太大。

打完了表，交上去，发现这么做只能 97 分，还需要小小优化一下。观察得分情况发现，我们需要平均 3 次之内才出来才可以得到满分。而上述这种做法，很多情况下，2 次猜完，备选答案的个数还剩 2 到 5 个。一般需要 3 次才能确定答案，第 4 次输出。我们可以加一点小优化。

比如当前 ans 还剩 2 个单词：\texttt{apple,addle}。我们有很多单词可以确定答案是什么，只需要试一试 \text p 在不在答案中即可。但是我们为什么不直接输出 \texttt{apple} 呢？这样还有一半概率直接猜出答案，省了一次猜测。

在筛选最佳单词时，对于每个单词，它如果在 ans 之中的话，让它的优先度增加一点点。这样我们就有一定的可能再前 2 轮猜出答案，弥补了有的单词我们需要 4 轮才能猜才出来的缺陷。

这样就可以通过本题了。

代码

// #include"word.h"
#include<bits/stdc++.h>
using namespace std;
const string first_guess[26]={"slier","lares","lares","tores","tarns","arles","lares","lares","snare","ousel","ranis","nares","tares","aides","tries","lares","raise","aides","plate","nares","snare","riles","nares","cones","kanes","aeons"};
const int N=8869;
int cnt,pattern[243];
vector<string> word,ans;
string query;
void init(int num_scramble,const char *scramble){
    for(int i=0;i<N;i++){
        string _s;
        for(int j=0;j<5;j++)_s.push_back(scramble[i*5+j]);
        word.push_back(_s);
    }
}
int judge(string s,string t){
    int res[5]={0,0,0,0,0};
    for(int i=0;i<5;i++)if(s[i]==t[i])res[i]=2;
    for(int i=0;i<5;i++){
        if(res[i]==2)continue;
        for(int j=0;j<5;j++){
            if(res[j]!=2&&s[i]==t[j]){
                res[i]=1;
                break;
            }   
        }
    }
    int _=0;
    for(int i=0;i<5;i++)_=_*3+res[i];
    return _;
}
bool match(string s,string t,bool *gold,bool *silver){
    int cor=0;
    for(int i=0;i<5;i++){
        cor*=3;
        if(gold[i])cor+=2;
        if(silver[i])cor++;
    }
    return cor==judge(s,t);
}
double calc_entropy(string s,int remaining_guesses){
    memset(pattern,0,sizeof(pattern));
    for(string t:ans)pattern[judge(s,t)]++;
    double E=0;
    for(int i=0;i<243;i++)if(pattern[i]>0){
        double P=1.0*pattern[i]/cnt;
        E-=P*log2(P);
    }
    if(remaining_guesses==4)E+=0.1*pattern[242];
    else if(remaining_guesses<=3)E+=1.0*pattern[242]/cnt;
    return E;
}
const char *guess(int num_testcase,int remaining_guesses,char initial_letter,bool *gold,bool *silver){
    if(remaining_guesses==5){
        ans.clear();
        for(string s:word)if(s[0]==initial_letter)ans.push_back(s);
        cnt=ans.size();
        query=first_guess[initial_letter-'a'];
        return query.c_str();
    }
    vector<string> last;
    last=ans;
    ans.clear();
    for(string t:last)if(match(query,t,gold,silver))ans.push_back(t);
    cnt=ans.size();
    if(cnt==1)return (query=ans[0]).c_str();
    double mx=-114514.1919810;
    for(int i=0;i<word.size();i++){
        double entro=calc_entropy(word[i],remaining_guesses);
        if(entro>mx)mx=entro,query=word[i];
    }
    return query.c_str();
}