Google Code Jam 2018 回顾

  • GCJ2018(Google Code Jam 2018)今年突然改了平台,从原来在选手本地机器跑测试再提交结果文件由服务器判别正确性,改成了选手提交代码,跑数据+测试都在平台上完成。整体来说这个变动不算太大,如果说有啥影响的话,只能说以前可以有效利用多核多线程加速,而现在不能用了。现在更像ACM的赛制一些。

  • 今年比较好的是比赛基本都刷在了周六周日不加班的时候,所以,就抽空做了一下。下面说说参与历程吧。


Qualification Round

  • 总的来说不算太难,不过想AK的话,还是得写一些恶心的代码。

A. Saving The Universe Again

没啥好说的,显然优先把最后一个能找到的”CS”改成”SC”即可。因为数据量不大,直接模拟即可。

B. Trouble Sort

排序完成时,一定满足$L[i] <= L[i+2] $。即奇数位置和偶数位置分别是排好序的(别用冒泡排序哦)。
所以,用sort分别对$[L[0],L[2],L[4],….,L[2k]]$与 $[L[1],L[3],L[5],….,L[2k+1]]$排序,然后归并后,遍历一遍即可。
因为,大部分语言都有各自的sort库,所以不算麻烦。

C. Go, Gopher!

一个交互题,选择一个位置,等概率命中周围$3 * 3$内的每一个位置,要让一个矩形区域内每一个格子至少命中一次。因为有1000次机会,但矩形面积只有200这么大,所以只要设计一个不那么坏的方法即可。
策略:矩形的长宽经可能接近,比如$10 * 20$就比$8 * 25$更好。每次测试点尽可能选择周围9个格子未命中比较多的位置进行测试。
这样就能过了,没仔细算过期望是多少。但是简单跑测了1000次基本在400~500次左右完成。

D. Cubic UFO

看起来复杂,其实也算比较简单。大概就是怎么转立方体,使其投影面积恰好和要求的面积相等。
显然,投影是一个凸包,定点一定是立方体8个点之一,所以转好后,把8个定点分别投影,然后求一下凸包面积即可。
小数据只用旋转一个轴即可,大数据需要转两个轴,由于是个凸问题,所以找到最大投影面积的姿态后,可以二分来微调角度。
可惜,最后输出结果时,没注意转置,不小心把XYZ轴按列向量输出了,直接挂了大数据,尴尬。(小数据能过是因为,XYZ列向量构成的矩阵恰好是XYZ行向量构成矩阵的逆,而只转一个轴,逆矩阵也是一个解,所以就过了)

  • 不过Qualification只要很少的分就能晋级,所以无压力晋级啦。

Round 1A

  • Round1的三场晋级赛难度排序,个人认为应该是Round 1B > Round 1A > Round 1C。可能因人而异吧,毕竟每个人脑回路不同。
  • 1A这场的时间,恰好不用加班,:)

A. Waffle Choppers

看完了可能会觉得很复杂,毕竟既要横切也要竖切。
不过很快发现,降一维似乎就很简单(即只横切或只竖切),在进一步发现,在一维的时候,切法几乎是唯一的(如果不考虑一段空格的出现的话)!太唬人了吧 = =
既然一维是唯一的解,那二维岂不是要么没解要么只有唯一解咯?
这样就简单多了,先解要切哪些行,再解要切哪些列,解完后两者组合起来校验即可。

B. Bit Party

二分,看起来没太多要解释的地方。

C. Edgy Baking

假设每个矩形高宽为H和W,不失一般性,假设$H<=W$。那么两个选择,如果不切贡献权重$2H+2W$如果切可以贡献权重$2H+2W+2H$ ~ $2H+2W+2sqrt(H^2+W^2)$。
对于每个矩形可选切与不切,可设计状态f(ith, length)表示前ith个矩形规划完,最小总长是length的条件下其状态可达到的最大长度是f(ith, length)。
剩下的就是标准的背包。
只要存在区间$[length, f(N,length)]$包含P那么就是P,否则$ans=max({f(N,length)})$.

  • 无压力继续晋级。

Round 1B & 1C

  • 虽然没有参与,但是过一下题吧。
  • 1B确实有些恶心啊,感觉真参与了可能做不完,大部分要想很久才能想通。

1B-A. Rounding Error

这个问题比较好玩,给你N和序列$[ci]$,都是正整数。说把正整数N分成若干的正整数ai满足$ai>=ci$,计算$qi = round(ai / N)$(round是四舍五入到整数),目标使$\sum_1^N qi$最大。
这问题相对还是比较好想的,只要构造尽可能多的ai能恰好以”xxx.5″的格式5入就行,因为ai数量是固定的,而每个ai不是4舍就是5入。所以”xxx.0~xxx.499999999..”都是一个坑比级别的,需要尽可能避免出现。而对于5入的部分,“能省则省”,即尽可能接近0.5,而不要超过太多,比如$[0.9,0.9,0.9,0.9,0.9,0.5]$就不如$[0.5,0.5,0.5,0.5,0.5,2.5]$好。
总结发现,每个ai尽可能接近xxx.5就是最优,那么就简单了,目标就是构造尽可能多的xxx.5。
显然可以贪心,按构造成本,优化每个ai。成本计算$cost[i] = ci – floor(ci) < 0.5 ? floor(ci) + 0.5 – ci : ceil(ci) + 0.5 – ci$,把每个ai构造成恰好qi的小数部分超过0.5即可。对于剩余的数全部加给某个ax即可。

1B-B. Mysterious Road Signs

这是个看起来不复杂实际也不太好做(or证明)的问题。
既然是连续子序列,每一项要么满足Di + Ai = M;要么满足Di – Bi = N。
实际上可以理解成一个二分图,Di + Ai是左边节点的编号,Di – Bi是右边节点的编号,每加入一项,实际就加了一条边。
一个合法的子序列满足:构成的二分图最大匹配$MaxMatch<=2$。
证明:二分图最大匹配 等于 最小点覆盖,显然本题中最小点覆盖<=2才合法。
那么直接双指针维护一段最长的合法序列,再用平均$O(1)$的维护方法加入或删除每个节点即可。

1B-C. Transmutation

恩,这个自己就没想通怎么搞。看了答案才似懂非懂。
二分结果,然后用催债的方式依次递归每个节点,其核心思想是每个节点在每轮催债递归不应该被遍历超过M次,超过了说明有不可解的环。
证明:还没想出简单易懂的解释方法, = =!

  • 总之1B实在是有点恶心,还好1A那场就晋级了,不然要凉凉。
  • 与1B截然相反,1C又非常简单了。简单串一下。

1C-A. A Whole New Word

直接构造一个Trie树搜一下就好了。

1C-B. Lollipop Shop

哪怕不会计算期望,也应该能想到方案。
每次统计已发生的结果,选出观测值中概率最小的出售即可。

1C-C. Ant Stack

$O(nlogn)$的最长上升子序列一个思路。


Round 2

  • Round 2,有点尴尬,先水了A,然后看B、C一开始都没啥想法,本来已经绝望,看了D却发现会做,惊呆。
  • 赛后发现,有个A、D大数据的分,实际已经够晋级了。。。(估计很多人没想到D会那么简单,直接卡死在BC上才没晋级的吧,略尴尬啊)
  • 做完D后,心态大变,发现C又会了。做完C,准备水一下B的小数据,结果写了个尴尬的bug,恰好时间不够提交。反正也晋级了,释然。
  • 过一下思路吧。

A. Falling Balls

不难发现最后落在一个格子里的球一定来自连续的格子里。知道这点就不难了。
直接构造答案,即可。

B. Graceful Chainsaw Jugglers

小数据背包,大数据不会–(吐槽,其实后来把小数据的方法贴了一下,莫名过了大数据,到底是gg的OJ,速度真是快 = =)
看官方的报告应该是$O(R^{4/3} * B^{4/3})$的方法,实际大家都是O(R^2 * B^2)的方法过了。
难怪那么多满分,坑!

C. Costume Change

给你$N^2$的矩阵G($N<=100$),每个格子有一个数$g(i,j) \in [ -N,..,-2,-1,1,2,…,N ]$。问你修改最少多少个数,使其每行每列没有相同的数。
这玩意其实是个裸体,没刷过同类题的可能很难想到(没想到gg也沦落到出原题的地步了)
对矩阵G中每种相同的数单独提出来建二分图,做最大匹配。(如当前数规划的数为-1,发现$g(1,3)=-1$那么对二分图中x=1,y=3的两个节点建边)
这个最大匹配数就是这个数最终能留下不冲突的最大可能的个数。(因为对于一种数,一行一列只能出现一个,这和二分图的匹配恰好对偶)
最后对每种数求个和就行,这就是不用改的,剩下的都要改。
那么,都要改的一定能改么?
– 一定能!因为你一行一列总共只有$2N-1$个格子,却有$2N$种不同的数, = =!

D. Gridception

因为最后递归的很深,实际上相对于$R * C$这么小的矩形,需要考虑的有效情况无非就$2^4$种。
对每种构造一个 $2R * 2C$ 的大矩形,直接在里面遍历每个位置,找 $R * C$ 矩形里的最大连通块即可。
我用了 $O(2^4 * R^2 * C^2)$ 的暴力过的。实际答案也是如此。


Round 3

周六,加班回家,发现Round3在22点开始。做了一下,简单做了一下A和C,其他的一时也没想法,白天加班有点累,想想也没戏了就睡了。
早上发现C的大数据代码没交上去,只有之前交的水小数据的题,非常奇怪,不过后来试了一下大数据还是挂了,哎。。。
有点坑,Round3的回顾以后写吧。不开心啊 = =

Round3回顾链接

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.