Apollo Connecting the World

Diligence and Intelligence

[zz]有关如何入门ACM

leave a comment »

一些题外话

首先就是我为什么要写这么一篇日志。原因很简单,就是因为前几天有个想起步做 ACM人很诚恳的问我该如何入门。其实就现在而言,我并不是很想和人再去讨论这样的话题,特别是当我发现我有很多的东西要学的时候,我实在是不想花太多的 时间在这种问题上。但是我当年也是纯凭热情搞ACM过来的,实在是不忍心打击一个同样有着满腔热情的起步者。所以干脆就多花点时间,总结一下我的一些观点 和看法,以后再让人问起这个问题的时候,也好不用再重复什么了。

其次,我在这篇文章中并不打算探讨特别细节的问题,比如说如果某些人想从中 得到诸如“该看哪本书入门比较好”或者“动态规划、搜索、图论该怎么学”之类问题的答案,恐怕要让您失望了。我觉得书和方法都是因人而异,对自己最好的方 法需要靠自己去摸索,抄别人是抄不来的。更何况当初我起步的时候也几乎是一个人单干,没什么人推荐好书之类,都是搜到哪本书里有我想看的东西然后就抓过来 看,感觉不行就再换一本。很多众口相传的好书,我第一次看的时候,其实里面绝大部分的内容我已经都学过了,所以这种书籍对初学者的作用,我本人并没有切身 的体会,而且也没有过相关的教学经验,所以不敢随意评价。

再次,本文很多观点仅仅从是个人经历和想法总结出来的,我对教育这方面也并没有什么研究,所以没什么体系化,内容非常山寨,仅供参考。

最后,这可能是一篇非常低端的文章,希望大家不要抱着什么很大的期望,免得到时失望更大。不足之处,还望谅解。

为什么要做ACM?

这个题头可能有些歧义。我这里并不是想要宣传ACM有多好,而是我希望每一个想参加ACM的人先问一问自己这个问题:我为什么要参加ACM?我想从ACM的锻炼中得到什么?

在 我看来,这个问题的最好的答案是“因为做ACM很爽”。当你埋头苦读你千辛万苦搜集到的各种资料,终于学会了某算法并用它A了一道连XX大牛都没有做出来 的题时,你觉得很爽;当你埋头苦思数日,突然灵光一现想到解法,一下AC,多日积郁一扫而空,你觉得很爽;当你看完一道题之后,行云流水般的在键盘上敲着 代码,一遍通过sample并AC,你觉得很爽,就行了。

或许有人会问,搞ACM能找到好工作吗?是可以。但我觉得如果你真的想找到好工 作,你应该多去外面实习,多做几个项目积累经验,而不是来搞什么ACM。搞ACM能对学术有帮助么?确实有。但是如果你真的想做学术,你应该早点进个实验 室,或者争取去MSRA实习,或者自己多研究一些前沿的学术论文,而不是来搞什么ACM。搞ACM对保研加分有帮助么?是有。但是你不觉得数学建模什么的 会比ACM更有帮助么?

当然我要承认的是,大多数ACMer除了爽之外,确实收获了很多其他的东西。可是如果你觉得除了“学算法、 coding、A题的感觉很爽”或者说“我想晋级Final”之外,更期待某些其它的结果,那说明你真正应该搞的不是ACM。如果有一天,你并没有因为搞 过ACM而拿到一份很优秀的offer,或者申请时发现你拿的那些ACM奖完全没有任何作用等等,你确信那时的自己仍然不会后悔参加ACM,我认为这才是 真正适合去做ACM的心态。

找到“组织”

这 里的所谓“组织”,是指和你水平相近(最起码讨论的问题,层次不要差太多),并且愿意经常和你交流的人,并不一定必须是一个团体。“组织”是相当重要的, 相互交流是快速进步的一个重要因素,这个不仅限于初学者。当年我集训队在役的那段时光就是我进步最快的时候,因为我有两个很强的队友fishcanfly 和mostleg,与他们两个的交流让我获益良多,远比之前一个人单干的提高要有效率。

就现在ACM的发展状况来看,想找到个组织应该不是 很难的事情。能有在你身边的人一起来做是最好的,像HIT的“ACM俱乐部”就是非常不错的组织,很多学校的ACM队也应该会有类似在集训队之外的“编外 组织”一类,应该多去打听打听。如果实在不行,网上有很多的bbs,QQ群,甚至你在renren上多留意,都能找到很多的ACMer,交流应该不会成为 一个主要的障碍。

如果实在是找不到组织,那就只能自己痛苦一点了,这点我也没有什么很好的办法。不过这也并不代表就没有希望了,我当年起步 时HIT的状况也差不多,我认识的很多大牛也都是从这样的环境起来的。乐观的来讲,这种艰苦的条件是很能磨练人的,出了什么问题都必须靠自己。对有热情有 毅力的人来说,是一个挖掘自己潜力的机会,并不见得是坏事。

要有毅力

这里所说的毅力并不是指熬过肉体上的痛苦,比如说那个广为流传的“弱校ACM奋斗史”中写的,在基地打地铺,每天泡面+熬夜一类。当然我对这种精神是相当钦佩的,只是这些困难其实不算是什么大问题,因为只要精神不累的话,肉体上的疲累并不像想象中的那么可怕。

我 觉得ACM很耗精力倒是真的。比如说你可能越学越发现要学的东西还有很多,似乎无穷无尽;或者你发现你周围的人都进步神速,可是你自己却还在龟速前进;又 或者你在参加比赛时很多题都不会做,看完解题报告后发现竟然如此简单,学会之后以为自己可以了,可是下次再比赛又有一大堆不会的题(我07年初做TC时就 是如此)。大多数人总要遇到一个长期不断被虐的过程,很多时候精神上会很痛苦,会冒出到底还要不要继续做下去,做这些都是为了什么之类的问题。实际上我 05, 06, 07这三年每年都遇到过这样的问题,现在看来,我很庆幸我坚持下来了。

事实上,我相信凡是真正喜欢ACM的人,是不会被这种困难击败的,只是应有一些心理准备,同时有一些决心才好。

不要迷信“神书”光环

其 实这很简单。很多神书确实神,可是不一定适合初学者。比如广为流传的,刘汝佳当年写的那本黑书“算法艺术与信息学竞赛”,也只是针对许久之前OI的那种 “信息流通性不强”的情况搞出的一个大杂烩,我当年刚开始搞ACM的时候就买了一本,结果搁了N年也没看完。其实就今天的眼光来看,这书应该基本不符合时 代了,要不然刘汝佳也不用大花心力再去编写一套新的。还有众口相传的CLRS,虽然我不是拿它来入门,但是我隐约觉得,如果有个明白人在你身边指点的话, 这书倒是还不错;如果是初学者自学,不见得会有很好的效果。

至于到底该选择哪些资料来入门?我只能说因人而异。记得当时我大部分知识的入门 方法就是在网上寻找各种资料,其实我觉得网上有很多资料讲得非常通俗易懂,对于一个身旁无人指点的人来说,效果不见得会比那些神书要差。当然在这种“山寨 式”的学过这些东西之后,还应该找几本好书来仔细看一看,由于这时很多基础问题不再是障碍,才能更加容易把握住这些好书中精华的部分。

多做难题

如果你去问那些牛人“这道题你是怎么想到要用XXX方法的”,我估计大部分人都说不出个所以然来。其实很多情况下都是纯凭直觉考虑到的数个思维方向,这种直觉是需要大量的练习来得到的,没有那么多“为什么能想到”,类似于Roba口中的“条件反射题”一样。所以要多做题。

不 过这里的“多”不是指数量多,而是质量多。所谓的难题也并不是指要做那种难到天顶的题,而是适合自己的难题。如果一道题能够让你经过数个小时甚至一天的冥 思苦想,最后终于AC,我认为这样的题才是最好的。当然这是你要有一些相关基础的前提下才能做的,不要一上来就走极端。

事实上,我认为只有对思维进行这种接近极限的运转,才能最大限度的加深对相关知识的理解能力,在众多的idea中一一排除,最后找到正确的那条路,也能让你每个方法的本质有一些更深的理解。而且这种方法过题,得到的成就感显然不是刷十几个水题能比得了的。

至 于这样的题该如何去找,看某些有难度分级的题单是一个不错的方法,TC, CF这种题目分级相当明确的OJ也是不错的选择,或者干脆去看一道题的AC数和AC率。这个可能需要做很久才能把握住哪些题适合自己,但是当有了一些基础 之后,至少要时刻提醒自己,多做有质量的题,少做水题。

不要做太多比赛

因为绝大多数的比赛都不是面向初学者的,所以我觉得初学者做比赛有害无益。就算是做比赛,也应该明白做比赛的目的是要警告自己还相当弱,激励以后继续努力,而不是要检验这段时间的学习成果一类。

由 于刚入门的人知识方面还有相当多的空白,想提高是一件非常容易的事情,有大量的资源可供使用,自己线下练习完全足够,我看不出比赛会有什么特殊的神奇效 果。在我看来,比赛主要锻炼和提高的是自己知识和技巧的运用能力,或者你可以看成是“招式”。比如我07年做了一年的TC之后总结了一下,发现我的知识水 平似乎没有显著的提高,倒是思维的活跃度、临场发挥能力有了显著的提升,对实际上没有超出自己知识水平的问题,AC率显著上升。但是想达到这个效果,首先 要有足够的根底,然后才是去考虑该如何高效的运用你的内功。只靠比赛是没办法无中生有的。而且比赛连续失利很容易打击一个人的热情,这对初学者来说是很致 命的。所以初学者对一般的比赛,建议还是少碰为妙。

附:我心中合格的队伍应该具有的素质

如果你要问:什么样的队伍是优秀的队伍?当然,这个答案非常之简单,三个全能型大神组成的队伍就够了。比如2011年IPSC的Petr + ACRush + tourist,你觉得这样的队伍还需要什么别的吗?

不过这个回答显然没有意义,这是任何队伍所能达到的能力上界。所以我试图从草根的角度出发,描述一下我心中一个“正常”的好队伍(我默认上面的那种队伍是不正常的)应该包含什么样的素质。当然并不是指下面这几条都要满足,而是这几条是应该关注的比较重要的方面。

  1. 三 人在ACM涉及到的各个大类都有很好的基础。或者说,如果在比赛中遇到任何一类问题,且难度定位为“简单”或者“中等偏低”,三人应该都可以独立解决。我 认为作为一个优秀的队伍,三个发展全面的队员是必不可少的。虽然不一定在各个方面都有解决难题的能力,但是基础绝对不能差。
  2. 每个方向至少有2人可以对难题进行讨论。如果一个方向只有一个人懂的话,可能这个人会有一些盲点,如果卡题了,也没有人能够与之讨论。每个方向有两个人深入的话,基本可以保证对绝大部分的情况都可以应付。
  3. 有一名知识面广阔的队员。这样的人比较适合掌控全局,可以对绝大多数问题的难度有准确的预估。
  4. 有一名编码能力稳定的队员。三人全都抽风的队伍波动太大,作为一个优秀的队伍,最起码要保持一定程度的稳定,至少应该有一名队员要有稳定输出的能力。
  5. 有 一名能够“混”的队员。这里的混到底是什么标准不太好解释,从境界上比较类似于那句广为流传的名言“这道题我不会做,但是AC还是没有问题的”。或者换句 话说,一个队伍应该有一个人有能力在关键时刻出“奇兵”,虽然并不一定要求有很高的成功率(否则就是神队了),但是最起码在最后关头不至于毫无翻盘之力。

想一想,我06年在役的队伍似乎在这五条上做得都还不错,唯一的缺点是三人都还缺少历练。也不知道是不是因为我对我们队的配合相当满意,所以影响了我对“好队伍”标准的设定。总之,我认为上面那几条是非常值得注意的几个方面,或者说在组队练习中应该注意的方向。

后话

其实上面这些东西可能只是我想说的一半左右,本来还想写一些其他的条目,只是确实有些累了。要不是在renren上发过一个状态让外界给点压力,我肯定就真的要半途而废了。说到底,我还是对科普这种活动没什么兴趣的。

当 初做ACM的理由很简单,我很喜欢那种经过多日苦思之后灵光一现,水到渠成的感觉;在看到那种将问题不断抽象与扩展后,一个普适的框架竟也蕴含着如此神奇 的定理,也能用那种神妙非常的方法去解决的时候,我会感到无比的兴奋。对那些陶醉于数学与算法,同时对国内本科教育极度不满的人来说,ACM是一个很好的 途径,让他们能够自食其力,在自己喜爱的事物上尽情发挥自己的天分。

我怀念当初做ACM的日子,怀念与队友共同奋斗的时光,是因为那时的 我,就像是牛顿那句名言中在海边玩耍的孩子一样,每天都能为自己捡到漂亮的贝壳而感到兴奋。可能这也是我近几年为什么越来越不愿再去做比赛的原因。当你不 再满足于ACM给你带来的欢乐时,不妨跳出这个圈子,去外面看看。外面的世界很精彩,ACM只是一个开始,而绝不应该只是终点。

我祝愿所有ACM初学者都能享受到ACM的魅力,也希望每一个初学者能通过ACM,找到属于自己的广阔天地。嗯。应该也没什么想要再说了,就这样了。

from: http://blog.renren.com/blog/60525895/852730269

Advertisements

Written by apollozhao

2012/06/15 at 04:00

Posted in Computer Science, Study

Tagged with , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: