AGM—ICPC训练方法与竞赛策略

王春平　王卫红　韩姗姗　李曲　方赵林

摘要：ACM-ICPC竞赛规模日趋增大，为了提高训练效率和竞赛成绩，文章依据ACM-ICPC的知识范畴，提出程序设计的训练方法和相应的竞赛策略，引导和增强学生的程序设计能力，提出在比赛中采取正确的组队策略、团队合作策略和答题策略。

关键词：ACM-ICPC；程序设计；训练方法；竞赛策略

0 引言

ACM国际大学生程序设计竞赛（ACM Inter-national Collegiate Programming Contest，ICPC）是由美国计算机协会（Association for ComputingMachinery，ACM）主办的一项旨在展示大学生创新能力、分析和解决问题能力、在压力下编写程序能力和团队精神的年度竞赛，迄今为止已经举办了37届。大陆高校从1996年开始举办比赛，目前中国赛区拥有5个站点，参赛队伍稳定在150支以上。随着国内高校参赛规模的增大，获取好成绩的难度也越来越大。

1 知识范畴与训练方法

程序设计是计算机科学领域的基础技术，涉及几乎所有的计算机基础课程。要提高学生的程序设计与应用能力，教师必须有规范的训练方法，并加以正确引导，才能达到学以致用的目的。计算机程序作为一种管理和数据分析手段，已经渗透到几乎所有的行业，而ACM-ICPC的竞赛题目有很大一部分是来自计算机实践的抽象，要想很好地解决这些问题，学生必须掌握相关知识点，拥有熟练的编程调试技术以及顽强不屈的心理素质。

1.1 知识范畴和基础编程

ICPC竞赛涵盖的知识面非常广泛，主要由以下几部分构成。

（1）数学基础：算法复杂性分析方法、概率论、代数学、组合数学、博弈论、数论等。

（2）数据结构：基础数据结构、集合、排序算法、堆、树等。

（3）图论：图的分类与遍历、二分图、网络流等。

（4）计算几何：向量、点与多边形、平面交等。

由于ICPC只是作为培养学生编程兴趣的一种手段，学生在有限时间里要全面学习掌握这些知识点非常困难，因此，知识点的学习可根据组队有针对性地进行，尽量使同一个参赛队伍中的队员之间相互补充。例如，队员1侧重学习计算几何，队员2和队员3则可分别偏重学习数学知识和数据结构，这使得组队可能在短时间内获得更好的比赛成绩。从长远来看，要想成为一名优秀的参赛队员，学生须具备“一专多能”的能力，“一专”是精通至少一种类型的不同难度题目，“多能”是指能解决其他类型的一般题目，这样的队员所组成的参赛队伍往往会有1+1+1>3的比赛效果。

在编程技术方面，ICPC竞赛主要采用2种程序设计语言：C/C++和Java语言。C/C++语言作为传统的编程语言，在竞赛中拥有很多优势，而Java语言也有自己的特点。Python和C#等语言近期也逐渐被各竞赛系统所支持。不论采用哪一种语言，可分为以下3个方面来训练：①基础语法训练：任何微小的语法和编译错误在赛场上都是一种损失；②STL技术：至少熟练掌握一种语言如C++的STL（Standard Template Library）模板；③基本题型训练。这些基础的编程训练都将在赛场上减少不必要的罚时，可以为各组争取更好的结果。

1.2 求解方法分类

ICPC竞赛同其他算法竞赛一样，训练时需要对求解方法有针对性的训练。求解方法的主要分类包括：穷举法、分治方法、动态规划法、贪心法、回溯法、分支限界法和线性规划法。

穷举法又称为暴力法（Brute Force），是使用比较普通也是最朴素的解题方法，但是时间复杂度非常高，实际解题时往往需要同其他方法进行结合。

分治法是指将难以直接解决的大规模问题分割成一些规模较小的相同问题，以各个击破、分而治之，比较典型的问题有全排列问题、汉诺塔问题等。

动态规划法指解题过程中的每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，这种多阶段最优化决策解决问题的过程就称为动态规划。动态规划法一般采用自底向上的求解步骤，学生较难掌握。使用动态规划法求解的典型问题有0-1背包问题、矩阵连乘问题、流水作业调度和最优二叉搜索树等。

贪心法指在对问题求解时，总是做出在当前看来是最好的选择。贪心法的求解步骤与动态规划法相反，通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。比较典型的问题有：散装背包问题、最优装载问题、哈夫曼编码问题、最小生成树和多机调度问题等。

回溯法则是在解空间树上采用试错思想，尝试分步解决一个问题。这种方法实际上是暴力法的一种变形，最坏情况是会导致指数时间的计算复杂度。比较典型的问题有：图的m着色问题、旅行售货员问题和最大团问题等。

分支限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法，但回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在某种意义下的最优解。典型的问题包括：布线问题、电路板排版问题和批处理作业调度问题等。

线性规划法则是最优化问题中的重要领域之一，指在线性等式或不等式的约束条件下，求解线性目标函数的最大值或最小值的方法。其中目标函数是决策者要求达到目标的数学表达式，用一个极大或极小值表示。约束条件是指实现目标的能力资源和内部条件的限制因素，用一组等式或不等式来表示。比较典型的问题有：最大网络流、最小费用流和网络单纯形问题等。

作为竞赛选手，掌握这些方法并能够在实际解题中进行应用是非常必要的，因此通常的竞赛题目解题方法都在此范围内。另外，笔者没有将搜索排序作为解题方法的基本要求，但实际编程中很少有需要自己写搜索排序算法的，因为一般在编程语言中已经有相应的库函数提供。在初期训练时，动态规划和线性规划应作为训练重点，也是因为此类方法的应用较难，虽然能够掌握方法的原理，但是需要选手具备具体问题具体分析的能力，而其他方法则相对要简单一些。在训练后期，特别是临近比赛时，要尽量避免做陈题，应该多尝试训练新题以增强临场应变能力。endprint

1.3 心理训练

ACM-ICPC竞赛的时间长达5小时，题目数量一般在10～12道之间，可以说，这对队员的体力和脑力都是巨大的考验。实际比赛气氛非常紧张，如在答题的过程中卡题，队员较易出现心理波动，导致发挥失常，因此，注重平时的心理承受能力训练是非常有必要的。当然，心理承受能力的培养并非一朝一夕可以完成，而是一项长期细致的工作。为了增强激烈竞争下的抗压能力，教师可以在平时训练中有意识地设置一些需队员努力才可以完成的难题，并授予奖品或者惩罚，让队员“跳一跳来摘果子”，把学到的对付困难、挫折的方法应用到实际竞赛中去，培养其心理承受能力。

在心理训练层面，一个良好的训练氛围也是不可缺少的。团队中除了培养队员平日训练的默契，也需要队员之间的相互鼓励。但是，在比赛中还有一种情形，就是多次提交后仍不能被判定正确，此时该题如同鸡肋，耗在此题上很容易造成战机的延误.这时需要一个具备心理素质强、有大局掌控力的队长命令大家果断放弃该题。

2 ACM-ICPC竞赛策略

ACM-ICPC是团队竞赛，因此在组队、团队合作和答题顺序上都要有一定的策略。每个ICPC参赛队由3名队员组成，这种奇数规定不是偶然的，而是ACM-ICPC主办方长期经验积累的结果。在1993年以前，参赛队是由4名队员组成，经过各主办方的长期观察，发现这样很容易导致队伍分成2个小组，其中一个小组（2名队员）使用电脑输入程序，另外一个小组则在纸上讨论下一题的求解，这样的情形是与竞赛设计者的初衷背道而驰的，因此ACM-ICPC委员会将成员缩减为3个，这样团队既可作为一个整体，也可以单独行动或者轮换组合。

组队策略一般有3种：强强搭配型、互补型和梯队型。强强搭配型是各高校为了取得最好成绩的常见组合，一般3名队员都是在该校排名靠前的队员，一般高校常用这种集中最优力量的组合来冲击全球总决赛。互补型通常又分为两种：技术互补型和能力互补型。技术互补型的队伍分训由英文阅读能力强、编码能力强和逻辑能力强的3名队员构成，这样可以在技术上相互补充。能力互补型则由知识面不同的队员构成，例如，队员1擅长数据结构，队员2擅长计算几何，队员3擅长图论等。梯队型则是为了完成传帮带的梯队建设需要，让老队员帮助新队员快速成长。

虽然目前在程序设计训练和竞赛中女队员所占比例非常少，但一个训练团队或队伍中如果有女队员的存在，往往会最大限度地激发男队员的学习激情和潜力，最近几年大陆世界总决赛参赛队都有这样的例证。

在团队合作策略上，一般分为3种：完全配合型、独立型和配对型。完全配合型指在全场比赛时间中，整个队伍在同一时刻只处理一道题，三名队员一起读题，编码直至题目被判定正确。独立型则通常出现在强强搭配的队伍中，三名队员能力都很强，一般在开场时就分配好各自任务，然后分头解题，这种策略是奔着最好成绩去的，但存在着集体卡题的危险。配对型则是两名队员讨论一个题目的确定解法后，剩余一名队员负责编码实现，而配对两名队员接着讨论下一个题目，如此循环配合；当然实际操作时，也可进行配对切换。

在答题策略上，一般有顺序答题、从易到难、中档一容易一难等3种答题策略。顺序答题是按照题目的顺序答题，但现在题目的难易程度都是打乱的。从易到难则是比较容易接受的答题顺序，但是实际竞赛中题目阅读实际上比较费时间，有时候也很难确定每道题的难易对比从中档到容易再到难的答题顺序则是一种折衷策略，如果发现有比较容易的题目，则可以留着最后来解决。当然，实际竞赛出现的情况是多种多样的，这也需要队员随机应变。

3 结语

ACM-ICPC的训练方法和竞赛策略可作为程序设计类课程学生培养的参考。当然，培养出色的程序设计人才是一项长期且艰苦的任务，作为教练，不仅需要制定完备的训练计划和竞赛策略，还承担着“学生导师”的角色，只有深入了解队员的学习生活状况，去帮助他们解决所面临的各种困难，才能培养他们对程序设计的“感情”，使得他们体会到编程的乐趣并“爱上”编程，从而最终成为优秀的编程人才，正所谓“知之者不如好之者，好之者不如乐之者”。

参考文献：

[1]姚翠莉，刘一玮，金博.ACM/ICPC竞赛人才培养模式的研究与实践[J].内蒙古师范大学学报：教育科学版，2012，25（3）：141-144.

[2]俞勇.ACM国际大学生程序设计竞赛知识与入门[M].北京：清华大学出版社，2012：7.

[3]王晓东.计算机算法分析与设计[M].北京：电子工业出版社，2011：5.

[4]夏鸿斌.竞赛教育与信息技术创新人才培养模式探讨[J].软件导刊，2009，8（10）：182-183.

[5]Andrew T， Chris H.Programming contest strategy[J].Computers&Education，2008（50）：825-830.

（编辑：孙怡铭）endprint