2022 Google Code Jam Round 2 比赛历程

终于有时间来记录一下队长这场比赛的参赛历程了。

首先呢，code jam是一年一度的谷歌全球编程大赛，因为高质量的题目和众多高手的参与，含金量不亚于ICPC。比赛分为资格赛(qualification)，三轮淘汰赛以及全球总决赛。

资格赛在3月底进行，30个小时之内能做出30分的题目（满分100）即可晋级，允许合作和讨论，队长轻松满分过关。第一轮淘汰赛分成三个sub round，你在任意一场拿到前1500名即可晋级，因为资格赛过关的人数有28111人，晋级率差不多16%，这个是队长第一轮比赛的视频

Code jam round 1A比赛录像

比完了第一轮，就是今天要说的第二轮了，第二轮是从4500名晋级的选手中再选出1000名进入最后一轮淘汰赛，晋级率22%。虽说比第一轮还要高一点，但是选手的水平大大增强了，毕竟能进入第二轮基本都是有两把刷子的，在codeforces起码是蓝名到紫名的水平。队长在去年，就是跪在了round 2，连T-shirt都没拿到。

那么今年这一轮又会怎么样呢。在比赛前两天，我停止了所有的科研，专心刷历年的题目，来培养自己的状态。5月14日上午10点，比赛正式打响。

首先是第一题，最简单的一题，一堆NxN的网格（N为奇数），每个房间都有一个数字，螺旋状排列

你要从左上角出发，然后走K步到右下角，在这K步里，你可以正常走(1->2->3->4....)，也可以选择捷径shortcut，比如如果是5x5格子，你可以从2->17，18->25等等，但是你不能从数字大的房间走到数字小的房间，而且你也不能斜着走，比如1->17是不行的。

问，请你构建一条路径从1-到N*N，要求正好走K步。比如N=5, K=4，你可以选择1->2->17->18->25，然后你只需要打出所有shortcut即可，比如你只需打出2->17,  18->25，一共两个shortcut。大家可以想想怎么做。小数据的范围是N<40，大数据是N<10000。

——————————

这道题一开始我本能想到BFS，然后看到数据范围N<10000，我就觉得BFS肯定内存会炸。那么我们就必须要用一些技巧来凑K步。怎么凑呢。我就开始了观察大法。

既然是走K步，那么K最多是N*N-1，这是没有任何shortcut的情况，如果K小于这个数，那么我们必须要走shortcut来节省步数，每个shortcut都会节省一定步数，加起来要等于N*2-1-K。

然后，我们发现，有些房间是处在角上的，这些角是不能做shortcut的，比如5x5的1，5，9，13，17，19，21，23，25。然后呢，如果数a和b都在两个相邻的角中间，比如2，3，4都在1和5中间，那么他们shortcut，其实节省的步数是一样的。之后我又发现，1,5,9,13,17,19,21,23,25其实分成了八段，每段节省的步数分别为14,12,10,8,6,4,2,0。而且当你从2走到17，节省了17-2-1=14步，你下一个short cut最多节省6步，也就是相差至少为8。

我的策略是要让shortcut尽可能的少，每次shortcut尽可能节省步数要多，典型贪心法构造。经过20多分钟设计，调试，我成功过了第一题的所有数据。然后我一看实时排名，60多名，惊呆了。

然后第二题是两种不同的涂阴影方法，求涂黑格点数量的差值是多少，这道题你需要读三段伪代码，小数据直接implement就可以了，送分题，大数据则需要hard math，各种四舍五入处理让人头疼。我拿下了小数据，看到大数据没思路就转战第三题了。

第三题是一个典型的匹配问题，一群人在足球场上捡糖果，人和糖果的坐标都给出来，每个人都会选自己最近的糖果去捡，如果两个糖果距离相同则你让他捡那个他就捡哪个，你能否通过控制这些人的顺序来让自己的糖果不会被捡走。这题我一眼就看出小数据完全可以用bitmask动态规划来做，20分多钟顺利拿下，大数据就不会了，看题解貌似是什么匈牙利算法，我也完全不会。

之后就是两个选择了，我是做第四题小数据还是做第二题大数据？我这个时候看到第二题过的人越来越多，因为第二题大数据是隐藏的，我不知道大数据多少人过，只知道过至少一个数据的总数。因为第二题大数据分值要比第四题小数据高5分，我决定把剩余75分钟都投进去。

然而，75分钟过去了，我啥都没做出来，第二题过的人越来越多，突破了2000，我越来越绝望，如果第二题有超过1000个人过了大的数据我就死了，不过比赛结束后一揭晓，发现只有200多人过大数据了。我的名次也定格在484名，没想到自己连前500名都能进。

当然了，现在想起来，如果我当时知道第二题没几个人会大数据，我肯定就做第四题了，而第四题第一问我发现我半个小时就能拿下，这样我还能再多拿11分。不过，这是当时的战略失误，怪不得我。其实我在48分钟拿下第二题的小数据就已经确保前1000名了，后面搞得非常紧张，虚惊一场。

不管怎么说，我终究还是过了，突破了去年没能突破的障碍，幸运的拿到了T-shirt。有好多codeforces积分比我高的多的红名大佬都没过。他们没过的原因，跟我一样，第二题围攻了太长时间，没心思做后面，不过我好歹还把第三题小数据顺便做了，所以排名比他们高，但这完全就是他们策略更失误，不是因为他们水平不如我。

接下来，Round 3在6月初进行，这个就是我的告别之战了。1000个人选25个人进世界总决赛，tourist，jiangly大佬都有翻车的可能，至于我这个业余爱好者，是不会有任何希望晋级的。我的任务就是，拿到分数就是胜利，不管几分吧，别被剃光头。不要碰题目的large test set，因为做不了，没这个能力知道吧。到时候我会录像，反正也无法晋级，没什么压力。

马上博士就毕业了，今年这篇prreserach的paper，还有这个code jam的T-shirt也都算是我这两年努力的回报了。