P13025

· · 题解

对每对选手做 \chi^2 独立性检验，取 \chi^2 之和最小的参赛者，可以达到 100\% 的正确率！

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T,P,V=1;
    cin>>T>>P;
    for(int _=1;_<=T;_++)
    {
        string s[112];
        for(int i=1;i<=100;i++)
            cin>>s[i];
        long double k2[112][112]={},k2s[112]={};
        for(int i=1;i<=100;i++)
            for(int j=1;j<=100;j++)
            {
                int a=0,b=0,c=0,d=0;
                for(int k=0;k<=9999;k++)
                {
                    if(s[i][k]=='1'&&s[j][k]=='1') a++;
                    if(s[i][k]=='1'&&s[j][k]=='0') b++;
                    if(s[i][k]=='0'&&s[j][k]=='1') c++;
                    if(s[i][k]=='0'&&s[j][k]=='0') d++;
                }
                k2[i][j]=10000.0L*(a*d-b*c)*(a*d-b*c)/(a+b)/(c+d)/(a+c)/(b+d);
            }
        for(int i=1;i<=100;i++)
            for(int j=1;j<=100;j++)
                k2s[i]+=k2[i][j];
        for(int i=1;i<=100;i++)
            if(k2s[i]<k2s[V]) V=i;
        printf("Case #%d: %d\n",_,V);
    }
    return 0;
}
记 $X \in \{1, 2, \ldots, n\}, Y\in \{1, 2, \ldots, m\}$ 是两个待判定的离散随机变量，$z_{i, j}$ 表示样本中数据 $(X, Y) = (i, j)$ 的频数，则： $$ \chi^2 = \displaystyle \sum _{i = 1} ^n \displaystyle \sum _{j = 1} ^m \dfrac{\left( z_{i, j} - \dfrac{\left(\displaystyle \sum _{i' = 1} ^n z_{i', j} \right) \cdot \left(\displaystyle \sum _{j' = 1} ^m z_{i, j'} \right)}{\displaystyle \sum _{i' = 1} ^n \displaystyle \sum _{j' = 1} ^m z_{i, j}} \right)^2}{\displaystyle \dfrac{\left(\displaystyle \sum _{i' = 1} ^n z_{i', j} \right) \cdot \left(\displaystyle \sum _{j' = 1} ^m z_{i, j'} \right)}{\displaystyle \sum _{i' = 1} ^n \displaystyle \sum _{j' = 1} ^m z_{i, j}}} $$ 在本题中，其他选手的作答正确率随题目难度增大而普遍降低，呈现较强的相关性，而作弊者以 $50\%$ 的概率一定答对题目，增加了作弊者与其他选手作答结果间的独立性，因此作弊者与其他选手作答结果间算出的 $\chi^2$ 会显著小于正常选手作答结果间算出的 $\chi^2$，上面给出的做法是可行的。 （当 $n = m = 2$ 时，记 $(z_{1, 1}, z_{1, 2}, z_{2, 1}, z_{2, 2}) = (a, b, c, d)$，则 $\chi^2$ 的公式可以化简成：） $$ \chi^2 = \dfrac{(a + b + c + d)(ad - bc)^2}{(a + b)(c + d)(a + c)(b + d)} $$