原题连接

世界杯特别场 TopCoder Marathon 101: World Cup MM 地址.


问题简述:

  • 给你30个球员,球员$i$有3个属性,$atk_i$(进攻)、$def_i$(防御)、$agg_i$(犯规);
  • 每个球员是3种职业之一,$F$前锋、$M$中锋、$D$后卫(不考虑门将);
  • 一个球员如果职业是前锋,那么$atk$属性乘$2$,$def$属性置$0$;如果是中锋数值不变;如果是后卫$def$属性乘$2$,$atk$属性置$0$;
  • 你只需要分配除门将以外的10个位置的候选人,比如:第$p$个位置候选人为$List_p$;
  • 每个人可以属于多个候选位置(这条信息非常容易漏掉,问题没有刻意强调,实际是可以的);
  • 但每个位置只能分配同一种职业,也就是当前上场的候选人只能以这种身份上场结算;
  • 场面上的队伍的得分计$Score=min(sum(atk{player}), sum(def{player}))$;
  • 赛场分5阶段进行,第一阶段按你排出的10个位置的候选人表的每个位置的第一个选手上场,之后每一场进行一轮结算,对每个选手按$agg_i$属性进行随机,随中了就吃一张黄牌,2张黄牌就下场,另外每个人还有$rate$的几率受伤下场($rate \in (0, 0.05)$);
  • 如果一个队员下场了,那么立刻从其候选列表找出下一个没有出现过的队员上场(注意:一个队员可能在别的候选集已经提前上场了)
  • 另外,这个问题中提供了一些阵容的概念,即在场的队员中拥有某个$group_j$集合里的全部球员,那么这些球员的基础属性分别增加$atk_j$、$def_j$、$agg_j$;
  • 注意几点:$atk_j$、$def_j$、$agg_j$可能有正有负;每个人都加这么多,且在结算前锋时用$2*(atk_i + atk_j)$,同理后卫;一个人可能同时属于多个阵容,那么就每个阵容的加成都获得;
  • 优化目标:5轮结算完成后,取5次结算后的总积分作为本次比赛的得分,得分越大越牛逼。

赛程回顾

这场比赛参与的人数不多,估计又和随机有关,不过这个问题其实受随机因素影响并不大,其标准差只有均值的5~7%左右,所以不用太考虑one hit问题也不会太坏。

因为最近加班已进入疯狂状态,导致我能调试的时间非常少,大多时候只能利用休息的间隙在脑海里yy一些思路。其实,也并没想出什么牛逼的方法,只用了一些中规中矩“随大流”的方法来处理,其实结果还不错。大致来说就是分阶段分别进行:快速海选种子解,对种子解进行粗过滤选出精英解,对精英解进行爬山选出最优精英,再把剩余的时间用在这个解的迭代上。

最后排11,还算满意。可惜的是对问题的理解上有一些偏差,并不知道每个选手可以分配在多个候选人集合里,错过了一些更优解。不然可能能进前十,略遗憾。不过这场过后marathon rating也终于进入yellow coder了,期待rating能继续涨下去,今年涨势真是喜人。


思路梳理

问题的评估:

  • 这个问题严格上来说,每个位置安排3-4个人基本就足够了,因为首先比赛只有5轮,而每轮每个位置一个球员受伤的概率平局只有2.5%,也就是整场比赛平均只有1-2个人因受伤淘汰,另一方面,犯规要2轮才淘汰,即每组成员最多能被淘汰两个人,所以安排3~4个人基本能满足全场不会缺人的状态。实际测试表明,一般情况下,整场比赛极大概率不会超过3个人被替换。
  • 所以,我们可以把搜索的精力集中在首发阵容和每个位置的前2个替补队员身上即可。

我的主要策略:

不过我在比赛过程中,对题目有一些误解,主要是没有发现一个队员可以放在多个替补的位置上,这使我缺少了一个优化方向,因为数据好的替补队员,你要让他有更大的几率上场才行。

言归正传,虽然有一些错误的理解,但基本不影响整个方案的实施与运行。

首先,将问题分为3个主要阶段:

  • 第一阶段,搜索尽可能好的首发阵容,包括,10个成员是谁,以及每个成员的赛场位置(F、M、D),赛选出$top K$的候选集;
  • 第二阶段,对第一阶段挑选出的首发阵容的成员,按贪心的思路依次补全前$k$个候选集方案的替补队员,并进行若干次比赛的随机模拟,将成绩最好的$top M$个队伍挑出来;
  • 第三阶段,对最好的$top M$的队伍,分别进行基于模拟退火的迭代操作,使其获得更好的表现,最终去除最优的一个座位解输出。

具体的细节总结:

  • 第一阶段的搜索如何评价? 只进行5轮模拟中的第一轮模拟,计算分数即可。
    这里算分有个小技巧:
    你可以把FMD标记为job=0,1,2,那么一个人的$real\_atk = atk (2 - job)$ 以及$real\_def = atk job$。
    这个技巧可以便于后期的模拟退火的迭代加速。

  • 第二阶段的如何构造一个阵容? 随机!${n \choose k}$,而$job$采用梯度下降来迭代。
    这里有个在蒙特卡洛方案下减小迭代成本的技巧,只针对job的迭代有效。
    我们可以先用蒙特卡洛模拟$N$次,并记住每次每轮每个位置上队员的$atk$与$def$值,记为atk[simu_id][round_id][pos],def[simu_id][round_id][pos].我们在改变某个位置pos对应的job时,只需要枚举simu_id与round_id并计算atk与def的变化差值即可。

    diff = new_job - job;
    _t_atk[simu_id][round_id] = atk_sum[simu_id][round_id] + atk[simu_id][round_id][pos] * diff;
    _t_def[simu_id][round_id] = def_sum[simu_id][round_id] - def[simu_id][round_id][pos] * diff;
    _t_scores[simu_id] += min(_t_atk[simu_id][seg], _t_def[simu_id][seg]);

    这个优化方案可以只采用一个蒙特卡洛就进行局部优化,但是注意因为随机的原因小小过拟合问题。因为数据不是完备的,所以迭代出来是基于这个数据集的。

  • 第三阶段怎么迭代? 模拟退火的操作,只有一种:交换某两个球员的位置,并相应的用第二阶段的方法迭代job,并将最优解作为这个迭代的解。

  • 主要的提升来源于第二阶段的这个低成本迭代job的方法,这使得问题在job这个维度上复杂度大大降低,以至于几乎不需要成本进行计算。

被遗漏的优化点:

  • 其实这个问题已经做得很不错了,不过丢失了一个关键的信息,就是一个替补可以在不同的队伍里。这样可以把顶级后卫或前锋尽可能排在各个替补的前面。其实最后和排第一的选手差距并不大,可能主要缺的就是这里了。略遗憾。

  • 这次大佬们好像没提供太多启发性思路,就不总结了。