标签： USACO

前几天，秋叶拓哉(iwi)、岩田阳一(wata)和北川宜稔(kita_masa)所著，我(watashi)、庄俊元(navi)和李津羽(itsuhane)翻译的《挑战程序设计竞赛》，终于通过人民邮电出版社正式出版了。可喜可贺，可喜可贺。有关该书的简介，目录、试读和购买链接请通过传送门访问。这里我主要想说一下自己为什么要翻译和推荐本书，还有对程序设计竞赛学习资料的一些看法。也附带一些对译者序和第1章的补充说明。

在译者序中我也略谈到了自己翻译此书的动机。和很多读者一样，最开始当然是奔着作者的名头去的，三位作者不但是国际知名的选手，而且TopCoder的最高rating加起来都破9k了。顶尖实力的作者往往可以站在更高的高度指点江山，也就更可能写出一本好书。随后就是读到书中的内容了，书中的绝大多数东西，我大概都在过去四五年时间的摸爬滚打中，逐步通过各种书籍、网络、道听途说、解题经验和总结体会掌握了。不过还是有一些耳目一新的内容，其中有一两个问题还是通过邮件得到了原作者的解答，涨了姿势。但仍有一种相见恨晚的感觉，假如自己早两年读到此书，想必能少费不少劲。从我个人的经历和对周围同学的了解来看，这是一本非常值得引进和推荐的书。

当然，在此之前国内已经出版有不少算法竞赛相关的书籍了，很多人想必希望知道这本书有什么特别之处。算法竞赛相关的书籍大致有两类，一类是算法和数学类的书籍，比如各种数据结构教材、离散数学教材、《算法导论》、《具体数学》等，一类是专门针对算法竞赛的书籍，其中的代表就是刘汝佳所著的几本书，而《算法艺术与信息学竞赛》（黑书）又是其中的代表。作者之一的iwi在MSRA实习期间也得知了黑书的大名。

首先，个人觉得这些书籍大致可以分为两类：教科书和工具书。诸如《数据结构与算法分析》(DSAA)之类的书可以作为教科书的代表，而诸如《计算机程序设计艺术》(大名鼎鼎的TAOCP)则毫无疑问是工具书的代表。大致地说，前者简单易懂，适于学习，后者高深全面，适于参考。二者并没有明显的分界线，很多时候全凭主观，因人而异。比如说，看懂了，这就是教科书，看懂目录了，这就是工具书。当然，和数学沾边越多的书，总是越难啃的，所以就难度而言，这类书籍和编程语言类书籍自然是没有可比性。

许多书都作为程序设计竞赛的学习资料被反复推荐，但事实上，我们大概可以仿照《最常被程序员们谎称读过的计算机书籍》写一篇《最常被ACMer们谎称读过的书籍》的吐槽文。里头有一句话很重要，所以我再抄一遍：“如果你自己没有读过这些计算机书籍，请不要推荐给别人”。当然，像《算法导论》这样的书个人觉得还是值得一读的，多数的章节并不难，可以当作教科书，后面的一些内容可以作为工具书需要时再参考，里面很多东西讲的很细，容易做到真正的理解吸收，比如从自动机引出KMP等等。而TAOCP则无疑是最常躺枪的装逼神器。有一天，我在同学的桌上看到一本TAOCP第一卷，打开一看很黄很暴力，我赶紧就把它盖上了。TAOCP很厉害，看exponentiation by squaring能引用到它，看permanent也能引用到它，连看数え上げお姉さん都能引用到它。读完TAOCP那必须能变得超厉害了，可那得是能读完啊，读不完说啥都白搭。所以推荐学习资料不能光看书好不好，还得看对目标人群合不合适。而一本好的教科书，不应该是尽可能体现作者有多牛，而是要能够尽可能简单地帮助读者变得更牛。如果看完了，懂的还是懂，不懂的还是不懂，那是没有意义的。

按照这个分类标准，个人觉得《挑战程序设计竞赛》是一本很好的教科书。它非常的适合作为有志参加程序设计竞赛的同学自学，或是正在学习数据结构与算法分析的读者作为练习和拓展的参考书。该书将不同的主题按难度分成了三部分，循序渐进。作为教科书，其一个明显的特点是，几乎没有外链，把每个的主题都讲得很清楚，便于读者理解。多数题目附有核心代码，代码风格也不错，而且讲解的时候会附带一些思路的说明和方法技巧的总结。它在正文中详细完整的介绍了在程序设计竞赛中最重要的知识和思想，全书涵盖了在绝大多数题目中所会用到的知识和思想。而对于拓展内容则以补充说明或是附录的形式给出，并未多做介绍。这样的好处是该书很连贯，结合练习容易完整掌握，并突出了对大多数人而言更为重要，应该多花力气的地方。

在此举几个例子。书中介绍一般图匹配的时候并没有介绍经典的带花树实现，而是介绍了利用Tutte矩阵求匹配数的随机算法。因为要在书中真正把带花树的实现给读者讲清楚很困难，而对Edmonds算法的介绍资料也很多。在介绍后缀数组的时候，用的也不是线性算法，因为后缀数组最重要的是理解其性质和应用，而求后缀数组往往是模板的工作。在介绍字符串上的动态规划算法的时候，没有介绍KMP算法和Aho-Corasick算法，而是用暴力的方法求出了二者所对应的状态和转移，事实上这反而更有助于真正理解KMP算法和Aho-Corasick算法。

另一方面，如果你是想要学像弦图、动态树、Dancing Links(DLX)之类的高深玩意的话，这本书对你就几乎没有任何帮助。当然，说到DLX，我不知道为什么国内会曾经有一段时间盛行出DLX的题，题目的规模大得惊人，能AC的原因却是因为数据太水。真正理解DLX的人应该明白，这本质就是一个常数优化的启发式搜索，并不能改变问题本身的困难程度。从某种意义上说，在把基础搞扎实前，还是少折腾这些高深玩意比较靠谱。

相比较而言，刘汝佳的《算法艺术与信息学竞赛》则介于教科书与工具书之间。书中按专题介绍了了相当多的知识，从头到尾许多小节都涉及到非常难的内容，还有一些神题。书中所提及的算法和数据结构要比《挑战程序设计竞赛》多得多，特别是计算几何部分要更为系统详细。书中包含有大量的外链，非常可惜的是OIBH早在多年前就挂掉了。书中对很多问题进行了总结归纳，但不都有详细的讲解介绍，对于身经百战的读者很容易找到共鸣，但对于其他读者而言，恐怕读起来就不那么轻松了，很多地方需要自己钻研，另找资料学习。黑书是可以多读几遍的书。起初可以在短时间内接触大量的算法和技巧，然后通过其他资料学习。遇到某个有印象的问题，或时隔一段时间后，可以再翻开看。慢慢地，就会对书中越来越多东西有共鸣了。

当然，从最初阅读《算法艺术与信息学竞赛》，到去年翻译《挑战程序设计竞赛》，我自身的实力也已经不可同日而语了。所以上面对于两书的评价，当作两个不同的人做出的应该会更为客观一些。

冰冻三尺非一日之寒。虽然书中的内容已经足以让读者的rating冲上2500，但真要达到2500的实力却还离不开充足的训练，通过实践把书中的内容真正化为己有。另一方面，训练的方法也是很重要了，好的方法能够做到事半功倍。正如《挑战程序设计竞赛》最开始所说的：程序设计竞赛是综合了以下两个要素的复合竞赛：

• 设计高效且正确的算法
• 正确地实现

并且，为了设计算法：

• 灵活的想象力
• 算法的基础知识

也是必不可少的。平时训练过程中切莫顾此失彼。

Q&A

Q: 能找作者/译者签名么？

A: 如果我们有机会见面的话，而且你居然还不嫌我的字丑的话，是可以的。由于我和另外两位译者马上就要分处三个不同的城市了，能不能集齐就得看RP了。如果你参加今年的TCO的话，我们到时候还可以去搭讪iwi和wata要签名。

Q: 卖出一本书你能抽成多少？

A: 0. 我们拿的是一笔稿酬。所以如果你买书的目标是给我钱的话，不如直接一点，打开支付宝。我会很开心的。

Q: 为什么黑Knuth？

A: 呃，虽然文中黑的两个东西全是Knuth搞的，但我绝无黑Knuth的意思，恰恰相反，我黑的是那些亵渎Knuth作品的人。比如建议你想要进某社先把TAOCP读个几遍啊，或者把DLX当万金油使的这类人。

Q: 《具体数学》怎么样？

A: 说来这又是Knuth搞的东西？《具体数学》可以算不怎么简单的教科书。里面许多内容还是可以看得津津有味的，但是有些地方就看着有点费劲了，里面那两页求和公式“简单的例子”当初可看死我了。《具体数学》系统地介绍了许多有用的数学工具，当你遇到过几类数学相关的问题，并开始觉得自己不会数数，不会算概率的时候，就很有看一看的必要了。

Q: 更上一层楼的练习方法。

A: 《挑战程序设计竞赛》也有这么一段，这里做一个补充。一是近年来Codeforces得到了很大的发展，其功能丰富，用户群也很大，是一个很好的练习平台。二是SGU也是一个老牌的OJ，其题库比较精简，且质量比较高，不会像其它OJ有刷不完的题，因此比较推荐。学习算法的时候，可以找一些相关的题做，巩固知识。练习的时候，不应该跟着解题报告做题，而是要尽量独立思考，否则“灵活的想象力“恐难有提高。同样的，不要在“神模板”和“神题”上走火入魔，而忽略了“算法的基础知识”。

转自：http://blog.watashi.ws/2382/pccb-etc/