#P3330. [BeiJing2013]分数

[BeiJing2013]分数

题目描述

出题时,希望选手的实力差异能反映在得分上。不同比赛的选手能力分布可能不同,小强为此建立了一个模型。

有 NN 名选手,将他们按实力从高到低排列,第 ii 名选手的实力为 aia_i。小强可以选择题目的难度 dd 和区分度 bb,第 ii 名选手的实际得分为

si=1001+exp⁡(d−bai).s_i=\frac{100}{1+\exp(d-ba_i)}.

理想分数形成首项为 100100、末项为 00 的等差数列,即 ri=100N−iN−1r_i=100\frac{N-i}{N-1}。题目的分数偏差定义为

$$\sum_{i=1}^N \left(r_i\ln\frac{100}{s_i}+(100-r_i)\ln\frac{100}{100-s_i}\right),$$

其中 exp⁡\exp 为指数函数,ln⁡\ln 为自然对数。

难度 dd 和区分度 bb 可取实数,不另设有限参数上界。求分数偏差的下确界:当最优值能在有限参数处取得时,它就是最小值;否则允许参数趋向无穷,并输出能逼近的最小偏差。

输入格式

从标准输入读取。第一行是选手人数 NN 和精度要求 PP。接下来 NN 行,每行一个 00 到 100100 之间的整数,表示一名选手的实力。

输出格式

向标准输出写入。输出一个实数,保留 PP 位有效数字,多余的位直接舍去。

样例 1

5 4
100
20
15
10
8
195.2

样例说明

这一组选手有一名能力特别强,题目更需要区分其余几名选手。最优参数约为 d=4.662016d=4.662016、b=0.299386b=0.299386,五名选手的实际得分约为 99.99999999.999999、79.01304179.013041、45.72999245.729992、15.86707015.867070、9.3899529.389952。下图展示样例中理想得分、实际得分与实力的关系。

样例的理想得分、实际得分和实力

下图给出本样例的分数偏差关于难度与区分度的等高线,可以看到本样例只有一个极值点。

样例中分数偏差关于难度和区分度的等高线

数据范围

3≤N≤203\le N\le20,1≤P≤101\le P\le10,0≤ai≤1000\le a_i\le100。原赛十个测试点的 PP 依次为 1 到 10;加强数据同样遵守上述范围。

相关

在下列比赛中:

三分