Skip to content

1315: 排位上分

题目

题目描述

国际等级分系统(ELO-rate-system)被广泛使用与竞技游戏的排位系统中。在此体系下,ELO初始积分一般定为1200,而2600分以上的分数可以视作最高水平。

根据日常经验和大量的数据模拟,玩家在游戏中表现的波动接近于逻辑分布,由此总结出玩家A面对玩家B的胜率公式: $$ P(D)=\frac{1}{1+10^{-D/400}} $$ 其中$D$为玩家A与玩家B的分差:$D=R_A-R_B$。

反过来,如果知道玩家A面对玩家B在游戏表现中胜率,能够通过上式反过来计算分差。

每次两个玩家比赛之后,双方根据比赛结果和双方分差来更新$rating$。对于某个玩家,具体的更新公式如下: $$ R_n=R_0+K\times(G-G_e) $$ $R_n$为比赛结束后的新的排位积分,$R_0$为比赛前的排位分

$K$是权重系数,一般来说水平越高$K$的取值越小,具体如下

  1. 等级分$<2000$,则$K=30$
  2. 等级分$\in[2000,2400]$,则$K=20$
  3. 等级分$>2400$,则$K=10$

$G$为玩家的实际得分(获胜为1,失败则为0),$G_e$则为在原排位分基础上玩家的预期胜率($P(D)$)

为了使得排位分能够更快地逼近玩家的真实水平,引入连胜奖励机制。

当选手连胜次数超过常数5时,接下来每赢一次额外增加积分$M=100$,失败则连胜数清零。公式如下: $$ R_n=R_0+K\times(G-G_e)+M\ (连胜数>5)\ R_n=R_0+K\times(G-G_e)\ (连胜数\leq5) $$ 我们希望模拟玩家在ELO积分体系下上分的过程。

现在有$n$个$Player$,每个玩家有一个初始$rating$和$skill$($rating<skill$),分别表示当前积分和真正的实力对应的积分分数。($skill[]$下标和$Player$的下标$id$对应)

我们将分别对每个玩家调用$Train()$函数,这个玩家通过不断地对战来提升积分,结束后返回对战的轮数。

为了简化对战的模拟,我们首先通过$matchPlayer()$函数生成一个和玩家$p$积分相同的对手(实力相仿),并且对手的真实实力($skill$)就是他的积分。

通过$battle()$函数获得比赛结果。双方的真实实力之差为$D$,则$P(D)$即为获胜概率,用随机值模拟结果。

通过$update()$函数更新玩家$p$的积分。

不妨认为当$skill-rating<delta$时,积分靠近真实水平,其中$delta$为固定常数。

```cpp // src.hpp

ifndef ARENA_CPP_SRC_HPP

define ARENA_CPP_SRC_HPP

include

include

const int N = 100010; const int delta = 10;

int n, rounds; int skill[N];

// todo: add necessary variables here

struct Player { int id; // index of players[] std::string account; char name[30]; double rating;

// add definitions if necessary

} players[N];

void init(){ srand(time(0)); }

double P(double D){ // todo: P() function }

Player matchPlayer(const Player &p){ // todo: construct another Player with same rating as p }

int battle(const Player &p1, const Player &p2){ rounds++; // todo: return 1 if p1 wins, or 2 if p2 wins }

void update(Player &p, double D, int G, double M){ // todo: update ranking of p with parameters D, G, M }

int Train(Player &p, int skill){ rounds = 0; // todo: keep battling until rating approaches skill return rounds; }

endif //ARENA_CPP_SRC_HPP

```

评测的时候,每个已有的变量都会有初始值,你只需要填写每个函数的内容即可。

数据范围

每个评测点的$n\leq100000$,其中初始积分和真实实力之差逐渐增加。

每个测试点,只需要超过$90\%$的玩家在$200$次比赛之内,积分接近(收敛于)真实实力,就视为通过。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!