「基本上codeforces上的赛制分做两种,codeforces规则(这个名字是我随便作出来的,如果有什么官方的名称也可以和我说一下)和ACM-ICPC规则。
在codefoces规则中每道题都有不同的分值,理所当然地越高分的题目就越难,通常就是由A题最简单,然后难度逐渐增加,去到E或F题就是最难了。例如在Round812当中分数的分布就是500-1000-1750-2000-2500-3000。
然后你如果看过比赛的榜单,其实会见到他们的分数不是整整齐齐的500,1000之类的分数,这是因为codeforces规则中有比较特别的一点,就是每一条题目的分数会随着时间的过去会线性减少。
举个例子,一题500分的题目,在比赛开始的2分钟后提交就会变做496分,而如果到10分钟后便会变成480分,每多一分钟便会扣两分。如果是1000分的话就会每一分钟扣4分,反正越高分就越会衰减。
还有,每一次提交的代码错误的话就会扣50分。但是其实也是不用这么在意这个扣分啦,反正IOI时提交多少次也没关系,而且你在交上去之前也很难知道自己的代码是不是对的。
ACM-ICPC规则的话,就不会每一题都有不同的分值了,做到多少题就是多少分了。但是ACM赛制中难度的顺序和codeforces赛制也是一样,A题最简单,然后难度逐渐增加。
当然,如果每道题的没有分数的差别的话大概就会有一堆人同分,所以如果两个人做对的题目数是一样的话,就会依照他们所有题目提交时间的总和来进行排序,用时少一点的排名就较高。
而在ACM赛制当中,提交错误就不是扣分而是变成了罚时,每错一次的话累计时间就会加十分钟,同样的也不太用在意提交错误的罚时,可以做对题目还是比较重要。
大概就是这样了,反正更多细节的话就你在你打比赛的时侯再和你说吧。」
「听起来有点复杂」
「唔,反正就按照顺序做题,然后越快做到就越好,具体扣多少分也不太需要弄得太清楚…啊,对了」
「嗯?」
「还有一件叫rating的东西」
差点就忘了和瑾茕说这个挺重要的事情了。
「基本上,rating的多少就代表着你的实力大概去到哪里。当然,这并不是绝对的,只是让你有个比较好的参考而己。
每次打完一场比赛之后,根据那一场比赛的排名,rating可能会上升或者下跌。唔,不如打开一下让你看看吧」
比起我在一直在旁边说,还是直接展现给瑾茕看比较方便。
「啊,好哇」
她点了点头,露出了浅浅的笑容。然后在我登入帐号,准备打开比赛纪录的时侯,瑾茕便把椅子搬到了我的旁边,坐了下来。
「这个就是我rating的变化了…能看到吗」
在意识到她靠过来后,我往旁边望了望。
她正在单手托头,露出了十分专注的神情,正盯着眼前的屏幕。
「嗯,能看到」
「例如这一场我打到第41名,rating就升了17分,然后这场突然掉了100多分的就是我打到一半有事做就跑路了…但是其实rating一时不小心掉下去的话,也可以很快就能打上去。
然后你一开始打比赛的时侯,波动应该会非常大,但慢慢就会稳定下来了。」
「话说,我有个东西有点好奇」
瑾茕微微点了点头,然后望向了天语。
「说吧」
「我想知道rating的变化是怎样计算的」
「…是一个相当麻烦的问题呢」
其实没想到瑾茕会对这个东西感到好奇…不过仔细想想的话,也算是正常。
一个OIer平常写算法写得多的时侯,就自然而然地想搞清楚各种数值的机制,因为自己平常也是这样,所以也能够理解到她的想法。
「唔,如果太麻烦的话…」
「没关系,反正就像是平常和你说算法一样」
我大概知道瑾茕打算说些什么,所以便直接打断了她。
之所以说出「相当麻烦」之类的话,其实也只是下意识的行为,也没有嫌麻烦不想教她的意思。
「让我稍微找一下官方发过的blog,没记错的话就是应该就是叫做Opencodeforcesratingsystem…啊,找到了」
「…Elo评分机制?」
「咦,你居然知道这个吗?」
「稍微有听过,但是不太清楚是怎么一回事。只是知道国际象棋的评分也是用这个计算方式」
「唔,那么要我仔细说一下吗」
「嗯」
「简单来说的话…在某一场比赛当中,我们首先要做的东西是要根据某一位选手当前的rating,和其他参赛选手的rating进行对比,然后预期他当场比赛的排名。
而想要计算某人的预期排名的话,就要用到Eloratingsystem的公式了。
ri和rj分别是选手i和选手j的当前rating,然后通过这一条公式,就可以算出来第i位参赛选手比第j位选择成绩更好的机率。
可能光看公式的话不太直观,可以稍微代一下数字进去。
如果rating的差距是200分的话,rating比较高的人胜率是0.75左右,而如果rating差距是400分,胜率就会变成0.9了」
「然后对于每一个参赛选手,都计算一次其他人对上他的胜率,然后加起来就是预期的排名了?」
「没错,但是最后要再加1,因为是排名是从1开始数起的。而这样计算的话就可以将Elo机制就可以作用于多人的比赛了。
然后如果实际上的排名比起预期的排名更高rating就会增加,相反如果比预期的排名更低便会跌分了。到这里还可以理解吗?」
「嗯,可以」
「好了,那接下来就到了具体变化的数值的计算了。
首先把你当前的排名和预期的排名几何平均一下(相乘再开根号),得出了另一个排名m,其实就是将你预期的排名往你实际的排名靠近一下。然后就用二分法就可能找出来这个排名m对应的rating大概是多少。
我打开一下比赛的standing给你看看…在榜单的最右边你是不是可以看到红黑色的数字,那个就是该排名对应的standing了。
然后,就把排名m对应的rating和你当前的rating平均一下(相加再除以二),就得到了新的rating了。」
「所以…这样就完结了吗?」
「还没有,因为还有数值膨胀的这一个问题需要解决。
其实按照这个算法可以预想到,随着新用户的加入,最强的那群选手的分数会不断升高。因为新用户会有底分1500分,而这个算法会令大家rating的变化的总和大致为0。」
「所以如果不进一些修改的话,新用户的分数就会被高分的人『吃掉』?」
「大概就是这样了。
而官方为了解决这个问题,决定了每一场比赛当中,rating位于前4倍根号n位的选手的分数是不会变化的。
然后在比赛结束后,再统计一下那些选手的rating的变化,加总起来后除以选手的人数。再对全部参赛选手扣除对应的rating的分值,就可以确保最顶尖的那些人rating位于一个稳定的区间里了。」
「唔…大概搞懂了」
瑾茕微微点了点头。
在确认她搞明白了后,我便继续了我原本想要说的话题。
「然后关于rating的话,还有挺多东西可以说的。
首先就是有关于用户id的颜色,基本上不同的rating便代表着不同的颜色。
记位高分的区间大概就可以了,大于1900分就是紫名,大于2100分就是橙名,大于2400分就是红名。
然后最后就是大于3000分的用户,他们的id最前面的一个字符会变做黑色,所以平常会叫做红黑名,基本上他们就是全世界最强的那一群人了。」
「那,天语你现在是多少分」
「唔,现在是在2900上下徘徊着,一个月前运气好打上过2982分,但反正我是没有上过3000分的」
「还差一点吗…」
瑾茕低下了头,然后低声地咕噜着。
…是为我感到可惜吗?其实也不是多大的事情。
「我倒是觉得,光靠一次运气就上到3000分,和真实地拥有这份实力是两回事。
虽然的确会偶尔渴望可以取得某种成就,同时会因为差那么一点就成功而感到可惜。
但是同时也会意识到,自己的实力其实并配不上这份成就。
甚至其实一场自己发生了失误,但是仍然取得不错成绩的比赛更会令我开心。
因为这样的话,我便清楚地感受到我自己实力的进步,这样对我而言就己经十分足够了」
唔…不小心勾起了一些回忆了,但瑾茕在这里的话,就忍一下吧。
在话语结束,内心的情绪稍微降下来后,我重新望向了瑾茕。
然后才留意到,她正在盯着我看。
就像我发烧的那一次,她贴上来盯着我的眼神一样。
「…天语你露出了平常都不会展露出来的表情呢」
「啊鸣,很抱歉我说了些奇怪的东西,你大概也挺难理解的…」
「没关系的」
瑾茕慢慢向我靠近了过来,然后脸上换上了十分轻松的表情,微微抬起头,望向了我。
「既然我也会在OI的这一条路上继续走下去,那么应该迟早也会能够理解到你的想法。所以也不用觉得自己的想法会奇奇怪怪的,然后担心别人会讨厌你之类的…所以,天语你偶尔如果想说些什么的话,也可以随时说出来的,我是十分愿意听听看的」
唔…
也许未来可能会忍不住的吧,把所有东西都说出来的那一天。
但无论如何也不会是现在。
「怎么话题突然转到了奇怪的地方去了…」
因为和瑾茕的话题逐渐己经偏离了codefoces的事情了,所以我便打算快一点打断她的想法,把话题转回来。
「因为你突然露出了很特别的表情,所以便忍不住说了出来」
「…好吧。」
也对,瑾茕就是那种有话就直说的那种人。
虽然语气好像略显无奈的样子,但是其实自己也不会讨厌她的这种性格。
-----------------------------------------------
后记:
今天赛完NOI了。
是我最后一场的比赛,但是却一点真实感也没有。
也许之后就悲伤感之类的东西会涌现出来也说不定?
然后分数还没有公布,公布了之后再和大家说一下成绩吧。
顺带一提,这次NOI我确信的确是地狱级的难度。等到试题公布了就知道我为什么这么说了。