发现有半年没有写博客了……愧对组织……忙都是借口……
今年的Google Code Jam前几天刚结束，神一般的存在Gennady Korotkevich（tourist）不负众望以巨大优势夺冠，拿下Code Jam三冠王。这次Code Jam决赛题目难度比起往年偏简单（tourist差一道Large AK），并且压轴题（Radioactive Islands）出的莫名其妙，是一道很明显的变分+数值计算，推导功底扎实的选手或许可以直接算出解析解。这种题出在算法竞赛而不是物理竞赛，让人觉得有些呵呵。
黑完了，开始捧。虽说Code Jam有些瑕疵，但比起市面上别的比赛，诸如Topcoder，CodeForces，Facebook Hacker Cup等等，还是不知道高到哪里去了。这年头盛行坑人和抖机灵，大量不负责的坑爹题，挖坑题，抖机灵题和特别人为的题充斥着各种比赛，毕竟算法竞赛是非常小众的比赛，而且出题人投入了大量精力，也只有一点点的经济上的回报，跟刚结束的，总奖金高达20M的TI是完全不能比的。Code Jam的冠军奖金只有15000美元。以前看过一个topcoder上的讨论，有人问：比起成为百万富翁，达成什么成就会让你更爽？当时还是算法竞赛届的（或者一直是）渣渣的Zuckerberg也参与了讨论。大家众口一词：成为red coder（大概是活跃用户中的世界前200左右）。蛮喜欢一句话：做事做到8成或许是出于利益的驱动，但做事做到极致，绝对是因为真爱。作为酱油选手+懒癌患者，对这些大神只有膜拜的份。T_T
闲聊到此为止。开始写点干货。今天我想跟大家分享的一道题是今年Code Jam决赛的第三题：Gallery of Pillars。题意大致是：在\(N\times N\)的棋盘上，摆放柱子。每个格子的规格是\(1\times1\)的正方形。柱子的中心和格子的中心重合。柱子有非零的半径。观察者站在最左下角的格子（该格子没有摆放柱子，别的格子全都有柱子）。试问，观察者可以看到多少跟柱子？因为有些柱子会被前面的柱子阻挡，『看到』的要求是：柱子有一段非零的区间可以被观察者看到。具体题目可以在Code Jam的官方网站看到，并有配图，有助于理解。大数据规模：\(N\leq10^9\)。
乍看一眼，这题是一道非常坑爹的计算几何题。计算几何题的最大难度来源于精度控制，而且这题是计算几何中最坑的输出确定整数的题。一个显而易见的做法是，对于每一个柱子，枚举所有柱子，算出格挡的区间，再合并区间。但合并区间的过程中必然会涉及double的加减法操作，特别是可以看到的区间特别小的时候，非常有可能会因为精度问题，导致答案错误。如果这题规模只有小规模数据所提供的300，那这题非常有可能就是计算几何题，几乎所有算法竞赛选手，包括很多大神，都对计算几何题深恶痛绝。
Code Jam除了那么几次出非常坑的题之外，题目质量还是相当有保障的。而且这题规模高达10^9，暴力枚举显然无法求解。我们先考虑极限情况。当半径无限接近于0的时候，可以发现，所有\(\text{gcd}(x,y)\neq1\)的柱子都会被阻挡，观察者只能看到\(\text{gcd}(x,y)=1\)的柱子。gcd表示最大公约数。而计算\(x,y\lt N, \text{gcd}(x,y)=1\)的pair的个数，可以通过容斥原理来计算。
另\(F(n)\)等于满足\(x,y\lt n, \text{gcd}(x,y)\)的pair的个数。我们就可以得到如下式子（具体请自行思考）： \(F(n)=(n-1)(n-1)-F(n/2)-F(n/3)-F(n/4)-\cdots-F(n/(n-1))\)
半径无限趋近于0的情况可以用上述的方法来处理，那么半径不等于0的情况该如何处理呢？我们可以考虑一对最大公约数为1的\((x,y)\)。我们从\((0,0)\)连线到\((x,y)\)。我们考虑这条线段『周围』的点与这条线段的距离。我们可以惊讶的发现，\(y\)方向的距离最小值是\(1/x\)。并且在直线上方和直线下方都存在这种点，使得\(y\)方向距离等于\(1/x\)。稍微推导一下就能推出最近的点与线段的距离是：\(1/\sqrt{x^2+y^2}\)。当柱子的半径小于这个值的时候，观察者可以看到柱子\((x,y)\)的中心。
经过进一步化简，这题编程了求解满足如下三个条件的pair的个数：
(1)：最大公约数为1
(2)：\(x,y\lt N\)
(3)：\(x^2+y^2\lt R^2\)，该\(R\)是由柱子的半径计算得到。
跟上面的比起来，多了一层限制，但求解方法不变，还是可以用容斥原理。
首先可以暴力算出满足条件2，3的pair的个数。
pair总数=最大公约数为1的个数+最大公约数为2的个数+最大公约数为3的个数+…
而最大公约数为\(K\)的个数等于满足如下三个条件的pair的个数：
(1)：最大公约数为1
(2)：\(x,y\lt N/K\)
(3)：\(x^2+y^2\lt (R/K)^2\)。
我们可以记忆化对应所有\(K\)的pair的值，这题并不需要额外的优化，就可以在规定时间内计算完。
表达能力所限，写得晦涩难懂……不过相信智商爆表的大家可以看懂……
严肃话题讲完，再吐吐槽。今年成功忽悠了ywy也参加了Code Jam，并且在一步步拖lzb往算法竞赛的深渊越走越远。自从开始工作之后，每天只有非常有限的时间可以做题。工作日一天基本最多只能做一道难度适中的题目，周末偶尔可以做两三道，而且水平在某种程度上到达了瓶颈，这道看着不难的题，也是想了好几天才想出来……哎……智商的铁壁无法逾越……并且在工作了一年之后，惊奇的发现在比赛中我会试图写注释，停下来思考函数名和变量名是否合理。还有就是就算不难的题，也会停下来，像造房子那样『规划』一下代码的结构。代码的正确率提高了一些，但手速显著的下降了……每个人都有自己的代码风格，有的人喜欢边写边想，有的人喜欢想好了再写，有的人在写的过程中想好，代码一气呵成（tourist）……