ACM北大命题经验

ACM/ICPC亚洲区预选赛命题经验谈北京大学信息科学技术学院郭炜北京大学除了自己办的两届比赛外，从2008年至2010年，先后为国内4次亚洲区预选赛命题。这4次比赛的时间和承办者分别是：2008年，北京交通大学；2009年，浙江大学宁波理工学院；2010年，浙江理工大学；2010年，福州大学。比赛时间地点参赛队数过0题的队数总题数没人过的题数现场最多过题数金奖题数银奖题数铜奖题数2008北京100101009N/AN/AN/A2009宁波1301610086-84-53-42010杭州138610185-84-52-42010福州15310100107-105-72-5注：有几场比赛的现场最多过题数，和金奖最多题数不一致，是因为在这些比赛中，过题最多的队伍都是不参加排名的队伍一道ACM/ICPC的好题，应该满足以下条件：1.题面和数据正确。(其中，输入数据的范围超过了题面所说的范围，也算是一种常见的错误)2.题目描述易于理解，没有歧义。3.数据要足够强。4.程序需要有一定的代码量。5.题面不能太短，而且要有一个故事。6.题目要有新意。不要和已有的陈题很像，一套题怎样才算好题ACM/ICPC官方提到过，一套好题应满足以下三个条件：1.每个参赛队伍至少能通过一道题。2.每一道题目都有队伍能够通过。3.没有队伍能够做出所有的题目。个人认为一套好题，还应该满足以下条件：4.比赛结果有足够的区分度。5.第一名至少能过7道题(一般比赛都是10道题)。6.题目覆盖知识面要比较广。7.题面长短搭配合适。8.题目要求有一定的代码量。北京大学命题的指导思想1．题目的难度分布一般是2道最简单的题，2道中等偏易题，3道中等难度题，3道难题。希望一个半小时内能有队伍过4题。2．不出比赛时基本不可能做出不可做的题。3．最容易的题目应该是开赛10到15分钟即被做出，但很弱的队，也要等到最后一小时才能将其通过，这样的题才有技术含量。4．倾向于让选手们多过题，希望第一名能过9题。选手们辛辛苦苦训练一年，为的就是体验在赛场上过题的感觉，那么命题者就应尽量让选手们多体验一下这种感觉。因此，题目不可太难。但是北京大学近来4次的命题，总有10支左右的队伍一道题也做不出，这是否和让选手们多过题的思想矛盾呢？其实不然。因为在我校出的题目中，最简单的题目一般都是用多重循环穷举即可解决的，这样的题目如果5个小时都做不出来，只能说明做题的队伍根本没有经过任何训练。没有付出，自然也应该没有收获。6.计算几何、搜索、动态规划是必考的，计算几何还常考两道。其他题型基本上也都能覆盖到。7.题面一般较长，向总决赛靠拢。笔者倾向于去掉SampleInput(输入样例)和SampleOutput(输出样例)的部分就应该至少占满一页纸。8．比较强调代码实现能力，模拟题常考。北京大学命题过程所有题目都由北京大学在校的ACM/ICPC现役或退役队员，以及笔者编写。共有10名队员参加过ACM/ICPC亚洲区预选赛的命题，他们全部获得过亚洲区预选赛金奖，其中8名队员参加过总决赛。每套题目一般有6至7名队员参与命题。出题和验题的是同一班人马。每道题由两个人验，每个人出一道题，就要验两道题。出题者须写承诺书，承诺不得向任何命题组以外的人提及有关题目的任何信息。北京大学命题过程首先确定要参加命题的同学，然后再确定题目的类型（即要考查的算法）分布和难度分布，接下来就是根据每个同学的长处，以自愿加指定的方式，为同学们分配题目类型和难度。简单题也必须有点新意，要有一个好故事。等题目有了想法后，将想法说出来同学们讨论。根据大家的评价来判断题目的难度是否合适。接下来就是写出完整的题目，以及验题。根据验题者的表现重新评估题目难度。偶尔会发生需要增减难度的情况，一般都可以通过修改题目条件完成。学生的英文普遍不够好，写出来的题面往往晦涩难懂，歧义较多。因此，教师需要修改甚至重写每一道题面。随着学生年级增长和经验增加，他们写的题面也越来越好，修改题面的工作就会轻松一些。命题注意事项1.最难的两三道题应难度基本相同，不能有一道明显最难。2.再难想的题目，都不用怕没人能做出来；代码量大、难写的题目，才需要担心没有人过。4.不要出需SpecialJudge（答案不唯一，要特殊评判）的题目，因为用来评判选手输出数据是否正确的那个SpecialJudge程序，其自身正确性往往难以验证。5.题目时限应尽可能短，大部分题目应该时限都是3秒以内。这样可以加快裁判速度。尤其是简单题，不要设10秒这样的长时限，否则由于提交次数多，裁判时间长，会导致许多选手因不能及时得到裁判结果而抱怨。6.题目的输入输出数据不要太大，10M以内为宜，大多数题目应2M以内。简单题或有陷阱的易错题，由于提交次数多，更不能有体积大的输入输出数据。7.输入数据应该有明确的结束方式（比如以两个0结尾，或数据开头就指明testcase的数目），不要让程序读到EOF了才能判断数据已经结束。8.出题者有时会为了看数据方便，在数据里多个case之间加空行，最后要注意去掉。9.对于每道题，出题者都要专门写一个验证数据范围的程序，输出每个变量的取值范围，看是否和题面描述吻合（不能超范围，也不能范围远小于题目所说）。此外还要看会不会出现无意义的数据，比如0的0次方，除数为0等。10.由于可能改了题面，改了数据而忘了改Sample(数据样例)，甚至文字编辑软件有可能自动将Sample里的某些字母变成大写，所以交付前一定要专门将SampleInput和SampleOutput从题面里拷贝出来，分别存为两个文件，然后以SampleInput文件作为输入运行标程，生成输出结果再比对SampleOutput文件。比对不能用眼睛看，一定要用文件比较程序。11.要检查题面中SampleInput和SampleOutput里各个数据出现的次序是否和题目描述的一致，SampleInput数据有没有超范围。12.题面由别人改过后，一定要让出题者再看一遍。13.在最终发布之前，要把上述9至11条全部重新做一遍,尤其是第10条，很容易被忽略。致谢感谢：北京交通大学李清勇老师，浙江大学宁波理工学院蔡明伦老师，浙江理工大学叶海荣老师，福州大学吴英杰老师在命题过程中给予的支持。感谢ACM/ICPC中国区指导委员会秘书长周维民教授在百忙中为笔者提供了近两年的中国大陆亚洲区预选赛比赛结果的原始数据。新书：ACM国际大学生程序设计竞赛亚洲区预选赛真题题解电子工业出版社谢谢大家！