第7届浙江省大学生程序设计竞赛(The 7th Zhejiang Provincial Collegiate Programming Contest, 7th ZPCPC),我+商天皇+dd继续组队,不过队名由校赛时的gensokyo(幻想郷)改成了省赛时的tsukimisakura(月見桜)。《月見桜》其实是东方西瓜theme《砕月》的由のりこ演唱的一首同人Vocal的歌名。

这回还是没什么压力,毕竟没有“任务”在身,不过比赛还是用力投入了,毕竟我们对不是来省赛打酱油的。中午饭后休息时间,先在218把《月見桜》这首歌repeat了十遍。我们队依然把GB的“时光倒流”,浙江大学SRTP成果汇编和圣经带到了赛场,这回还带上了“教练”博麗霊夢,quark的“明明白白用Word”和kid的“C语言调试技术”是左右护法。(<-啊,求真相啊求真相,天师?can哥?谁有真相给我一份啊)

(感谢天师提供的王道)

(感谢天师提供的王道)

比赛开始,我搞定vimrc,然后换dd,dd上来就把A(5)B(7)L(9)秒杀掉了,而我和天皇同时把题看得差不多了,讲完题,觉得没有那么秒的了,于是我上去敲E。E我没有暴力枚举验证,用的是一个复杂高点的方法,所以也比较慢,写了一半,dd和天皇讨论出了G是n/2的结果,于是让路,但G居然WA。于是我回去搞E,debug过sample后submit,WA,发现闰年有个off-by-1的bug,改过再交E2y(35)。于是后我也来看G,讨论后我也确认了答案就是n/2没错,而且G当时有一个队过了,最后想到了一种可能——“交错题了”……脑海里隐约想起我在IE提交框好像看到dd交的是一坨我写了一半的E……于是再交一次……G2y(42) @@

5道题,我们爬到了Ranklist的前面。当时我看到D,对其中题意不明,然后让队友帮忙看看,这是个很明智的决定,我要头脑一热占着机器开始写的话,后面搞不好就悲剧了。一看JK都有人AC了,自然成为重点目标,天皇也考虑了H。天皇的H比较快就过sample了但是没AC,于是中间打印,debug了几次。dd对K的结论有印象,于是这题就交给他了,过sample后也WA了。我和天皇讨论了一下J,觉得复杂度没问题,于是我负责这题,在天皇修改H2y(75)后,我迅速敲完J,代码非常短,一次编译过sample,J1y(84)。中间dd和天皇讨论了一下K,具体我就不清楚了,只知道我刚搞定J,dd就上机修改好K2y(89)。我们顺利度过了三人开三题的“艰难时刻”,一看,比赛才过去90min,我们8AC,有两题+的优势了。

当然有点比赛常识的都知道还得继续用力,剩下的题目只有CDFI:D在dd看了题目后基本认定大自然;F显然是必须搞的;C看着操作像线段树,但对维护H-group的值没什么确定的想法;I天皇和dd已经确定了删边的算法,不过有点肉,而关键的判同构,我们都知道可以用hash,不过我也提议用简单易写但比较慢的linyue(或者叫cerror)的方法试一下。

我和天皇思考F后先讨论了一下,写题前讨论一下是很有必要的,磨刀不误砍柴工嘛,天皇指出了0这种xe的情况,然后我们大致讨论了一下普通情况的处理,开始我们的想法麻烦而且是不对的,我写了一半发现点问题,于是继续和天皇讨论。讨论的间隙,dd上去写了一些I的code,主要是把森林转为vector<树>的split代码。我和天皇讨论了F,想到了并不复杂的正确算法,确实,冷静下来认真思考一下,要比在机器上写啊写,不停debug和修改的效率要高很多。我继续写F,F生成答案方面我是’9′-’0′人肉的,大量Copy-Paste,所以代码很长,不过不算复杂。然后用天皇准备好一系列case测试了一下,发现一个长度要增加时会死循环的bug,改过提交,TLE。由于复杂度是很有保证的,所以TLE应该就是代码的问题,一看,发现Copy-Paste+人肉的代码里,’7′的情况有个下标没改对,于是改正一个字节以后再交……F2y(151)

剩下的题就比较自然了,C dd决定用块状链表O(n*sqrt(n))的复杂度来做,算法自然是没有问题,我们觉得时限也是够的,于是开搞。我先写了离散化的部分,剩下的核心代码则交给了dd,dd没有花太多时间就写完了,然后大家一起debug。我离散化的地方忘记把0和n加进去了,于是小改之,过了sample后提交,WA。既然没有TLE,那么就得好好找bug了,天皇决定写个暴力对拍的程序,我帮忙看dd的code,我看完了code,发现代码不复杂,应该没什么问题,但天皇对拍的结果大部分都过不了。我们找了个case以确定C的bug,纠结的看了半天case,最后我发现是由于off-by-1的bug,程序里在n-1的右边还加入了一段,改过之后,对拍没有问题,提交AC,C2y(223)。这个时候比赛还有一个小时,两题加上巨大的罚时优势,基本锁定冠军了。

D是越想越大自然,于是只有搞I了。然后我接着dd的代码写I,主要就是删边并生成两棵树和判断同构的算法,天皇和dd则检查打印的split代码,中间发现点小问题,改了几次。我写好了代码后没有过sample,全是NO,于是加printf输出信息debug,最后确定bug在split上,然后天皇没用多久就指出的bug所在,改过之后通过(误)了sample。还能怎么样,去掉调试信息交呗,程序编译了半天,又跑了很久,看着时间一直涨,打算如果TLE了就换hash判断同构,结果却WA了。WA了是好事,说明现在这个算法够快了;但也是坏事,因为现在的代码比较复杂了,这bug真不知从何找起。今天既然都有过提交错代码的情况了,于是一个玩笑的念头在我脑中想起,“o(∩_∩)o…哈哈,不是YES/NO”写错了吧……不对……我看看……我靠,真写错了,居然是Yes/No,于是改过提交,I2y(277) ^_^

搞定I之后时间也不多了,D自然是不折腾了,应该说是折腾不起,于是提交了一个表达对题目作者vls的仰慕和对土LCLL的鄙视的程序。最后我们队以11题,领先两题的优势获得了省赛冠军,发现网上同步赛里也只有两个队过了10道题。

这次我们有几个比较脑残的失误,不过都及时纠正了,也没什么恶劣影响。比赛发挥算不错了,总体很顺,没怎么跳错坑,这是我和商天皇的最后一次省赛,无论过程结果都很开心,dd可以考虑包办4届省赛奖杯了……哦,最后附上《月見桜》(tsukimisakura)这首歌:

Get the Flash Player to see the wordTube Media Player.

ps: 2010省赛 Judge’s View && 解题报告 by hhanger
pps: 2010省赛Final Standing by hsys

32 Responses to “第7届浙江省ACM竞赛小结 by watashi@月見桜”
  1. Xuanwo says:

    赛前仰慕一发,求好运

  2. liuhighway says:

    对楼主无比仰慕

  3. CrazyAC says:

    同楼上~~~~

  4. prowindy says:

    赛前前来仰慕,求好运

  5. xujiazhe says:

    作为一个acm菜鸟 对楼主充满了无限的膜拜 望赐脚一舔

  6. jing says:

    表达对楼至无限崇拜,居然能A11题

  7. jing says:

    悲伤的一次省赛之旅~~~~(>_<)~~~~

  8. Navi says:

    ym学长…

  9. javaman says:

    ym

  10. owen_water says:

    ym all

  11. quark says:

    sf~

    秒杀得都好快……

  12. VegetableB says:

    sf

  13.  
Leave a Reply