Acumon 的长春比赛报告

行程

• 11月1日 下午~11月3日早上　在火车上度过比较无聊的36 小时
• 11月4日 　试机
• 11 月 5 日 　比赛
• 11 月 6 日 　在长春游玩，但长春实在没什么好玩
• 11 月 6 日 晚 ~11月8日上午　在火车上度过比较无聊的36 小时

比赛

　　比赛一开始，我开屏幕调配置。发现试机时的配置全部被保留。大喜，遂去看题。我看 ABC ，基宏看 DEF ，德健看 GHI 。按照之前的作战布署，此时我们首要的目标是找出最水的题并予以消灭。我很快地看完 A ，发现是一条计算几何题，应该不是水题，便先放在一旁，转而看 B 。 B 题大意是给你一个数 n ，要你找出 k 个数 a₁~a_k ，使得所有 1~n 之间的自然数都可以用 a_i, a_j-a_i, a_j+a_k-a_i 三种方式表示出来，并使得 k 最小。乍看之后像是一条数论构造题，便交给基宏想。此时德健正在看 F 和 H ，前者是一条图论题，后者是一条数据结构题，都不是传说中的最水的题，而且属于德健擅长的类型，我便留给他继续想，继续扫其它题，也帮助基宏一齐想 B ，此时基宏先后找到一些构造的方案，但没能证明它们，而 judge 的返回也说明它们并不正确。

　　比赛一小时后，开始有零星的队过 A ，大多数队还是 0 题。于是拉德健一起讨论 A 。 A 题题意是给出 20 个平面上的点，要求你选取其中一些点，连成一个多边形，使得式子周长平方除以面积取得最小值。马上证得最优的多边形是简单多边形，并且是一个凸包，考虑到点数较少，便想枚举所有凸包，但直接枚举复杂度太高，又无法找到一种遍历凸包的算法。稍后，我们发现一种遍历所有简单多边形的算法，复杂度为 n 2ⁿ ， 10s 的限时绝对能过，便交给德健敲，在经历了几次小 bug 带来的 TLE 后，我们终于迎来了第一个 yes 。此时暂时排名十几，很多队过了的 E 题我们还未过，形势看来不错。二队和六队还未过题。为他们祈祷了一下，继续做题。

　　E 题又是一道数论题：给出一个复数，判断是否高斯素数。我便和基宏一起想 E ，并写了一个暴力枚举的程序来把小范围的高斯素数打印出来找规律，然后我去想 D ， D 题目较长，但其实是一个很容易想到的一个 DP 。看完题后不久便想到了算法。但觉得有点繁琐，而且复杂度好像有些高而且不容易算出准确的复杂度，便等到德健过 A 后再交给他敲。另外 E 题我们在《初等数论》上也找到一些结论，可惜我们看不懂证明。后来我写了一个 n² 的水的方法，却水了几次都没有水过。

　　这时评委看到 A 题过的人太少，便做了件最令人匪夷所思的事：对 A 题连续多次 rejudge ，最终把时限改为用最强大的布鲁特福斯算法都可以过的题，一下子哗啦啦地过倒一大片，我们一个小时的努力换来的的优势顿时化为乌有。

　　不幸中的万幸是，当我用了各种预处理和水的方法都过不了 E 而打算放弃之时，基宏很神奇地修改了其中的一个参数，改大了枚举量，就把 E 过掉了。

　　这时德健已经敲了一部分 D 题，但似乎遇到一些困难，却又无法说出来。之后他便去想 F ，然后决定先水一下 F 。这是一个有关最短路的问题，很不幸地我们选择了使用 Floyd 来求最短路，结果无论怎样改都没法水掉道这题（后来六队用对所有点求 Dijikstra 的方式过掉了这题，实在太神奇，膜拜orz~）。在比赛结束前 40 分钟左右，我们终于放弃 F 来继续做 D ，由于此前我已算出准确的复杂度是 O(500*270*12*case 数 ) 左右，所以那时我觉得把 D 过掉的希望还是很大的。这时德健终于说出了他遇到的困难，原来他把我的算法和他之前的一些想法搞混了，结果我们花了很大力气才取得了一致。最后的时间是在我和德健一齐敲 D 题、调 D 题中度过的，可惜最后都没调过。

教训

1、  不要以为 g++ 一定会对简单的 inline 函数进行展开。这次比赛的 g++ 对我们测试的所有的简单 inline 函数都不展开。

2、  不要以为题目的标准解法不用打表。本次比赛花了我们很多时间的 B 题的标准解法就是花几个小时去暴力打表。

3、  作为队长，我应该更清楚队员的状态，并且更灵活地调整策略。今次比赛德健明显状态不佳，我应该在更早的时候意识到这个问题。

4、  数论和组合数学是我们队的弱项，这次我们的数论题过得很险，相信随后的成都之战会更加艰苦。必须在接下来的休整时间里尽力恶补一下。

5、  我们队的交流还是做得不够。其实那条花了德健很多时间的 H 题，正是我擅长的线段树题目，而事后也证实那道题真的很容易想出来，但我却因为各种原因没有认真去想。

花絮

1、  在去长春的火车上，大家都在努力看书和论文，还讨论一些以前的题目，其间我发现某题可以用 O(n(nlogn)^1/2 ) 的复杂度过。这是我想过的题中“最复杂”的一个复杂度。

2、  去长春的路上大家都没有打太多牌，怕伤 RP 。很不幸地我连胜了几局，赶紧收手去睡觉。回广州的路上终于可以放手打牌了，大败而归。

3、  由于是第一次在深秋时节跑到北方去（假如前几天飞去北京面微软不算的话，但显然长春要比北京冷多了）所以大家都准备了很多御寒衣物。去到后发现其实也没有想像中那么冷，我的围巾和最厚的绵袄都没有用过。

4、  王磊在火车上开玩笑地说他在实验室研究“布鲁特福斯”（ brute force ）算法。我们的德健更号称“系数之王”。很不幸地，这次我们遇上了更加暴力的评委，方知“强中还有强中手”。

5、  在去长春火车上的第一晚，我接连推掉了百度、网易和腾讯的面试，当时感觉心痛无比。不过很幸运地，最终我还是赶在百度团队飞回北京前获得了面试的机会，并很顺利地拿到了 offer 。 ^_^

6、  比完赛后二队和郭老师随即飞回了广州，剩下六个大男人在长春逛沃尔玛，囧。

7、比赛服装的size除了印的码数不同外几乎没有什么差别，导致我们的基宏同学选了件XXL，而肥东师兄却选了件M。

发现

1、  东北有很多西南菜，尤其是云南过桥米线。

2、  在北方千万不要乱点“清淡”的菜，它可能辣得令你无法下咽。一个较好的做法是叫师傅“绝对不放辣椒”，但这时师傅很可能会跟你说那道菜他不会做了。

3、  坐火车千万不要坐车厢两边，除非你不介意车上那帮烟鬼们日夜不停地轮番轰炸。

4、  一个城市的空气和饮用水质量真的很重要的，为了这两个原因我打死都不会到长春去生活。

5、  长春的轻轨很慢，而且车站很密，一两分钟就停一次站，使我们怀疑步行是否会比坐轻轨更快。

6、  原来在手机 QQ 上是看不到对我可见的密友的，由于大家都习惯隐身，结果我经常觉得 Q 上一片冷清。

鸣谢

• 谢谢郭 老师给了我代表中山大学到长春比赛的难得的机会。
• 谢谢队友德健和基宏给了我这个菜鸟队长许多支持和帮助。和你们一起并肩奋斗是我毕生难忘的一段经历。
• 谢谢嘉慧借给我手机，使我没有错过任何一个重要的面试电话，并且在旅途中可以一直用 QQ跟大家 聊天。我那只肥猪仔现在经常“智能悭电”了。
• 谢谢在这次旅程中帮助过我、关心过我的所有人，谢谢你们。