IMG_4320

长春之行——记 2015 ACM-ICPC区域赛 长春站

       

      这次长春区域赛以铜牌收尾,预料之中的结果,也算是给2年的ACM生涯画上了一个句号。第二次参加区域赛,总算没有和去年的上海区域赛一样打铁。今后的精力也会放在开发上了吧,毕竟什么都还没开始学。希望明年有机会可以去区域赛打打酱油~

      这次比赛比较顺利,没有怎么卡题。特别是一开始连过三题,特别爽。可能是因为强队都去南阳CCPC了,竞争压力不是很大。之后想了各种可能,还是认为铜牌已经是一个没有遗憾的结果了。不过觉得可惜的是信息那边一队没来,目测这次是今年最容易拿金的赛区了,比较可惜。他们来的两队都打铁了,目测是没发挥好。

      10.17 报道、热身赛

      早上5点多到的长春,天已经亮了。感觉这边天亮得特别早,毕竟是北方。刚到并没有觉得特别冷,只是觉得凉快。

      2015-10-17 055503

      在附近的KFC解决了早饭,就去东北师范大学了。后来想太早了,就在学校附近转了几圈,然后就去酒店收拾了下行李。

      2015-10-18 160323

      回到学校的时间大概是10点。我们报到的时间已经算比较晚了,有很多学校前一天就已经到了。签了字领了比赛服装。想吐槽下,衣服好像中学的校服=。=

      高大上的体育馆

      2015-10-17 101052

       

      2015-10-17 101236

      热身赛惨不忍睹,直接爆零。

      2015-10-17 131233

      比赛一开始我就看的A题,读完题发现就是凯撒密码,只是偏移量没给出,需要去猜。队友读懂了B题,觉得是水题,就先把A题放下了。听完翻译觉得很简单,就开始写。之后WA了重新读题才发现题读错了=。=加上刚开始比赛还是比较紧张,最后都没有想出正解。热身赛最后十几分钟开始去猜A题。由于判题比较慢,也没猜出来。

      比赛结束后知道A题果然是用来测试判题压力的=。=还是经验太少。

      不过热身赛算是给正式赛攒人品了,所以结束后我们也没觉得有什么压力。之后在酒店把B题想出来了,很简单一个题,只是比赛时SB了=。=

       

       

      10、18 正式赛

      有惊无险,4题顺利拿铜。

      2015-10-18 141421

      比赛一开始我还是看的A题,读完题后和队友讨论了下,没思路,就先放下。这时候看见F题已经有人AC了,于是就去看F题,发现是个很水的题。考虑了下觉得思路没什么问题就开始写了,然而直接WA。觉得写法可能哪有漏洞,就换了种写法还是WA。

      这时候已经有很多队过了F题了,感觉有点压力了。我们果断决定先换一道题。L题也有几个队过了,于是决定看L,题意就是求表面积,于是很快就AC了。这次是一A,瞬间压力就没那么大了。之后小元元看完G题,觉得凸包可解(虽然之后知道我们想复杂了),我们也觉得没啥问题,就直接写了,提交就AC了。在队友写G题的时候,我们也讨论出了F题的漏洞,之后修改了后提交果然AC了。

      在很短的时间内连过三题,我们一下就冲到银牌区了。这时候就放松下来了。接着去看剩下的题中通过队伍最多的J题。看这道题各种别扭,有异或,时限9s。这时候就开始sb了。一开始觉得是二分答案,算了下复杂度可过,就开始写,写到一半才发现并没有单调性。于是又开始重新想。。后面还试了HASH,也被推翻了。这时候后面的队伍已经赶上来了,我们周围的队大多数都过了4题了,我们也掉到了铜牌区,着急起来了。

      在比赛开始后3个多小时的时候,终于想起了以前做过一道类似的关于异或的题,是01字典树,而且也带了模板的,看了下,不就是这道题的正解么,只需要稍微改动下。之后也是因为太着急了。。忘了把next改成Next,第一次提交CE,马上改好后再次提交WA,瞬间就蒙了。觉得思路没问题,于是重新检查代码。。发现少写了一个else。。加上之后觉得没问题了,于是提交,果然AC了。

      虽然4题了,但是只是在铜牌区的排名上升了,并没有进入银牌区,但是也肯定不会掉出铜牌区了。

      这时如果再出一题就可以拿银了,于是我们去看H题。最开始是一点思路都没有,我就想试下分治可不可解,于是就开始写,写完发现答案完全不对。这时想到最开始就该先笔算下,还浪费时间去写代码=。=这时候已经封榜了,更加紧张了。这时候队友想到将N个点连成一棵树不就是把2N-2个度数分给N个点,于是就变成了DP。马上就去用代码实现,写完发现复杂度是 \(O(n^3)\) ,肯定过不了,而且应该是哪里写错了,跑出来的答案比正确答案多1。强行减一后试着提交,果然超时,比较奇怪的是居然是TLE不是WA。感觉思路没问题,但肯定需要优化。

      这时候离比赛结束只有十几分钟了,由于平时没有怎么做过DP的优化,所以这时候完全没有想法了=。=

      比赛结束前几分钟把每道题都交了一遍,算是实现了之前说的每道题都交一遍的想法~

      QQ图片20151022171241

       

      之后便是讲题和颁奖。

      听了题目讲解,知道了H题我们的思路是正确的,只是才想到一半。N个点连成一个树的必要条件是每个点至少有一度,于是先给每个点分配一度。这时候就转换成没有限制条件的把N-2个度数分给N个点,有点像统计上的隔板法。之后还需要转换下角度,把题目转换成现在有若干个物品,恰好把容量为N-2的背包装满的最大价值。

      最后的颁奖完全没有悬念,果然是铜牌。

      ACM长春区域赛就这样结束了。

       

       

      10.19 净月潭

      之前向杨老师申请了多呆一天,所以可以到处去浪了~

      百度了下决定去净月潭。

      因为景区太大,我们租了自行车。里面风景很美,遗憾的是照不出来。

       

      IMG_4284

      IMG_4311

      IMG_4285

      IMG_4316

       

      Categories: 随笔