猜词题解

· · 题解

假设你会一点点信息论，因为做这道题的人一定知道这是一道信息论题。

如果不会的话，你可以观看这两个视频：https://www.bilibili.com/video/BV1yVNU6xERx/，https://www.bilibili.com/video/BV1zZ4y1k7Jw/。

理论上每次我们应选信息熵最大的一个单词，一个单词的信息熵是：

E=\sum_{i=0}^{242}-p_i\log_2{p_i}

这里 p_i 指这个单词获得的反馈是 i 的概率（这里我们把每种状态编码成一个三进制数，g 是 2，s 是 1，否则是 0，共五位）。

我们有两个集合 \text{table} 和 \text{st}，第一个是所有单词的集合，第二个是所有可能作为答案的单词的集合。每次 guess 前，我们应适当地从 \text{st} 中删去元素，这部分是模拟。

然后我们枚举 \text{table} 中的每一个单词，计算它们的信息熵，找到最大的那一个，然后返回。

但显然此时时间复杂度是 O(Tn^2) 的，根本过不掉，所以我们要优化。

计算熵最慢的是第一次 guess，但它可以很方便的打表解决，然后剩下的部分就跑得很快了。

但这个时候我们还不能 AC。比如在最后的查询中，只剩下两个单词 a 和 b，只有 b 是对的，但看起来它们的熵是相同的，这时程序就可能得不到分了。

于是我们改变熵的求法：

E=0.01p_{242}+\sum_{i=0}^{242}-p_i\log_2{p_i}

也就是加上了这个单词正确的概率乘 0.001，显然这很有用。

#include<bits/stdc++.h>

std::vector<std::string> table, st;

std::string ans_fir[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"};  // 打表

int n;

int siz;

void init(int num_scramble, const char *scramble) {
    n=num_scramble;
    for(int i(0); i<n; i++) {
        table.push_back("");
        for(int j(0); j<5; j++) table.back().push_back(scramble[5*i+j]);
    }
}

std::string las;

std::array<int,5> check(std::string appt, std::string ans) {
    std::array<int,5> ret;
    for(int i(0); i<5; i++) {
        if(appt[i]==ans[i]) ret[i]=2;
        else ret[i]=0;
    }
    for(int i(0); i<5; i++) if(!ret[i]) {
        for(int j(0); j<5; j++) {
            if(ret[j]!=2 && appt[i]==ans[j]) { ret[i]=1; break; }
        }
    }
    return ret;
}

int to_num(std::array<int,5> result) {
    int p(1);
    int ret(0);
    for(int i(0); i<5; i++) ret+=result[i]*p, p*=3;
    return ret;
}

int cnt[243];

const char *guess(int num_testcase, int remaining_guesses, char initial_letter, bool *gold, bool *silver) {
    if(remaining_guesses==5) {
        st.clear();
        for(int i(0); i<n; i++) {
            if(table[i][0]==initial_letter) st.push_back(table[i]);
        }
        las=ans_fir[initial_letter-'a'];
        return las.data();
    } else {
        int result[5];
        for(int i(0); i<5; i++) result[i]=std::max(gold[i]*2, (int)silver[i]);
        std::vector<std::string> nxt;
        for(auto i : st) {
            std::array<int,5> now(check(las, i));
            bool flg(1);
            for(int j(0); j<5; j++) {
                if(gold[j]*2+silver[j]!=now[j]) { flg=0; break; }
            }
            if(flg) nxt.push_back(i);
        }
        st=nxt;
        siz=st.size();
        long double max(-1);
        for(int i(0); i<n; i++) {
            for(int j(0); j<243; j++) cnt[j]=0;
            for(auto j : st) cnt[to_num(check(table[i], j))]++;
            long double p(0);
            for(int i(0); i<243; i++) {
                long double x((long double)cnt[i]/siz);
                if(x==0) continue;
                p+=-x*log2(x);
            }
            p+=0.01*cnt[242]/siz;
            if(p>max) max=p, las=table[i];
        }
        return las.data();
    }
}