ACM／ICPC亚洲区预选赛命题经验谈
摘要：ACM国际大学生程序设计竞赛，是世界上规模和影响力最大的大学生程序设计竞赛。从2008年至2010年，笔者依托北京大学，先后承担了国内4次亚洲区预选赛的命题工作，积累了一定经验，也有一些教训，写出来与大家分享，希望对兄弟院校今后的命题工作，以及ACM/ICPC选手和教练们有参考价值。
关键词：ACM/ICPC；亚洲区预选赛；题目；数据；算法
1ACM/ICPC的题目形式、赛制及中国区命题的现状
ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest，简称ACM/ICPC)是全球规模最大，最有影响力的大学生程序设计竞赛，它始于1970年，到2010年为止已经举办了35届。
ACM/ICPC的形式是三名队员在5小时内用一台电脑编程解决8～12道题。每道题由英文题目描述(题面)、标准输入数据和标准输出数据三部分组成。英文题面中包含很小一部分输入数据及其对应的输出数据，以作为Sample(样例)。参赛者须根据题目描述编写程序，该程序读
学编程用什么电脑最合适入标准输入数据，其输出必须和标准输出数据完全一致，而且要在题目规定的时限内(通常是两三秒，超过10秒的极少)算出结果，才算通过该题。完整的标准输入数据和标准输出数据选手们是看不到的，选手的程序提交到裁判的机器上，裁判以标准输入数据作为输入运行其程序，然后取得该程序输出结果和标准输出数据进行比对，以判断该程序是否通过。必要时也会用人工来比对输出结果。比赛最终以通过题目的数量多少来决定名次，过题数相同的，以做题速度区分高下。
例如，著名的“A+B Problem”，题目就是：输入两个数，请输出他们的和。标准输入数据是成对的数，标准输出数据是每对数的和。当然，真实的竞赛是不会有这么简单的题目，这里只是用它来说明题目的形式而已。
ACM/ICPC的竞赛题，都是需要编程解决的问题。因此，一道完整的题目，除了英文题面、输入和输出数据外，命题者还要提供标准程序(标程)。标程必须在题面规定的时限内，由标准输入数据计算出标准输出数据。
ACM/ICPC的赛制是每年的9月到12月在各大洲进行预选赛，选拔出优秀队伍100支左右参加第二年3、4月份进行的全球总决赛。
目前，在预选赛阶段，中国大陆有5个赛站(赛站并不固定)。因此，每年有5个大学会承办ACM/ICPC亚洲区预选赛。例如，2010年，哈尔滨工程大学承办哈尔滨赛站的比赛，天津大学承办天津赛站的比赛，浙江理工大学承办杭州赛站的比赛，四川大学承办成都赛站比赛，福州大学承办福州赛站比赛。
中国的大学申办ACM/ICPC亚洲区预选赛比较踊跃。但是，有信心或愿意独自命题的学校并不多(为何如此后文会解释)。因此，许多大学在承办比赛时，会委托ACM/ICPC实力较强的学校代为命题。除北京大学外，复旦大学、浙江大学、中山大学都曾为别的大学举办的亚洲区预选赛命题。
笔者依托北京大学，从2008年至2010年，先后为国内4次亚洲区预选赛命题。这4次比赛的承办者分别是：北京交通大学(2008年)、浙江大学宁波理工学院(2009年)、浙江理工大学(2010年)和福州大学(2010年)。
表1是最近11场中国大陆亚洲区预选赛的比赛结果统计，其中打星号的比赛由北京大学负责命题。
北京大学的命题区分度好、难度适中，从未Rejudge (因题目错误，或其他原因导致必须对选手们提交的程序重新评判)，因而获得参赛选手和教练们的广泛好评。2009年ACM/ICPC中国区指导委员会曾经评选过“优秀命题奖”，北京大学获得此项荣誉。
2ACM/ICPC对题目的要求
笔者从2004年起担任北京大学ACM/ICPC竞赛教练，率队参加过二十多次亚洲区预选赛和六次总决赛，此外还有一定命题经验，因而对什么题目是ACM/ICPC的好题，有一点自己的看法，希望能与大家探讨。
笔者认为，一道ACM/ICPC的好题，应该满足以下条件：
1) 题面和数据正确。这是最基本的要求。其中，常见的错误是输入数据的范围超过了题面所说的范围。
2) 题目描述易于理解，没有歧义。中国人用英文写题面给中国人看，如果出题者不仔细斟酌，不同人读题很可能就会有不同的理解。选手按错误的理解去编程，就是一场灾难。这样的题目，必然会遭人诟病。虽然赛场上可以在有人提问后发现二义性问题并且发Clarifica
tion予以澄清，但还是比较狼狈的。
3) 数据要足够强。所谓足够强，有两个方面的含义，一是指数据里应包含各类边界条件、特殊情况等(如果有的话)，使得做题者一旦有某个地方考虑不周，就会得出错误答案；二是数据应尽可能让那些算法时间复杂度比标程高五六倍的程序不能在题目规定的时限内算出结果。这第二条有相当的难度，因为，有些程序的算法，其平均复杂度并不比标程更高，只有在最坏情况下才会比标程慢很多，为了要卡住这样的程序，设计的数据就要包含各种投机取巧算法的最坏情况，使得那些算法无法通过检验。
4) 程序需要有一定的代码量。毕竟这是程序设计竞赛，如果十几行代码就能完成，就算题目设计精巧，思路巧妙，也难说是个好题。当然，比赛中最简单的题目，可以不作此要求。
5) 题面不能太短，而且要有一个故事。题目最好不要是纯粹的一个已经抽象好的算法或数学问题，应该用一个故事将这个问题包装起来，这样才能对参赛选手的英文阅读能力和问题的抽象能力有一定要求。
6) 题目要有新意。不要和陈题类似，也不要单纯地、不加变化地考某个算法，即不要让选手照抄某个算法的模板就能通过，最好让选手在建模上就需要花费时间思考。
在满足上述几条的基础上，若还能一题多解，则更是锦上添花。
由上所述可以看出，ACM/ICPC竞赛题，尤其是中等以上难度的题目，对命题者有很高的要求。命题者不但英文要好，而且还要考虑问题足够缜密；不但要通晓题目所用到的算法原理，而且还必须具有编程实现该算法的能力；当然，还要有一定的想象力和创造性，才能编出有新意的题目，包括题目里的故事也要生动有趣。
ACM/ICPC命题费时费力，对于没有参赛经验的人来说，哪怕是专门研究算法的教授，出一道好题也并非易事，何况教授们往往也不愿意在此事上花费精力。所以，到目前为止，国内亚洲区预选赛的绝大多数题目，都是由ACM/ICPC的现役或退役选手编写的。对于ACM/ICPC实力不强的学校来说，没有足够多的高水平选手，为亚洲区预选赛命题就成为一项比较困难的任务。所以，许多承办亚洲区预选赛的大学，往往请别的学校代为命题，或自己出一些相对简单的题目，委托其他学校出难题。
前面说了一道题怎样才算好题，下面再来谈谈一套什么样的题才能算好题。
ACM/ICPC官方提到过，一套好题应满足以下三个条件(当然不要出错是起码的)：
1) 每个参赛队伍至少能通过一道题。
2) 每一道题目都有队伍能够通过。
3) 没有队伍能够做出所有的题目。
这三个条件得到了大家的广泛认可。但是以笔者经验看，一套题目，只满足这三个条件，还不足以称为好题。笔者个人认为，一套好题，还应该满足以下条件：
4) 比赛结果有足够的区分度。
5) 第一名至少能过7道题(一般比赛都是10道题)。
6) 题目覆盖知识面要比较广。
7) 题面长短搭配合适。
8) 题目要求有一定的代码量。
上述的第1条，并不容易做到。因为现在每个赛站参赛队伍多达120支到150支，有的队伍并非是经过网络预选赛选拔出来的，而是主办方为支持当地竞赛发展而邀请的，队伍水平有限。为确保所有队都能过题而出一个像“A+B Problem”这样的题，没有意思，也不是命题者所愿。在中国大陆2009年和2010年共10场亚洲区预选赛中，只有3场做到了所有队都能至少能通过一道题。
第2条也不容易做到。为了防止有参赛队能做出所有的题而使题目显得太简单，或希望通过出难题来显示水平，许多学校会出一两道难度很高，甚至根本不可做的题来压轴。这样的题目，往往导致没有人通过，甚至根本没有人提交。因此，在亚洲区预选赛上，2道题无人能过的现象也不少见，在2009—2010年的10场比赛中，其中5场有2道题无人通过，仅有4场是所有题都有队伍通过。
第3条是普遍现象。在中国大陆赛区，2010年前从来没有一支队能在比赛时通过所有的题目。2010年的哈尔滨赛站，第一次出现了一个队做完所有题目的情况；在后来的福州赛站，则有3支队通过了所有的题。
第4条非常重要，笔者甚至感觉区分度是大多数教练判断一套题目好坏的最重要标准。如果
同样的题数的二、三十支队，一半得银奖，一半得铜奖，那么落后的队伍必定心中不服，认为该场比赛偶然性太大。
第5条指的是题目不可太难。国内的比赛曾经不止一次出现过冠军只做了4道题的情况，这样的题目，必然区分度也不好，是很难得到大家好评的。
第6条，一套题目一般应该覆盖到以下算法类型：搜索、计算几何、图论、数学、动态规划、数据结构、模拟。
第7条，因为总决赛题面一般较长，英文阅读能力对于总决赛上取得好成绩也比较重要，因此笔者认为短题目不应太多。
第8条，毕竟是程序设计竞赛，不能光靠思考能力取胜，代码编写能力也很重要。因此题目应该要求有一定的代码量，这也和总决赛的要求吻合。
3北京大学命题的指导思想
笔者一般按照以下几条指导思想进行命题：
1) 题目的难度分布一般是2道最简单的题，2道中等偏易题，3道中等难度题，3道难题。希望一个半小时内能有队伍通过4题。
2) 比赛时不可能做出的题不出。
3) 最容易的题目应该是开赛10到15分钟即被做出，但很弱的队，也要等到最后一小时才能将其通过，这样的题才有技术含量。
4) 倾向于让选手们多过题，希望第一名能通过9题。选手们辛辛苦苦训练一年，为的就是体验在赛场上过题的感觉，那么命题者就应尽量让选手们多体验一下这种感觉。因此，题目不可太难。但是北京大学近来4次的命题，总有10支左右的队伍一道题也做不出，这是否和让选手们多过题的思想矛盾呢？其实不然。因为在我校出的题目中，最简单的题目一般都是用多重循环穷举即可解决的，这样的题目如果5个小时都做不出来，只能说明做题的队伍根本没有经过任何训练。没有付出，自然也应该没有收获。
5) 计算几何、搜索、动态规划是必考的。计算几何还常考两道，其他题型基本上也都能覆盖到。
6) 题面一般较长，向总决赛靠拢。笔者倾向于去掉Sample Input(输入样例)和Sample Output(输出样例)的部分就应该至少占满一页纸。
7) 强调代码实现能力。
4北京大学命题的过程
从2008年至今，所有题目都由北京大学在校的ACM/ICPC现役/退役队员，以及笔者编写。共有10名队员参加过ACM/ICPC亚洲区预选赛的命题，他们全部获得过亚洲区预选赛金奖，其中8名队员参加过总决赛。每套题目一般有6～7名队员参与命题。出题和验题的是同一班人马。每道题由两个人验，每个人出一道题，就要验两道题。出题者须写承诺书，承诺不得向任何命题组以外的人提及有关题目的任何信息。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。