ACM-ICPC 国际大学生程序设计竞赛亚洲区数据分析：Part 1

Part1 前言篇

在刚刚结束的第43届ACM国际大学生程序设计竞赛亚洲区总决赛（Asia-East Continent Final）中，由中山大学数据科学与计算机学院的三名本科生组成的队伍，在郭嵩山老师的带领下，获得了学校亚军，同时获得了2019年参加第43届在葡萄牙举行的国际大学生程序设计竞赛全球总决赛资格。

据悉，该赛事吸引了全国380余支队伍，180多所高校计算机领域的顶尖选手参加，是国内大学生计算机学科的最高赛事，获奖选手得到了各大著名IT企业的青睐。

图1：比赛颁奖现场，左二至五为中山大学教练张子臻，选手王凯祺、范俭豪、黄镇。

ACM/ICPC是由美国计算机协会（Association for Computing Machinery）于1970年发起组织的国际大学生程序设计竞赛（International Collegiate Programming Contest, 简称ACM-ICPC），是一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。

经过近40多年的发展，ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛，被誉为计算机软件领域的奥林匹克竞赛，到2018年底为止已经举办了43届。赛事由各大洲区域预赛（regional）和全球总决赛（world final）两个主要阶段组成。

根据各赛区规则，每站前若干名的学校自动获得参加全球总决赛的资格，决赛安排在每年的3-4月举行，而区域预赛一般安排在上一年的9-12月举行。一个大学可以有多支队伍参加区域预赛，但只能有一支队伍参加全球总决赛。

ACM/ICPC以团队的形式代表各学校参赛，每队最多由3名队员组成，每位队员必须是在校学生，取得学士学位超过两年或进行研究生学习超过两年的学生不符合参赛队员的资格，并且最多可以参加2次全球总决赛和5次区域选拔赛。

区域赛一般分别按10%，20%，30%的比例颁发金，银，铜奖。各预赛区第一名自动获得参加全球总决赛的资格，其余总决赛名额按一定规则进行分配。

Part2 分析篇

ACM/ICPC竞赛是计算机学科的盛宴，其历史悠久，影响力大。我们何不把历年的比赛情况数据拿来分析一番？

我们收集了2010年至2018年间中国大陆各高校机构参加ACM/ICPC的情况。（数据来源于互联网，历年中国香港赛区数据没有纳入统计，2018年部分赛区没有采集到数据，数据统计可能稍有偏差）

2.1 获奖情况

部分高校机构历年参加ACM-ICPC中国各区域赛区的获奖情况如下所示（年平均获奖牌数）：

图2：金牌总数统计

图3：银牌总数统计

图4：铜牌总数统计

2.2 基于因子分析的综合排名和聚类分析

2.2.1 历年数据

我们整理了各高校机构历年参加中国各赛区区域赛的数据如下表：

其中特征含义为：

2.2.2 判断数据是否适合因子分析

在执行主成分分析之前，我们需要假设变量之间存在线性相关关系。为此，用KMO检验和Bartlett's检验分析选择的变量是否适合做主成分分析。KMO检验主要用于主成分提取的数据情况。一般来说，KMO检验系数分布在0到1之间，如果系数值大于0.6，则认为样本符合数据结构合理的要求。

Bartlett's检验的原假设是研究数据之间的相关矩阵是一个完美矩阵，即所有对角线上的系数为1，非对角线上的系数均为0。在这种完美矩阵的情况下，各变量之间没有相关关系，即不能将多个变量简化为少数的成分，没有进行主成分提取的必要。因此，我们希望拒绝Bartlett's检验的零假设。

计算结果显示KMO检验系数为0.742，我们认为我们使用的研究数据结构是一般的；Bartlett's检验的显著性小于0.01，拒绝零假设，即认为研究数据可以进行主成分提取。

2.2.3 提取主成分

该输出结果显示了通过主成分分析提取的因子数量为3，提取的因子对所有变量的累积方差贡献率达到81.413%，说明因子对变量的解释能力较好。

2.2.4 因子旋转

为了使因子更具有可解释性，我们进行因子旋转，旋转方法采用最大方差法。旋转的目的在于调整变量在各因子负荷量的大小，旋转后变量在每个因子的负荷量不是变大（接近1）就是变得更小（接近0），这就使对公因子的解释变得更容易。

上图为旋转后的成分矩阵，第一个因子上载荷量绝对值较大的为’solved_avg’、’time_avg’和’rank_avg’，其中’rank_avg’与第一个因子呈负相关，因此第一个因子主要反映的是一所学校学生程序设计能力的平均水平。

第二个因子载荷较大的变量为’silver_sum’、’bronze_sum’和’team_sum’，主要反映学生参赛的积极性。

第三个因子载荷较大的变量为’gold_sum’和’final_sum’，反映的是竞赛成绩的拔尖程度。

2.2.5 因子得分和综合得分

下面是得到因子得分的散点图分布：

图5：基于3个因子的散点图分布

由于该三维图不易于观察，我们将其投影至二维。

图6：因子1和因子3得分的散点图分布

图7：因子2和因子3得分的散点图分布

我们得到的3个因子分别从不同方面反映了各个高校机构参加ACM/ICPC的总体水平，单独使用某一公因子很难做出综合评价，因此考虑以各公因子对应的方差贡献率比例为权重计算综合得分情况。计算综合得分的公式为：

综合得分 = （因子1的贡献率/总贡献率）*因子1上的得分+（因子2的贡献率/总贡献率）*因子2上的得分+（因子3的贡献率/总贡献率）*因子3上的得分

即FAC_sum= (30.936/81.413)*FAC1_1 + (29.213/81.413)*FAC2_1 + (21.264/81.413)*FAC3_1

得到部分综合得分及综合排名结果如下：

注意该排名不是实力排名，而是基于选取特征下的综合排名。

2.2.6 基于因子分析的聚类

我们根据3个因子的得分，对各个高校机构进行了K-means聚类分析，将495个高校机构分为5类（K=5），得到每个聚类中的案例数和最终聚类中心如下图：

通过5个类的最终聚类中心情况，我们可以看到聚类第3类高校机构的学生程序设计能力是比较强的，同时参加ACM/ICPC取得的成绩是非常拔尖的，这类高校机构综合排名也是最高的，第3类高校机构如下图：

同时，可以看到聚类第2类高校机构的程序设计能力平均水平也是较强的，但是他们的参赛积极性很低，可以判断该类是以一些非高校为主的组织机构，第2类高校机构部分如下图：

（未完待续）

---The End---

文案 ：郑光柱（中山大学数据科学与计算机学院本科四年级， 1030477833@qq.com）

编辑 && 排版：邓发珩（华中科技大学管理学院本科二年级：2638512393@qq.com）

校对 ：邓发珩（华中科技大学管理学院本科二年级：2638512393@qq.com）

指导老师： 张子瑧（中山大学数据科学与计算机学院副教授，zhangzzh7@mail.sysu.edu.cn）