acm中队员的合作策略.html
转自：http://blog.programet.org/2009/12/
最近刚刚开始认真的ACM…于是去网上找了找关于合作方面的内容，找到一篇E文的，不知道作者是谁。我看了看，感觉还不错，准备收藏。但是一想总觉得看E文的水平毕竟欠佳，没有中文一目十行的那种快感。于是我将其简单地翻译了一下，懒得润色了，还是贴了出来，方便大家的阅读与交流。因为翻译上的缺陷在所难免，所以我已经做好了被拍砖的准备TT……原文的txt版点击这里下载。
简介：
自1977以来就有了ACM。这项由资格赛和决赛逐级递进的竞赛为大学生提供了磨砺自己的机会。三个学生要在5小时内用一台电脑解出尽可能多的问题。解出最多问题的队伍就是冠军——解出问题指的是对每个输入都给出了正确的输出。虽然说队员的个人能力很重要，但是如果想要登峰造极，队员们之间还需要有效地配合。我们作为1995年世界决赛的参赛者（我们仨中的两人还参加了1994年的），倒是总结出了不少团队合作的策略。
我们准备在这篇文章里总结我们这么多场比赛的经验，希望这对想参加ACM（或者其他比赛）的你有用。
最基础的东西：练习，练习，练习！！
因为三个人手头只有一台电脑，所以良好的合作是非常必要的。当然，为了让策略更有效，你首先必须尽力提高自己的能力。你不一定要是一个天才，因为勤奋与刻苦也可以让你走得很远。我们认为，一个队伍是否出色取决于下面三点：
1.对经典算法的了解以及找到每一个问题的算法的能力；
2.编码实现算法的能力；
3.队友之间有效的沟通策略。
这篇文章将重点阐述第三点。不过仍然会有一些提高个人能力的建议。
我们分析了以前的比赛题目，发现同类型的题目不断地出现——可以分类为以下五个类型：
1.搜索类题目。这些题目需要对很多的情况进行考察以找出最佳的一种。因为搜索最头疼的是时间限制，所以说你应该多注意算法的时间复杂度。
2.图论问题。这些问题有特殊的可以转化为一个图的性质，所以可以用经典算法来解决。
3.几何问题。主要是形状，线段以及角度的问题。
4.模拟题。这 些题目的算法很容易想到，但是细致的编码则常常需要很长的时间。
5.杂题。
你可以在各种资料里面找到前三类问题的算法，你要做的就是事先编好他们的代码然后带到赛场。这样你就可以避免总是犯下同样的（小）错误，然后集中精力对付问题真正困难的那部分。
练习的另一个目的是高效地编程。这并不意味着你要飞速地敲打键盘然后花上海量时间进行调试。相反，应该把问题想清楚，考虑每一种有可能出现的情况，然后开始编码，要保证你的编码能够将调试的时间减少至最低——通常调试都会用掉大量的宝贵时间。
为了磨合一个队伍，做大量的仿真练习是必要的：5小时，一台机器，三个人以及一个评测系统。
团队合作策略的理论
当你的算法和编码水平到了一个难以进一步提高的境界时，改善你们的合作策略会在你冲顶的助你一臂之力。我们和很多不同的队友使用不同的策略练习比赛很多年了，同时发现很多其他队伍也这样做。从中我们归纳出了一套如何让一个队伍最优化的理论。不过，改良策略不一定是必要的：1995年的世界冠军弗赖堡大学只是一支新手队，1994年的西北欧冠军华沙大学的队员们在赛前2个星期才互相认识。
为什么合作策略这么重要？比赛的时候只有一台电脑，所以大家要共用它。问题要被分成几块。为什么不让全队人共同参与呢？“各有所长”(Specialization)是一个很好的分工合作的依据。如果每一个队员都是解决某一类问题的专家，那么他们自然对这类问题的编码更确定，也有可能实现的动作更迅速。对于其他方面，“各有所长”也是很有用的。比如某一个队员是击打键盘的好手但是对设计算法不是很擅长，而另一个队员是算法专家但是不能很流畅地实现算法——他们合作的成果就是能够流畅解决复杂问题的代码！
另一个分工合作的办法就是让两个人分析所有的问题。两双眼睛看得更清楚，也能更准确地判断一道题目的难度。在早期形成一个“思维坦克”(Think Tank)对找到最合适的题目以及对应的算法非常有帮助。不过，一旦把算法分析透彻了，就只能让一个人进行编码。
经验告诉我们，最有效的编码方式就是一个人完成。这样可以避免相互交流的时候由编程风格的差异造成的混乱——即使你们尽量使用相同的变量名和函数风格，这样的差异仍然是不可避免的。一个人编码能让3*1等于4.
其他的注意事项
因为最后的排名是根据AC的题目数量以及（如果数量相等）运行所有程序花去的时间之和。所以一支队伍应该在5小时里面尽可能地AC，将耗时视为其次的目标。每一次比赛都有队伍在前三个小时内都处在前六名的位置上，但是最后连前十都没有进，相反的过程也经常发生。因此一个长期的策略非常重要：尽量最优化15个人力小时以及5小时的计算机时间，而不要去担心如何最快AC前两题。
为了珍惜宝贵的时间，尽量完成每一个已经动手了的问题。一个已经解决了99%的问题对你们来说没有任何意义。一开始就应该分析清楚题目难易（比如使用“思维坦克”策略）以避免你本就无法完成的题目，或者是防止放过一道伪装得很好的水题。你需要对问题的难度有一个很好的嗅觉，这是选出5小时内你能完成的问题的唯一方法。
因为永远不可能得到最准确的信息，所以你必须冒险。如果你采取了高风险的策略——准备着手解决大量的问题，可能最后你的排名位于后半区，同时电脑上有一堆解决了90%的题目——或者你会笑到最后。反过来，选择比较平稳的策略——选择少量问题，一般就会让你在前4个半小时内完美地AC他们，但是剩下的时间对于一个新问题来说又太短了，这样就浪费了10%的比赛时间。
时间规划应该成为你的策略的一部分。如果你准备对一个难题问题下手，那么请立刻动手，否则你难以完成它。虽然这听起来没什么，但是有很多队伍刚开始选择了小问题，迅速切掉，然后比赛结束时一共也就AC了三题——因为他们没有解决难题。我们认为最后的一个半小时内应该最优先考虑调试而不是新题。如果你在比赛的晚期又开始了一题，那么比赛的最后时刻（最后一个半小时）将成为一个瓶颈。
显然，对最后时刻的安排是决定性的。虽然绝大部分的程序都比较小（不超过100行），最后时刻仍然是一个瓶颈：三个人都想好好利用电脑来做自己的程序。怎么样解决这个问题？首先要记住：坐在电脑前永远只能打字，而不能思考。将你的程序写在纸上，一直到最后一个分号。这样一来你通常都会有一个更好的全局观念，同时你可以仔细考虑每一种特殊情况而不必担心旁边有人虎视眈眈你掌控着的电脑。一旦你写完了整个程序，录入进电脑就不会超过15分钟。虽然你应该避免调试（如果你在纸上写得很认真，那么这是有可能的），但你真正调试的时候应该这样做：从你的程序中收集尽可能多的数据然后和你的代码一起打印出来，然后进行分析。动态跟踪调试是无比罪恶的事情。
一些策略样例：
1.最简单的策略
这条策略对于新手或者是不想沉沦于题海中的人来说非常实用，当然这条策略基本没有什么很好的效果。基本思想就是各做个的题目然后将交流的时间降至最低。每一个人都读一道题，然后挑出一个进行编码。完成一个之后就接着下一个。
这种方法的好处就在于基本上不用练习，程序运行耗时被降到最低——因为最简单的问题最先被解决。但是有几个缺点很明显：因为最早被解决的问题通常都是一样水的题目，那么三个人都会在差不多的时间内完成他的程序，所以在最后，电脑的使用权就会引起冲突。另外，只有最简单的程序被解决因为没有时间剩给难题了。最后可以得出这样的结论：假设你的编程水平不算差，那么你们队就应该能解决三到四题。这会使你的耗时很少，可能进入前十，但是不太可能进入前三。
2.终结者策略
在终结者策略中，只有一位队员T在使用电脑。另外两位则负责分析问题，将算法和代码的关键部分写下，然这时后T应该要完成必要的输入输出部分。当算法完成时，T就开始打字，如果必要还应该简单调试一下。如果bug难以发现那么这题算法的设计者就过来一起调试。
这种方法的好处在于最后时刻不再是瓶颈，同时解决问题的不同过程交给了不同的人。这个方法的一个缺点就是T在打字之外没能发挥任何的作用，只是像一个秘书一样。如果你是唯一一个比较熟悉编程环境的人，那么这可能是一个好方法。你可以一开始在队友思考的时候打出大段大段的基础代码作为热身。是否选择这个方法与你在这支队伍中的地位关系密切。
3.思维坦克
我们自己赛前练习以及在1995年总决赛上使用的策略就是前文提到的“思维坦克”策略（Think Tank,TT——套套？）。我们感觉在早期选择和分析问题是一个决定性的步骤，所以不能只让一个人来完成。队内两名最擅长问题分析的人组成了套套，同时开始读题，同时第三个人就在电脑上面打一些常用的程序段以及所有的测试数据，并且要确定准确无误。15分钟过后，套套简单地讨论了一下问题同时选出最适合第三个人的题目。交流过核心思想之后他们就可以开始工作了。然后套套将所有的问题都彻底讨论一遍，并将主要思想写下来。我们发现两个人讨论一道难题经常会出现富有创造性的方法。估计一个小时后，套套对整个问题都有了了解，同时找到了所有的算法。接下来的关键就是你想解决多少问题。最短或者最容易的问题通常都交给第三个人，然后套套就瓜分了剩下的问题。
最后时刻只是用来将纸上的代码誊到电脑上，或者是解决一个有bug的程序。如果一个程序没有AC却又找不到错误，那么就将其放到一边直至最后一个小时。原则上最后一个半小时都不应该再输入新代码了。此时整个队伍应该简短地讨论一下当下情况，然后对剩下的代码制定一个调试方案。
这个策略的优点就在于：基本上每一题都可以被解决，因为套套在早期就开始考虑难题。一个明显的缺点就是你们的开头会比较落后，同时耗时不一定最少，所以你们要比其他组多AC一题才能获胜。我们觉得对于一个队员水平相对均衡的队伍来说，这套策略能够帮助你们解决尽可能多的问题。