2008年11月24日

昨天,ACM/ICPC杭州赛区以金奖(第五名)谢幕。对于Genesis队,本赛季的所有比赛已经结束,以后不大可能再在比赛中看到我们这支队伍了,希望Genesis得到的两块regional金牌以及一直以来的表现能让关注我们的人满意。

对于我已经研一的两名队友,这大约是他们最后一次以队员的身份出现在ACM/ICPC的赛场上;与高远(xgy)、杨克特(T_T)两位学长的无间配合是太过愉快的经历,学长的经验也让我受益良多。

而对于我,一名正式进入大学才三个月的大一新生,一切才刚刚开始;前方还长的路让人激动憧憬,请相信我会带来更多惊喜。

其实,这赛季能够连拿两金,取得对于我这种新手来说可称辉煌的成绩,不仅取决于全队的努力,对于我自己来说,其实不乏运气成分。这学期我主要的突破是仔细读了本《简明数论》(其实这书只有一半名副其实,“明晰”是无疑的,“简单”则谈不上),打下了还算扎实的数论基础,差不多能应付Regional中通常的数论题了,结果我们队参加的哈尔滨和杭州两个赛区正好都有数论题出现,特别是我们在哈尔滨最后才解出的B题更是我们夺金的关键。另外,在杭州赛的前几天,我匆匆浏览了《柔性字符串匹配》的后半部分,主要内容是用有限自动机做正则表达式匹配。对那本书的主题我自然是一知半解,不过倒对有限自动机有了较多的感受和认识。没想到杭州赛区的H题就是判断两个有限确定性自动机是否等价的题目。虽然没见过,但正好这几天见识了很多与自动机有关的内容,灵光一现就得出了算法,使我们队解出了第6题,也是场上解出的最后一道关键题目。

这样看来,我第一年的ACM/ICPC征程真可称顺风顺水,似乎幸运眷顾,完全没遇到挫折地走下来。当然,以后还是老老实实提高自身实力才是王道,近期打算学学Java,读读SICP之类的书。

这个学期还剩下大约一半,除了为了保持状态做点SRM以外,就不再寻求编程竞赛方面的突破了,应该多尝试点不同的内容。学Java达到与目前的C++近似的熟练程度,读SICP、Concrete Maths、Programming Pearls是必须完成的内容,如果还有闲暇就打算读读Algorithm Design以及一些AI方面的书目。最近一本《数学分析原理》让我多少发现了纯数学的美感,虽然这学期应该不大可能了,但以后还是要读些纯数学的经典教材的。物理是这学期多少令人头疼的科目,得抓紧看一下,希望能培养出兴趣。

好吧,读书去了。

Comments (9)

ACM/ICPC – Asia Harbin 2008 小结

10月8日晚的火车,三十多个小时的旅途,去往一座遥远陌生的北方城市,哈尔滨。

上火车后,惊喜地发现,我们硬卧车厢的走廊窗口下竟然有两相和三相的电源插座!可以无顾忌地使用电脑,似乎会给旅途增添不少趣味和意义。火车上,我把觉得比较有用的论文看了一遍,又对照着CD看了几章《听音乐》。

我在重要的比赛或考试之前容易滋生紧张情绪,这也是NOI2007的败笔之一。不过这次不同,一路上有队友相伴,本应枯燥的车厢里,充满欢声笑语。

灿哥通过神奇方式买到的火车票十张全是上铺,不过大家发现这种新式车厢的上铺非常舒服。更何况,在某人的下铺处有一只天真无邪可爱动人如假包换的小萝莉……这个话题不展开了,请自行YY。

T_T同学出了一些猥琐的迷题(e.g. 一只公牛和一只母牛同时踩坏了别人家的田,为何公牛主人赔偿三分之一而母牛主人赔偿三分之二?),令大家都很惊讶的,某位dd同学几乎每次都反应很快地第一个说出答案。好吧……在此我申明三点:第一,那些迷题没有一个是我之前听过的;第二,之所以我每次都能最先得出答案,我的唯一解释就是:我的思维敏捷、智商高;第三,我很天真哒,我的话讲完啦。

火车上的每顿饭都去餐车吃,虽然贵且不好吃,但毕竟是能找到的最佳选择了。这时T_T同学的母亲在德州站送上来的三只扒鸡正如雪中送炭,众饕餮很快就将那些可怜的无毛二足动物杀得片甲不留,对其二足尤不留情^_^。

火车到站时间是10日早晨5时许,一群几乎都没来过东北的人立即领教了寒风的威力。一干人等饥寒交迫地奔赴某盖头gg事先选定的车站门口的KFC,却发现人满为患无处容身。我通过手机上的Google Map搜索到了最近的另一家KFC,大家便打车前往。BTW,发现哈尔滨的GPRS网络很棒,明显感觉到比杭州的快,然而不知为何某只很拉风的iPhone在哈尔滨却无论怎样都连不上GPRS……

KFC的早餐让大家都找回了久违的饱腹感,充电完成的一干人等玩起了由gdb引进的多人纸牌游戏“盖棉被”。如果仅描述规则的话,听起来真是一个挺傻气且低技术含量的游戏:若干人轮流出牌,同时循环报数1至13;若某人打出的牌和说出的数字恰相同,所有人都需要尽量快地将手掌盖向牌堆,盖在最上面的手掌(也即反应最慢的)需要拿走所有的牌;手中无牌者胜。不过大家都玩得不亦乐乎,情不自禁高声大叫,引来了KFC MM礼貌的制止。在KFC的经历,让大家明白了一个深刻的道理(做小学生作文状):南北风俗不一样!好吧,看不懂的请略过或自行YY -___-。

打车来到哈尔滨工程大学……门口的八一宾馆报到,然后在志愿者MM的带领下入住十五元一天的学生宿舍-___-,还好后来在我们强烈要求下换成八一宾馆的标准间了^_^,偶和可爱的xgy队长gg一间哦~

10日一天都没什么安排,继续盖几圈棉被以后,一堆无聊人士围坐一圈玩起了同样低技术含量的梭哈,用另一副牌当筹码。赌博的结果是有的人(可怜的xgy gg,cmft)输到倾家荡产,有的人(就是我啦^_^,嘻嘻)成了大资本家,我赢了比翻倍还要多哦~

午饭选在某忘记了名字的火锅店,灿哥中途从机场赶来加入。相信大家都吃饱了,而且我自己认为吃得还不错,只是某人点了过多的丸子浪费不少……

下午和晚上,除了必要的赛前准备,大家仍然把时间用在了打牌与谈天之类娱乐放松的项目上。期间七个人玩两副牌的接龙还是挺好玩的。顺便炫耀下,在哈尔滨玩的很多盘接龙的分数都记录了下来,在幸运与实力的双重照耀下,dd同学是总积分的最后赢家~oh yeah~

期间值得一提的事情是,我们目睹了某欧阳极囧的脸红过程,并拍下了真相。欲知详情,请私下交流或自行YY……关键字:罩杯-___-。

10日晚上一直玩到午夜才睡。

11日上午貌似仍然是谈天玩牌。哈工程“大学生美食广场”午饭后,Genesis+gdb的猥琐男们在哈工程的长椅上懒洋洋地晒太阳,顺便开展猥琐的分手现场偷窥行动以及路过MM打分行动,期间小耗子乱入-___-。

下午试机,觉得电脑上的NetBeans还算好用,决定第二天比赛就用它了。试机期间,主办方的组织让人不能满意:每队三个人只有一份题目且不说,最不能忍受的是judge故障连连。我默默祈祷正式比赛时最好不要出现judge问题。

11日晚上,大家没有过分的娱乐,早早回到了各自的房间里养精蓄锐。我看了lrj“习题指导”和北大出版社《简明数论》两本书中的重要章节,听了贝交第五全曲,九点半安然入睡。

12日早晨六点半,醒来后的我感到前所未有的精神焕发,觉得这应该就是所谓的最佳比赛状态了。早餐中,灿哥给我们讲了若干“坚持到最后一分钟翻盘”的传奇故事。我相信听者没人想到,那天的比赛中,我们中的一支队伍会创造另一个传奇,一个毫不逊色,且注定被一遍遍讲述的传奇。

开赛半小时前进入场地,我们的装备大致如下:德芙巧克力一盒、红牛饮料若干罐、圣经一本(和合本+NIV对照)、牛津高阶词典一本、以及常用参考书一堆。

比赛开始了,共有十题,从A到J。按照一贯的读题分配:T_T看ABC,xgy看DEFG,我看HIJ。

我分到的题目都比较长,H大致看懂了,断定绝不是前期能写的题;I题意很简单,给定一个顶点的度序列,问是否存在对应的无向简单图,我觉得这应该是的经典问题,但却完全没看过类似的问题或算法;J的题意也不难理解,但可以看出,相当有大自然题的潜质。

大家把题都看的差不多了以后,互相两两交流了一下题意,没发现明显可做的题目。这时看到大屏幕上已经有四个队过题了,过的都是I。我意识到,I肯定不是难题,便专心yy之。期间xgy和我都怀疑是否只判断一下度的奇偶性就可以了,不过很快找到了反例。仿佛灵光一闪,我脑中突然出现了一个贪心构造的方法,讨论后,大家都没思路证明其正确性,却也找不到反例,于是我便上去敲了代码并提交之。

这时看到有牛队过了A,T_T给我讲了题意后,我写出前N层和的表达式给了他,他完善了一下二分答案的细节,便上去写了。写完后发现,按照我给的表达式计算的话,虽然输入不会超过六十四位整数,然而计算的中间过程完全可能会溢出,一时没有找到解决之道,只好由xgy把这个C++程序翻译成Java用BigInteger来写,交上去以后很快返回了Yes。这时已经拖了不知多久的I终于返回了,还好是个Yes。拿到两个气球的我们排名并不乐观。

在此之前,xgy给我讲了他对F的想法,我在他的基础上很快推出了完整的充要条件,但我俩都不太确定该怎么实现比较好。T_T听见后表示,如果充要条件是这样的话,那么他完全能写,因为写过很类似的题目。于是他上去用DP/递推的方式写了个程序,很快Yes了。三道题都1Y的我们第一次冲进了前十名。

写F期间,我和xgy在讨论G题,这道题的文字叙述得挺模糊的,不过通过仔细阅读加合理推测,我们很快发现原来就是一个有向无环图上的博弈问题,拓扑排序一遍再DP就行了,我上去写了以后也1Y了。当我们第4题的AC反映在大屏幕上的时候,我发现,在比赛时间过去约一半时,我们是全场第一个AC 4题的队伍,排名第一。旁边堪称全明星的清华IronGods队也只有三个气球。

这是我第一次感到情绪波动的时候,在此之前,我一直都保持着平和淡定的情绪,精神非常集中,头脑非常清醒,基本上处于巅峰状态,思考和敲题的效率都很高。然而此刻,看着大屏幕上飘扬在最上方的team53(我们的队伍编号),我出现了不应该有的过分激动以及过分自信。现在,我(多少有些羞愧地)承认,在那一瞬间,我想到了斯德哥尔摩。暂时领先造成的情绪波动直接影响到了我后半程的发挥,这也是我个人本次比赛得到的最重要的教训。

C题大概是早就得出了二分图最优匹配的算法,T_T上去写,似乎是用了令我难以置信的短暂时间就敲完了。交上去以后,返回了我们的第一个WA。我提醒T_T是否注意到船到达port以后不能再出来的条件,他意识到忽视了这一点,很快改好了,没想到仍然是WA。于是T_T打印了代码让xgy和我看。给代码查错应该是最需要集中精力的活,而我在看那份代码时却完全做不到这点,草草地、甚至一目十行地在看,怎么看都觉得没错误。很无奈的我们便想,是不是题目比较阴险必须用64位整数才可以过呢?其实赛后来看,这绝对是不必要的想法。因为当时至少有十多支队伍过了C,不少队伍都是作为第四道题过的C,且其中不乏1Y。这可以推断出,WA不大可能源于出题人的阴险,而是应该源于我们自身的问题。不过,当时的情况是,改了long long,依然WA。这期间,4题甚至5题的队伍越来越多,我们的rank一直在跌,前景非常不容乐观。看来我的缺点就是这样……处于顺境的时候容易被冲昏头脑,只有适当的逆境才能达到冷静。我再次看T_T的代码,不漏过一个字符的认真看,终于发现了程序中的低级bug。——只是注释掉了一行代码,程序就AC了。那个错误的根本原因是T_T在写那一小段时稍微有点想错了,而我从局外的角度看这段代码时,本应很快意识到这个几近愚蠢的错误,然而由于第一遍的不专心,我直到若干次WA之后第二遍阅读代码时才发现了它,这题做得不好,我至少应该承担一半的责任。

还好,虽然C题罚时比较多,在我们前四道题全部1Y的基础上,终于五题的我们名次还不错。接下来可做的题只有B和D。前者是数论题,我已经推导出了一个结果,有算法了;后者是纯粹的高斯消元而已;二者的共同点是都需要用到大数,最好是用Java来写。嗯……应该是我们队的另一个缺陷吧,我们没有人能把Java写得跟C++一样熟,所以必须用Java写的题在敲代码的速度上是吃亏的,甚至有些有关语言特性的东西还需要在赛场上试一试才知道。我们三人中写Java最熟练的xgy队长觉得B似乎更容易实现,于是便上去写。花费了比通常要多的时间,但却是严格地按照我给定的算法写出来的,没想到交上去以后WA了,只好打印出来交给我们查错,而他自己接着写D。——我想在这时我们的缺陷就完全暴露出来了:剩下两道可以写的题都需要用Java写,而赛前的训练中用Java写过题的竟只有xgy一人。这导致此时能写D的仍然只有xgy,而自己写的B还没能AC的xgy恐怕无法专心全力去写D,T_T和我在下面对着打印出来的B的Java代码YY其bug……T_T和我一致认为那Java代码十分“诡异”,表达算法时显得很不直白,但分析的结果也无法找到错误。我建议把那代码改成不那么诡异的形式再试试,大家同意了,便放下D来改B的代码。终于改出了比较清晰易懂的代码以后,测试的结果却似乎与刚才“诡异”的程序并无区别……(期间我还忍不住下手帮着写了几行,现在回忆时发现,赛场上的那几行其实是我平生第一次写Java代码- -。。。)貌似又是在我的撺掇下,把那个改完以后完全看不到区别的程序提交了,结果又是WA。这时进入比赛的最后一小时已经有一段时间了,封了board,各个队伍的排名已经不再实时公布,但从现场升起的气球情况来看,貌似已经有七题的队伍了,如果我们再不抓紧时间搞出第六题,能否拿到金牌相当未知……这时xgy继续写不知道有多大希望的D,而T_T和我做了一个相当正确的决定:我们从题意开始,对推导的过程完整地讨论地检查了一遍。期间,T_T的一句话启发了我,我发现原来是我在一开始的数学推导中少考虑了一种情况,难怪一直WA到死……我谢罪。。。还好把那种情况的代码加到程序里并不困难,加上以后就AC了,在比赛还剩十多分钟的时候,我们终于六题。

看到屏幕上的Yes的时候,我们全都激动地站了起来振臂欢呼。这是出现了一个喜剧性的小插曲,比赛的志愿者MM给我们送气球时弄错了:应该给我们的是B题对应的浅紫色气球,她却拿来了J题对应的深紫色气球。据说当时观众席上立刻一片哗然,没人想到会有队伍在比赛中把最不可做的J给做出来。周维民教授(ICPC中国区秘书长)也马上带着一堆摄影记者走过来对着我们不住地拍照。(嗯,以上文字有野史的风范,若有不确切之处请一笑而过^_^。。。)

最后几分钟的时间里xgy在敲D,不过花在这题上的时间和精力的确是比较少,加之我们不知道高斯消元在无需考虑精度的情况下会有比标准的做法好写很多的实现,所以直到最后也没能写完。至于旁边我们的Sirius凭借最后一分钟提交的D题冲至第五的神迹,我们也只有深深膜拜了。。。Orz

金牌到手的我们无忧无虑,下午我玩了会儿牌,听了会儿音乐,晚上代表队伍上台领奖(非常感谢队里的两位gg给我这个荣耀的时刻)。

接下来的时间里,Genesis与Sirius们都兴高采烈,发挥失误获得银牌的三个gdb则无法避免地淡淡失落。不过大家都知道团结勤奋的gdb实力还是相当强的,相信你们下次在成都的比赛中会弥补这次的遗憾!

其实我发现……比赛结束以后的事情我大都不太清楚了,因为颁奖结束的那天晚上起我就全身心地沉迷在一本奇书里。包括在归途火车上也一直是捧着电脑在进行一千多页的脑力激荡与思维历险……嗯,接下来我会抽空慢慢写点关于GEB的读后感的,虽然一下子很难整理出繁复的思绪。。。

哦……这次的哈尔滨之行Sirius与gdb各自也有非常精彩的小结,请原谅这篇略有些虎头蛇尾的文章吧,这五千多字已经写得我要吐血啦。。。有什么脱误遗漏错愕指出请指出,我一定修改。

好了,下一站杭州,在自己家门口比赛,相信通过对哈尔滨之行的总结,我们会越发完美。Genesis加油!

Comments (16)

July 14th, 2008

每个或有或无意义的开始,我都会变得兴奋而躁动,一些忘却抛弃,一些憧憬期许。就像今年一月我无理由地坚定地认为2008年是美好的一年一样,七月的最初,我同样坚定地做出七八月的暑训、今年下半年以及整个大一的一年时光都将美丽姣好的没有理由的结论。——七月四日

过了二分之一的这个七月,给我的感觉不同于以往的任何一个时期。——极度繁复的同时,也极度简约。极度火热的同时,又极度冷寂。贯穿每日的主线是,一边拼命挣钱、一边拼命花钱,一边努力出题、一边努力做题,一边尽力提高自己、一边尽力指导别人。就是这样,若非亲历很难体会。

集训前两周期已经结束的六场比赛需要总结一下。

Contest 2 by Balloon 是没进行任何ACM/ICPC有关的活动几十天之久后第一次比赛,完全没状态,Rank 12。依序看到D,便知道该怎么做了,19 min 1Y,是全场第一个AC此题的。看到有两人AC了A,略思考便想到了跟NOI某题类似的做法。当时认为,精度的缘故,需要写一个分数类,很快的敲完了。后来的事实证明,我现场敲的分数类对负数的处理有极大漏洞。可我错误地估计了错误,一遍遍地在主程序中寻找bug,WA无数次才意识到是分数类写得有问题。后来我发现,只要把我第一次提交的很垃圾的程序加上两行补丁,就可以AC。现场在66min交到第九次才AC的原因,一是一开始错误地估计了bug的位置,二是正确地找出bug以后没有仔细思考就开始写较为复杂的补丁,而没有看清错误的本质所在。这两个题水过以后,看上去可做的题目有B和E。对于B,我非常怀疑自己此时的coding能力能否应对这个算法不难代码似乎不好写的题目,于是看E,这个我最终交了13次也没AC的题目。交了4次E,完全不知道为什么WA,放弃了。然后开始很慢的写B,写一种极度麻烦的算法,一直到145min才交了两次AC。再次概览剩下的题目,仍然认为只有E可做,拼命查错和提交,一直到比赛结束都无果。最终才明白,原来E是因为误解了scanf中”\n”的意思,导致读入出错了……交的第二个程序的算法就是完全无误的。如果能更早地做掉E,显然与它的加强版F题不存在AC的障碍。真没想到算法一点问题都没有还会败在输入上……

Contest 3 by Cannon 也是一场郁闷的比赛,Rank 8,虽然Rank有所上升,但是题数上非常不满意,只有两题,是第一名的三分之一。陷入两个大坑,是做过的所有比赛中最郁闷的一次。看了A就觉得可做,不过大概由于慢热的缘故,26min时交到第4次才AC,原因主要是coding时欠考虑吧。又看了B和C,B觉得略有麻烦,C似乎是裸的高精而已,就开始写大数类。看来是完全没有吸取上次手写分数类的教训,对自己当下的coding能力认识不足,大数类不是写错就是效率有问题。期间推了下B的式子,也AC了。在C还是没能AC的情况下,又陷入了F,记忆化搜索,WA无数。后来发现,我的算法和标程不一样,但也没找到实质性的错误。剩下的时间就是在疯狂地改和交C和F,无果。比赛结束前20min意识到C可以用模板,可惜对学校的大数模板完全不熟悉,C++中stream相关的内容也基本忘了,输入输出都有点搞不定……现在看来,这次比赛AC
题数过少的原因之一是我较为熟悉和擅长的DP一题都没出。见到的题目太少,略有些 ad hoc 的题目就会搞不定,这是目前最大弱点。

Contest 4 by Die 的感觉稍微好一点,Rank 5。35 min时一次AC了H,擅长的套路。然后67min时用了三次提交AC了G,算法完全正确,问题在于无视了题目中一个条件,导致两次WA。然后就看到很多人过了B,便也很容易地AC了,在此之前的一次提交竟然是MLE……原因是忘了输入完成以后break。下一道题的目标我选了E,交了9次基本都TLE以后,确定自己的算法错了,就中途离开机房吃饭去了。这场比赛做得太急,导致不细心。赛后觉得,如果更多地花点时间思考下D,是应该能搞出来的,错误地估计了其难度与麻烦程度。

第一轮完毕以后,计罚时和不计罚时的rank分别是9和11。

第二轮,从 Contest 5 by Balloon 开始,逐步有了状态,Rank 3,比赛过程可称顺利。一开始看到了B,觉得是一般难度的DP,随手写了交上去,然后WA。静下来看一下,发现整个算法是错的,换了正确的算法重写,结果疏忽了一句保持单调性的话,交到第三遍才AC。下面是E,非算法题,比较熟练地用着STL,1Y了。F又是一个DP,吸取教训仔细想清楚了才写,同样1Y。接下来做A的时候又卡了一下。最开始写的是搜索,没有估计好复杂度,TLE两次,第一次交TLE了以后还以为是被卡了常数,第二次TLE后算了下复杂度才意识到必须加上记忆化。加记忆化的时候又写错了一次,第四次才AC,属于失误。看到wanwei似乎很轻松的1Y了winsty的小蘑菇题G,虽然明知自己对这种题目根本不擅长,但也没发现有别的可做的题目了。写了很久,调了很久,花费了近一个小时,还好1Y了。在这一段过程中一直都是紧随Murphy,排名第二,看到他过了C,就也去搞。没想到一下子就看出了C的本质,用DP预处理一下后,又1Y了。这时,只剩下了一道没人碰的蘑菇题D,我怎么看都没信心,很累,又计算了一下发现后面的人不大可能超过来,就很高兴地提前近一个小时出去吃饭了。后来得知G的数据有小问题,rejudge了以后rank 2的位置变成了watashi。在题数上,应该说没有任何遗憾,1Y率有提高,很满意。

Contest 6 by Cannon 是目前位置的最好成绩,Rank 2,但是不像上次一样毫无遗憾,因为是由于不必要的失误没得到Rank 1。前一天晚上只睡了五个小时不到导致状态很差。开场先做了矩阵题G,打算秒杀之,没想到一开始就因为矩阵乘法写得不太好而TLE两次,优化了效率以后又接连地WA,要郁闷死了。到论坛里看了答疑才知道原来自己把题意理解错了,改之即AC。91min第7次才AC这题,真是开场不利。AC了G以后开始做C,很老的题,用匹配做,没想到竟然WA。难道自己已经退化到连Hungary这样简单的算法都会写错?很沮丧,就暂时放下了。看到A是不难的DP。哦……好吧,对于我来说不难的DP,WA一次以后AC了,WA的原因是没看清题……寒。把手放在键盘旁的圣经上,定神了以后做C,一个不太难的搜索题,终于一次AC。接下来的时间就在搞C,出很多组数据来测,怎么都看不出为何会WA……这时看到自己是Rank 2,3题的两人之一,但由于罚时太多太多后面的人很有可能超过来。十一点一刻的时候最后交了一次WA终于放弃了,因为实在是找不到错误,加上极其瞌睡,就跑掉了。没想到但是直到结束竟然能保持住Rank 2的位置。后来得知,C是因为输入处理错了导致不断WA。竟然又是该死的scanf里面的”\n”,第三道题了!所以太遗憾了……真不应该那么早离开的。以后再遇到这种莫名其妙的WA一定要仔细验证下输入输出。

Contest 7 by Die 打破了前五场Rank单调递减的神话,Rank 6。做得不够好,罚时太多了,而且策略有失误。开场以后大致看了一遍题,发现A是可做的DP,虽然有点麻烦。写了四十多分钟,交上去WA。惊讶地发现这时AC两题的都有了,都是B和E,E有十几个AC的。意识到E是第一遍没看出来的极水的题,随便一写就1Y了。又去做A,又WA一次,发现没看清题,53min第三次提交才AC了。接下来当然是做B,做的过程很不顺利。一开始发现搜索可做,经历了MLE、TLE和两次WA以后,对搜索有些绝望了。惊奇地发现用匹配可做,粘贴了任意图匹配的模板,终于很不容易地AC了。事实上这题完全可以用搜索,是我一开始写丑了。接下来的目标我锁定在D上,自以为对这类最优比率的题目非常熟悉,不就是二分答案么。虽然写起来也有点繁,不过还是很有信心地在写。写完以后,就总是WA,发现我的Bellman-Ford总是莫名其妙地找不到负环……在那边拼命地调啊改啊,基本上各种可能的错误返回都经历了一遍,还是没能AC。期间发现比我多一题的都是AC了F,但是F使我非常不熟悉的类型,完全没法形成完整的思路。到了只剩一个小时的时候,我终于放弃了搞了一个半小时的D,开始硬着头皮写思路还想不清楚的F,加上这时已经很累了,一直到比赛结束还没调出样例来……罚时太多就不说了,看错题写错代码还可以解释成状态不好。关键是,这场比赛的策略太失误了!像A那么麻烦的DP显然不应该作为第一道题来做,要相信肯定会有比这水的题嘛,这直接导致了E和B的用时比正常值多多了。至于D,后来知道,应该用迭代法做的。自己不会这个方法,AC不了,也没什么不正常。但问题就在于,D搞了那么长时间,交了24次,实在有些过于固执了。虽然E是我不熟悉的类型,但毕竟是非常可做的题,那么多人都AC了,只要有时间慢慢搞应该不存在问题的,至少完全可以写个复杂度略高但好写很多的算法。唉,还是经验少,太莽撞。

第二轮结束以后,计罚时和不计罚时的Rank都是6。

~~~~以下是三、四轮的总结~~~~、

Contest 9 by Cannon,一场有失误、没遗憾的比赛,Rank 6。开场扫了一遍题,没发现特别秒杀的,就开始写F,一道简单的树的题,轻松1A。不久后又有人过了A,属于经典问题。一开始没想清楚算法,WA了,又因 为忘了删掉调试语句Output Limit Exceeded了一次(第一次得到这种返回的说- -)。好在第三次提交就AC了。这时有一些人过了C,一个小蘑菇题。这种题我也掌握了一些诀窍了,就是不厌其烦地尽量结构化,让自己能掌握全局的思路,就 可以了。似乎用了十多分钟就很高兴地AC了这题。E是一个数论题,略加考虑写了一个递推求欧拉函数的程序,还不厌其烦地加了很多优化,没悬念地AC了。这 时,比赛开始才一个半小时,我AC了4题,速度都很快,排名第一位。这时,D那种蘑菇题我显然是不写的,F可以看出来是搜索可怎么分析都会TLE(后来知 道标程是IDA*)。可做的题目只剩下B,一个背包问题的变体。我yy了一会儿,发现自己可能“证明”了,可以将一种规模一定不可做的01背包问题规约到 这个题,所以说,这题一定不可做了!我甚至抱定了“标程的算法是错的”这样的信念。加上我很期盼的快件到了,便很潇洒地离开了机房。当然,当时“规约”的 证明是完全错误的,属于失误了。最后有五个人很艰难地搞出了B题,我就排到了第六,不过也没什么遗憾的。呵呵,恐怕我觉得不遗憾的原因之一是我离开机房以 后取到了期盼已久的相当漂亮的原版书吧,Music: An Appreciation Fifth Brief Edition (with 4 CDs and 1 CD-ROM)。

Contest 10 by Die,发挥正常,成绩斐然,Rank 2。顺序看到C以后觉得好做,一道不难写的图论。第19分钟,全场第一个提交,AC了,然后继续看题。一分钟以后的全场第二次提交是hhgg的,AC了G 题。于是马上去看,发现又是一道跟背包有关的DP。由于细节的错误,拖到52分钟交了第三次才AC。不过仍然是全场第一个2题的,保持rank 1。再次仔细看了剩下的题目,A根本读不懂题意,B是我绝对不碰的蘑菇题,D是暂时不想碰的小蘑菇,E和F好像都是建立图论的模型。于是在那里做E,连续 WA了四次以后才领悟:我建立的图论模型完全是错误的,这不是一道图论题!(事实上,赛后得知是用搜索做的。)放弃了E以后,在很麻烦地写F。一次TLE 和一次WA以后,感到对这题没有把握,无法控制程序的思维复杂度,放下了。看到好多人都在写不太好处理的D,只好跟风了。这题是一道较为麻烦的文本处理的 题目。做这题我采取了非常正确的策略:先在forum里看了长达数页的问题,确保正确理解了题意、没有漏掉细节,然后仔细地设计了程序的结构,怎样最方便 处理,很充足的准备以后才开始写。第一次提交返回的PE比较让人振奋,194分钟时交了第三次AC了。很囧的是,两次PE的唯一原因是没看到输出的 cases之间要加空行的要求……很有喜剧效果。这时好多好多人都三题了,没想到我竟然是总罚时最少的。不记得最后的及时分钟在做什么了,大约已经放弃写 程序了,坐在那里静静地读圣经吧。结果,比赛剩不到十分钟时Fire大神AC了B,就得了第二。

Contest 12 by Balloon,有一定失误,Rank 10。大致看了题以后,没发现能秒杀的。只有小蘑菇题G似乎能做,快速地敲完了代码,却TLE,尝试优化时间效率,却TLE依旧,非常茫然。半小时左右的 时候,看到有很多人AC了F,便去做。写程序找了半天规律,推出了公式,拷贝了大数模块,提交以后SF。改了大数类里的数组大小,就AC了。同时,有不少 人1Y了A,判断出一定是第一次没看出来的秒杀题。找到了一个必要条件,充分性不会证,写出程序过了样例就提交了,一次AC。想到了B的算法,二分答案加 匹配,于是做。第一次有种特例没处理到,SF了,第二次提交AC。期间还在修改和提交最开始写的题G,找到了一处导致死循环的错误,把TLE变成了WA, 又因为某种小错误折腾了很久,终于在九次提交以后AC了,真是很没状态。剩下的题目里,C与E,由于算法复杂和程序蘑菇的缘故,对于我来说不可做。D与H 是可以考虑的,前者是大家都在搞的字符串蘑菇题,后者是数据结构题,用平衡树或者块链做都没问题。二者之间,我选择了H,开始写需要不少扩展的 Treap。最后两小时一直在搞这题,太久没有写这种东西,期间失误数不胜数,最终也没能AC。这次的失误在于:面对令人困扰的G,没能冷静、细致地查 错,而是一遍遍地无策略地乱提交,导致在相同题数的家伙中间排名很靠后。H在实现时有失误,为了删除操作的简洁,采用了懒惰删除的策略,却没有意识到,这 会使其它每种操作都要额外考虑更多的情况,大大提高了整个程序的编程和思维复杂度。B组比赛的特点,似乎是每到题目多多少少都会融入蘑菇的元素,导致我做 起来不顺。这大约与B组组长的特质有关?^_^

Contest 13 by Die,发挥不错,Rank 1,第一次呢,8题的比赛AC掉7题也算比较圆满了。开场看到C题以后觉得比较水,8 min的时候秒杀了(其实还小调试了一会儿弱智错误)。提交的时候看到好几个人过了A,判定一定是水题,找了个充分不必要条件就写了很短的程序交了,13 min时1A。下一道去做的是H,一道多少有点old的题,隐式图里BFS找最短路,同样还是因为弱智错误调试了一会儿,没想到38 min AC的时候还是全场第一个三题的。这时剩下的就没有水题了,明显的广搜但写起来很繁的是B,不太擅长的几何题是D,E看上去挺大自然的,简单但是处理起来 麻烦的是F,一般困难但完全可做的图论题G。考虑了以后,我还是选了F先做,因为这题到最后会被很多人AC,我是不得不做的。好在没有出什么低级失 误,83 min时1A。接下来的选择就不太好做。别人在这时大概都会选D做,因为这的确是剩下的题里面难度最小的一道,不过考虑到我不擅长几何,还是去做了更有把 握的G,果然写起来很顺利,113 min时一次AC。迄今的五题全部是一次AC,用时非常低,Rank 1保持。这时D好几个人过了,B还没人碰,不得不写D了。发现自己这么晚写D还是有好处的,因为一开始题目描述有误,更新了以后变简单了。写好了以后,不 断地过不了样例,不断地发现一开始的思路就有错。好不容易把样例调过了,交上去,返回了我本场的第一个WA……检查了好久才发现是题目要求输出之前要排 序,175 min用了三次提交AC。剩下的两道题里看上去可做的只有B。离结束还有半小时的时候写好了,提交上去WA。很无望地在读代码查错,怎么看都觉得代码无懈 可击,用了几种诡异的办法打补丁,仍持续WA。直到距比赛结束还有五分钟时才猛然发现:自己开数组时犯了一个6*6=24的错误!又是这种令人沮丧的情 形,数组开小了造成的后果是WA而非SF……把数组开大以后,终于在最后时刻AC了,凭借相对很少的罚时,保住了Rank 1。赛后发现,最终也没人碰的E事实上是完全可做的,如果B的数组没有开小,最后留下半小时写E的话,还是有一定可能圆满8题的,算一点点遗憾吧。

Contest 15 by Balloon,令人没想到的是,在上场的个人最好成绩以后,这场迎来了暑期集训的最差表现,Rank 16,惨不忍睹,感觉整个比赛都在梦游。总结教训的话,却找不到什么能凸显出来的失误,只是不知为何一直在犯低级错误。

Contest 16 by Cannon,最后一场,比得如何都很难影响最终的结果,所以对我是一场轻松平淡的比赛,Rank 4。开场很快AC了B和G,简单图论和简单DP。C是一道有一定难度的猜数字的题,O(N^2)的DP是显然的,但这样会TLE也是显然的,我把DP写出 来了以后一直找规律,但无果。后来发现从另一个不太显然的角度去设计状态复杂度就低了,就AC了这题。期间小失误若干,TLE一次,因为忘了测试时 main里写的是for(;;),汗。F是搜索题,时限5s非常厚道,我的复杂度非常高的程序用时4.4s一次AC了,呵呵。 剩下的题里面,可做的只有D,一道可以用RMQ解决的题。SF、MLE很多次,才发现用的RMQ模块有bug……很艰难地用了七次提交AC了。剩下的时间 在yy A题,看到有人过了,但是想不出来,就去吃饭了。

Comments (4)

ACM新手上路总结及感言

(6月5日小更新,增添一些细节。)

儿童节那天,七场新手赛全部结束。当天睡得很早的我,第二天早上才看到总积分的榜单,对着那些空洞的数字,对着那些浸透多少人奋斗与梦想的数字,我看了很久。

本篇的标题早就定好了,就不改了。不过,我想这篇文字不会单单总结这半年来参加的ACM/ICPC活动,我希望它是我加起来不到两年的OI+ACM征程的回顾,和对将来不知会延续多少年的竞赛之路的展望。

~~~~~~~~回首往事的分割线~~~~~~~~

两年前的此刻,我还不知算法为何物。(现在的你,真正理解什么是算法吗?)

两年前的六月底七月初的某个不确定的日子,除了C语言的语法什么都不会的我,第一次以竞赛的目的走进高中的机房。开始了,我的OI征程。那天上午,做了一套NOIP模拟题,得分130。记得那四道题中竟然有一道平衡树题。所以说……我做的第一套NOIP模拟题真是太不厚道了!(现在的你,已经参与过不知多少次这样那样的模拟赛的命题了吧,有几道是自己满意的好题目呢?你发现问题的能力比那时有多少增强呢?)

两年前的七月与八月,正是最热的时期,也是我如饥似渴获取知识的时候呢。在那个暑期集训结束的时候,我再一次对照了NOIP大纲,确定其中知识的盲点已经不存在了。大概也就是在这个时期吧,第一次拿了学校OI小组内部比赛的rank1。呵呵,那些个阳光灿烂的日子,我心里想的一定是随随便便拿个NOIP一等奖然后回去专心钻研我的数学竞赛。就是从那时开始狂妄与轻浮的吧?(现在的你,把这些坏毛病改掉了多少呢?)

两年前的九月十月十一月,一起学OI的同学,都在进行最后的冲刺吧。而我呢?显然没有尽全力。在论坛上灌水,跟MM聊天,在网上闲逛……我想这些活动的时间,加起来会超过这一段我做题学习的时间吧。觉得自己什么都会了,NOIP一等奖如探囊取物。(现在的你,每天几个小时坐在电脑前面时,哪些活动占的的时间最多呢?)

两年前的十一月十七日,NOIP2006复赛的前一天,在郑州。关于那天的记忆,大部分都已变得模糊。记得有跟某MM一起逛街,却把她的名字忘了。记得买了个钱包,却忘了是买给谁的。可以确定的是,当天晚上的九点到十一点,哦,也许是到第二天凌晨,我都待在旅馆里一起来的女生的房间里,跟她们很愉快地说笑,其间教她们唱了《隐形的翅膀》这首歌。(现在的你,对音乐的欣赏风格发生了一次又一次的转变,很久不听张韶涵的歌了,把《隐形的翅膀》的歌词也忘得差不多了吧,也听了许许多多不同风格的歌,可是,像当初一样打动自己的歌还有吗?)

两年前的十一月十七日上午,NOIP2006复赛,郑州轻工业学院,机房C。对着完全写错的DP,没有检查和测试,心里想的却是要不要用四边形不等式优化。面对稍微有点变化的背包问题,狼狈地发现连01背包都写不出来。在最后半小时匆忙地写了个蘑菇题。出来以后对老师信心满满的说两百分没问题。(现在的你,代码的速度和准确度自然有了很大提高,可是,为何像那时一样的低级致命错误仍然在重复呢?)

两年前的十一月十七日下午,坐车回家。在现场等到了评测结果的老师打来电话,告知我100分的可怜成绩,并一遍遍问我是否申诉、复评。我瞬间回忆起了那道寄托希望的DP的低级错误,明白这个成绩是绝对准确的,变得颓唐。跟家里人打电话,几乎哭泣。(现在的你,又经历了许多次失败,可是,面对失败的态度有改进吗?)

两年前的十二月开始,我被迫承认不得不在OI的路上走下去,设想中的一次小插曲式的短途旅行,变成了贯穿整个高中阶段的OI征程。每天中午到机房做USACO Training,瞒着家人,瞒着班主任,他们都以为我会在宿舍午休。教室里,趁老师不在的时候,读Weiss的《数据结构与算法分析》,读《算法导论》。疲惫,也一点一点的脱胎换骨。(现在的你,明白了当时无法接受的失败完全是因基础不扎实所致,那么,在你现在学习中的各个方面,基础扎实吗?)

一年前的三月三十一日晚,一次成绩还算满意的高考模拟以后,没上晚自习,而是到了机房,正式停课准备省选。记得非常清楚,当晚AC了卡了我很久的 Cryptcowgraphy 一题。第二天开始学习网络流,继续做USACO Training。(现在的你,面对那种程度的题目自然会觉得小菜一碟,做题做得越来越快,可是,有多久,你忘记了那种AC了困扰自己几个月的题目的欣喜?)

一年前的四月的前二十天,在为21日的省选而奋斗。4月1日到4月5日,用了五天时间,把USACO Training从4.2做到了6.1,通关了,后来写了篇《USACO心得》。Bellman-Ford、最小后缀、虚二叉树、匈牙利算法、RMQ、KMP、LCA、图的割顶与桥、并查集、凸包、高斯消元法、收缩强联通分量、树状数组、Splay、Treap……这些算法和数据结构,都是在2007年的这20天里学的。(现在的你,还会有像这20天一样充实的学习过程吗?)

一年前的四月二十一日,省选,HAOI2007,又是郑州轻工业学院。提包里装着打印出来的几十页的算法,只是为了比赛前的前一天晚上看上两遍。结束以后,对老师说,展现出了自己的全部真实实力,但也没有超常发挥。第二天的学校门口,已出现“荣获河南省第一名”云云的大字。(现在的你,能做到在每次比赛中都“展现出了自己的全部真实实力”吗?)

一年前的四月最后几天,以及五月六月七月,怀揣着NOI金牌的梦想奋斗。大多时间,坐在属于我一个人的空荡荡的的机房里,看书做题。期间去郑州101中学,省队集训,非常好的朋友、兄弟。Suffix Array的O(NlogN)和O(N)算法,Network Flow的SAP、Dinic、HLPP等算法,字符串匹配自动机,最小树形图,博弈论的SG函数理论,线段树,大概是在这段时间学习的。《组合数学》、《Code Complete》是在这段时间读的。还学用了Emacs、GDB、gprof等工具。用梦想取暖的简单生活。(现在的你,还能找到一个单纯明确的梦想为之奋斗吗?)

一年前的七月倒数第二天和八月第一天,遥远的福州,NOI2008的两试。铜牌,我的OI生涯的句号。我软弱到不愿提起那次经历。(现在的你,比那时变坚强了吗?)

一年前的十一月十六日,在郑州的河南省实验中学逸夫楼三层的机房里,写下了充满梦想的文字,后试图约xtt出去未果。次日,NOIP2007,满分。(现在的你,还记得写下那些文字时的心情吗?)

从那以后,我的生活真的与OI两个字没什么关系了。

好了,以上跑题完毕,下面开始说本次ACM新手上路。。。- -

~~~~~~~~跑题完毕的分割线~~~~~~~~

总结一下已知的缺点和解决方案:

  1. 思维广度不够。一些完全在能力范围内的题目,不知为何当时就是想不到。解决方案:似乎只能多做题多思考吧,切ZOJ2.0上的题目。
  2. 对STL不熟悉,导致每次用到几乎都要查文档。解决方案:抽空把文档看一遍,多用。
  3. 数学功底不够,尤其是组合数学很需要加强。解决方案:再细读一遍《组合数学》。
  4. 计算几何和数论根本不会。解决方案:不会就学呗。计算几何看lrj的书好了,手头还有一本清华社的《计算几何——算法与应用》;数论还不知道该看啥。
  5. 某些算法(比如说网络流)的实现,特别是应用,遗忘得太多了,要重新拾起来。解决方案:仔细重读一遍Weiss的书以及CLRS好了,这次读英文版的,注意习题。(或者读别的算法书?)
  6. 看题不仔细。解决方案:比赛时别太匆忙,多花点时间仔细看题利大于弊的。
  7. 体力和意志力不行,每次比赛都坚持不到最后就不写了。解决方案:还不知道。找人组队可以很大程度上弥补体力的不足。但如何培养“不到最后一刻决不放弃”的意志力呢?

当然啦,上面光说缺点了,其实我的优点更多,比如说代码写得快、算法会得多……还有其他好多好多啦都说不完的。但是我这个人这么谦虚,是绝对不会对别人炫耀甚至提起自己的优点的。我一直都是那样的自省、内敛与深沉……(以下省略二千字- -)

感言:

感谢 Channel [V]、MTV……哦,不好意思拿错稿了掐了别播啊。

不到半年的ACM/ICPC经历,让我懂得的最重要的事情,是团队合作。我知道了,ACM不是单打独斗,个人能力很重要,但良好的团队合作更重要!(本段做字正腔圆感情充沛状,末尾语调上扬,眼神坚定。)

需要做的事情还有很多,很多东西还要学习,不仅是知识方面,也包括“如何平衡ACM与其它各种事情的关系”之类命题。但是快期末考试啦,除了考虑出题以外,考完之前就不安排ACM方面的计划啦,考试完了就该暑期集训啦。

所以,千言万语,赶紧汇成一句话:期待暑期集训的精彩吧!

梦想:

我要登上 ACM/ICPC World Final 的领奖台。

附:[转载] For Beginners Final Ranklist

Rank ID            C1    C2    C3    C4    C5    C6    C7    Points
1    dd_engi       2/28  6/104 3/40  4/53                    0.2795926
2    ll861112      3/28        2/40        2/50  5/69        0.2696066
3    moondy        1/28  6/104 1/40  2/53  3/50  4/69  4/47  0.2607697
4    Ouyang_Jialin 2/28  5/104 3/40  3/53  2/50  3/69        0.2511093
5    yuzhirenzhe   2/28  4/104 3/40  3/53                    0.2414939
6    rpggpr        1/28  5/104       1/53  2/50  3/69  5/47  0.2379382
7    EZdestroyer   2/28  6/104 2/40  1/53        4/69        0.2370919
8    navj          3/28  5/104 1/40  2/53  0/50  1/69        0.2179556
9    hsys          1/28  3/104 0/40  4/53  2/50  2/69  3/47  0.2150158
10   asmn                6/104 2/40  3/53        3/69        0.2077743
11   classT        1/28  4/104 1/40  3/53  2/50  3/69  3/47  0.2039118
12   relive        0/28  4/104 2/40  2/53  0/50  3/69  3/47  0.1957696
13   hazy          2/28  4/104 1/40  3/53  1/50  2/69  1/47  0.1954794
14   ljzhao        1/28  1/104 2/40  3/53  0/50  3/69  2/47  0.1926352
15   vivyli        0/28  4/104 2/40  3/53  0/50  3/69  2/47  0.1926352
16   wanwei        0/28  3/104 1/40  2/53  2/50  1/69  4/47  0.1916884
17   aaahexing     0/28  4/104 1/40  1/53  2/50  3/69  3/47  0.1857696
18   winsty              4/104 2/40  1/53  1/50  5/69  0/47  0.1809253
19   aaron35203432 0/28  3/104 2/40              2/69  3/47  0.1716614
20   owen200402    1/28  3/104 1/40  2/53  0/50  4/69  1/47  0.1602673
21   jay23jack     1/28  4/104 1/40  1/53  2/50  2/69  2/47  0.1567290
22   liu3063031168 0/28  5/104 1/40  1/53  0/50        3/47  0.1557746
23   pkwgl         1/28  2/104 1/40  1/53  1/50  2/69  3/47  0.1535296
24   milki         1/28  3/104 0/40  2/53  0/50  2/69  2/47  0.1449888
25   retadykay     1/28  2/104 1/40  2/53  0/50  3/69  1/47  0.1419284
26   gaohaidong    0/28  3/104 2/40  1/53  0/50  2/69  1/47  0.1291083
27   hzqtc                     1/40  1/53  2/50  2/69  0/47  0.1128534
28   wyest         0/28  2/104 1/40  1/53  1/50  2/69  1/47  0.0952621
29   Jiangch       2/28                                      0.0714286
30   pp85365640    0/28  3/104             0/50  0/69        0.0288462

Comments (5)

省赛总结

坐了一夜火车,在昨天上午十点多赶到紫金港校区,浙江省程序设计竞赛十二点即开始,OIBH队依旧。

嗯,省赛就是不一样,免费发T-shirt,还有免费的午餐和晚餐。由于预习生的缘故,我们属于观摩/旅游队,不计入最终排名。

到了机房里,看到墙上挂着的十二个不同颜色的气球就开始激动,好像都没参加过这么多题目的比赛的说。分配任务,我看A、D、G、J,tzf看B、E、H、K,ww看C、F、I、L。于是比赛准时开始了。

我对自己的四道题目各略读了一下,判断出A是极水的,D不可做,G略麻烦,J矩阵乘。于是在他们两个还没看完自己的题的时候随便就AC了A题。然后他们俩告诉我E和F极水,我看了一下先敲F,没想到挂掉了,我的判断是行末有空格,把输入的方式由gets(s)改成scanf("%s",s)就好了。(据说事实上是因为数据是Windows格式的换行符,嗯,对于输入输出的处理要想考虑周全也没那么容易呢。)然后敲了E,AC了。

这时秒杀题已经没有了,在我coding的时候tzf和ww讨论确定了B就是一个裸的最小生成树,没有带模板(事实上,我们没有带简单的算法的代码,比如说,带了最小树形图,但没带最小生成树),我敲了std::sort加并查集的Kruskal,迅速AC之。

接下来,摆在我们面前的是各自手中的三道可做之题,ww的小蘑菇题G,tzf的DP题H,和我的矩阵乘法J。这时,我们队的薄弱环节就暴露出来了,只有我一个coder。如果有两人甚至全部都可以coding的话,我此时做出的决策会是将连续coding了半天的我换下来做点低强度的事情,让别人coding他自己的题。但是,没有这种选择。我的决策是:让ww在纸上写G的伪代码,我敲H,J先放下。结果由于考虑不周全的错误H交了三次才过,原因应该是我的coding状态开始下降。

出去喝饮料、上卫生间、凉水洗脸,回来以后状态好了一些,写一开始就想到思路的矩阵乘的J题,在文件的第一行写上注释“I Love Tan Zhiyi!!!”(别乱想!TZY是我很喜欢的线代老师。)交了两次才AC,是因为输入处理的时候有一种特殊情况,本来已经考虑到了,但因为样例里没有,所以打算先过了样例,然后再把处理特殊情况的代码加上,但是过了样例以后就很高兴地拿去提交,忘了还有一段该写的代码没写,所以没AC。哦……我真啰唆。

ww很快就把G的伪代码写完了,也出了很多组测试数据,交给我coding。tzf推出了L的公式,两人讨论一下复杂度以后觉得可以做,又讨论K无果。我拿着ww给我的伪代码和测试数据、tzf给我的公式,在不长的时间里AC了G和L(事实上coding时还是很磕磕绊绊,没有前几题时的手感),加入到对K的讨论和思索中。想啊想,想出了用繁琐的位运算降低常数的招数,search了一下别人AC这道题的用时,觉得应该就是这样了。不过,我此刻coding手感已经极差了,调试了很久,才发现犯了局部变量未初始化的超低级错误,幸好没有乱提交,还是一次AC的。

这时候,AC了九道题的我们能选择的题不多了。C是计算几何题,我完全不会;D看起来非常难,我们都一点思路也没有;I是长达五页的蘑菇题。结合各题的提交和AC次数来看,D首先被排除,曾经钻研过计算几何的ww想到了C的O(NlogN)算法,意志坚强的tzf看完了I,觉得只是严格按照超级繁琐的题目描述coding而已。C与I之间,我,唯一的coding男,选择了写C,因为我真的不愿意去写蘑菇题的!(分享winsty关于蘑菇题的金玉良言。)从赛后的情况来看,这个选择是正确的,因为I直到最后一刻仍然是有人提交无人AC的,做出十题的金牌队伍都是比我们多了C题而已。

直到现在,我相信ww提供的精妙异常的O(NlogN)的I题算法是完全正确的,交了整整十次都没有AC,或者因为我没有实现正确,或者由于精度问题,我们都不知道计算几何题中究竟应当怎样控制精度。当然,相对于上次校赛卡在二分答案题上的OIBH队,这次我们队卡在计算几何题上,已经心甘情愿许多了。

最后一小时封rank,加上没有给我们发奖(如果我们是正式选手,应该得银奖),所以我现在也不知道我们这个不计入总成绩的队伍的最终排名,大约是12或者13吧。OIBH队在成长,仍没有克服它的致命缺陷。接下来期待暑期集训吧!

最后是用Nokia 5700 XpressMusic拍的两张照片:

为什么我拿着一本圣经?嗯,因为我新手赛rank1的那次就放了一本圣经放在键盘旁边,然后感到圣灵充满无往不胜,所以我打算以后每次参赛都把圣经拿去,作为我的……吉祥物。

Comments (19)

08年5月11日至12日

这段时间不知道天天在瞎忙什么,blog变得像周记一样……

推荐一些这段时间看的极好的书:《剑桥插图音乐指南》《中国文学欣赏举隅》《中国历代政治得失》《沉思录》,还有《你的灯亮着吗》《像自由一样美丽》也不错。冲动消费比较多,一冲动就在amazon.cn上买了Avril的所有CD和DVD,还有去年全年的《爱乐》……在图书馆借了两卷本厚厚的《音乐圣经》。新了解到的挺喜欢的乐手是JS与自来卷,开始逐渐接受陈绮贞的风格。

看到的帮忙测试一下www.mozartproject.org是不是被GFW了,这可能是关于Mozart的生平、曲目等最全面的资料网站了。哎,伟大的某党,宁可错杀一千……是啊,我总是需要翻墙,但是我翻墙真的不是需要做什么Big Brother不希望的事情啊!我只是看看中文维基百科(也不会看那些Big Brother不喜欢的词条),查查mozartproject,也有可能看看Flickr,写写Tumblr、My Opera,可是为什么这些都要受到限制呢?跟SoariEz讨论这些事情,他说:“想翻墙,背TOEFL、GRE去吧……”一语点醒梦中人啊,什么freegate、SSH Tunnel,还不是凿壁偷光式的小打小闹,想一劳永逸地无视那道伟大的墙,真正的翻出墙外才是解决之道吧。

最后高兴地发今天新手赛的rank list,嗯,按照原定计划本学期不去参加这系列比赛了。

Rank Handle        Solved  A      B      C       D E      F      Penalty
1    dd_engi       4       34(1)  8      60(5)   0 119(1) 13(1)  306
2    hsys          4       80(1)  0      85(4)   0 162(4) 21(1)  468
3    hazy          3       42(1)  0      0       0 117(1) 20(1)  179
4    Ouyang_Jialin 3       35(1)  8      121(3)  0 0      17(1)  213
5    asmn          3       17(2)  100(4) 1       0 1      35(1)  232
6    ljzhao        3       62(1)  0      0       0 164(3) 23(1)  289
7    yuzhirenzhe   3       59(4)  0      13      0 178(4) 24(1)  381
8    classT        3       117(1) 0      159(7)  0 0      24(2)  440
9    vivyli        3       70(3)  0      163(12) 0 1      21(1)  514
10   navj          2       30(2)  6      3       0 0      10(1)  60
11   moondy        2       32(1)  4      0       0 0      42(1)  74
12   relive        2       59(1)  0      1       0 0      26(1)  85
13   milki         2       58(1)  0      0       0 2      29(1)  87
14   retadykay     2       49(1)  0      0       0 3      70(1)  119
15   wanwei        2       115(1) 0      0       0 1      71(5)  266
16   owen200402    2       154(5) 0      0       0 0      116(3) 390
17   aaahexing     1       0      0      0       0 0      15(1)  15
18   EZdestroyer   1       0      4      4       0 3      19(1)  19
19   liu3063031168 1       0      0      0       0 3      20(1)  20
20   rpggpr        1       5      1      0       0 0      20(1)  20
21   wyest         1       1      0      0       0 0      40(1)  40
22   pkwgl         1       1      2      0       0 8      63(1)  63
23   hzqtc         1       1      0      0       0 3      53(2)  73
24   gaohaidong    1       0      1      0       0 0      88(1)  88
25   jay23jack     1       8      1      1       0 0      35(4)  95
26   winsty        1       2      0      0       0 0      84(7)  204

后知后觉地开始使用Google Reader,惊奇地发现上面显示的我的feed的订阅数竟然是70+,而且最近似乎每天都有增长!有点不敢相信有会这么多人在关注我,嗯,以后得注意文章质量了,欢迎一些希望看到哪方面内容的建议。

明天回家,高考体检。啊……很久以后想到要再见到某人还有点紧张的说。

Comments (5)

2008年5月5日,凌晨

五一改短假了,但浙大有七天的“春假”,从上周一到周日,多么充实而颓废的七天啊!

拿到了新的手机,Nokia 5700 XpressMusic,非常喜欢。看重音乐功能、喜欢S60智能机、预算在两千以内,应该是满足这些条件的最佳选择了。用手机的标准来衡量,音质非常棒。照相功能比较弱,2M的镜头很烂,严重偏红,不过我对这方面的要求倒也不高。另外,“扭腰”的设计应该让所有第一次见到的人感到惊艳。完全不轻薄,这应该是目前S60智能机的共同缺点吧(SoariEz同学的超级水货E51不算的话……)。不过,最近读TAOUP,对操作系统的设计自然敏感一些,就觉得S60这目前最主流的手机操作系统令人不满的地方还是比较多。不知道BSD内核的iPhone怎么样?实在烧钱的说……我将来再买手机一定要选Unix类内核的操作系统,话说随着目前iPhone和将来Android的强势,未来Unix全面占据手机操作系统市场的可能性还是相当大的嘛,虽然目前而言Symbian仍是不二选择。

头三天,艳阳高照,陪妈妈姥姥和姥爷仔细地游览了灵隐寺、植物园、西湖几个景区。感想是……要门票的景色的确胜于免费的,飞来峰、三潭印月很赞。5700拍照就是方便快捷,随随便便就拍了好几百张……不过照的都是风景,加上摄影技术实在低能,就不发出来献丑了。遗憾是时间关系没去成白堤上传说中一百六十年历史的楼外楼……

接下来的几天时间,除了写写马上要交的作业以外,就是在音乐和书籍中度过了。哦……好吧还有大量的上网闲逛。消耗前一段时间下载的无数音乐,以及继续更多地疯狂下载。Strauss、王若琳、Avril、Linkin Park、Tschaikovsky(疯狂喜欢啊),加上李志、陈绮贞、苏打绿、牛奶@咖啡(新了解到的,还好吧)是这几天的主旋律。极赞Ein Straussfest、Start From Here、Live in Roxy Theater、Meteora以及Piano Concerto No.1 in B flat Minor, Op.23, I – Allegro non troppo。话说名字里面带琳字的女生我都喜欢,像陈慧琳啊关之琳啊蔡依琳啊范佳琳啊林琳啊,现在又多了一个王若琳。买了社会契约论、中国历代政治得失、沉思录等一些书,不过还没开始好好看,TAOUP的进度倒是不慢。

发一张前几天的书架照供亲爱的fans们瞻仰,这几天新买的书当时还没有放上去,从中您可以看出我的阅读是多么驳杂,以及5700XM的镜头,呃,或者我的拍照技术有多么烂。

最后,今天又新手上路的说。照例发ranklist:

Rank Nickname Solved A B C D E F Penalty
1 Stone Cold 3 0 62(1) 0 0 176(5) 16(1) 334
2 DD 3 0 31(1) 0 0 166(6) 39(1) 336
3 冰之魄 3 0 172(9) 0 0 136(5) 38(1) 586
4 asmn 2 1 90(1) 0 0 0 24(1) 114
5 Aaron 2 0 78(2) 0 0 2 34(2) 152
6 winsty 2 0 120(2) 0 0 0 25(1) 165
7 ll861112 2 0 0 0 0 101(4) 22(1) 183
8 relive 2 0 0 0 0 125(6) 30(2) 275
9 gao 2 0 165(4) 0 0 0 97(2) 342
10 EZ 2 0 176(12) 0 0 0 76(4) 532
11 cscser 2 0 168(14) 0 0 0 114(4) 602
12 vivy 2 0 133(18) 0 0 9 44(8) 657
13 hazy 1 0 23 0 0 0 17(1) 17
14 classT 1 0 5 0 0 7 21(1) 21
15 moondy 1 0 0 0 0 9 21(1) 21
16 wanwei 1 0 5 0 0 0 36(1) 36
17 owen_water 1 0 2 0 0 0 43(1) 43
18 Navi 1 1 0 0 0 11 44(1) 44
19 jack 1 2 3 0 0 2 55(1) 55
20 XO 1 0 3 0 0 5 46(2) 66
21 loulou 1 0 14 0 0 0 29(3) 69
22 cai 1 0 19 0 0 1 43(5) 123
23 小强 1 0 140(3) 0 0 0 8 180
24 听雨轩士 1 0 3 0 0 0 142(8) 282
25 555 1 0 1 0 0 3 150(10) 330
26 我是小白, 大牛轻踩 0 0 7 4 0 0 2 0
27 milki 0 0 0 0 0 0 2 0

5555~~又是由于罚时过多rank1被抢了……重大遗憾是AC三道以后自以为无人能敌,就发起呆来,最后五分钟奇迹般想到D的思路以后大势已去……

打算下次比完以后就不再参加最后两场新手赛了,把积分留给别人,展示高风亮节以及积攒RP。连续两次因罚时的rank 1被抢了,11日是最后的一战,我要rank 1!

Comments (8)

紫金港->玉泉->苏堤->中国美院->家乐福->华家池->紫金港

今天和亲爱的SoariEz同学一起骑车穿越了半个杭州……

九点半从紫金港出发,骑到玉泉借两本书,从苏堤穿越整个西湖。(苏堤风景太美了!比白堤更胜一筹。)

十二点半到达中国美院(中国美院在杭州,我认为很合适的说),在美院食堂吃的饭,觉得比浙大好吃。强烈推荐游西湖时到美院里去吃饭,又便宜又好吃,而且美院内的所有建筑及设施都给人一种艺术品的感觉,是我目前看到的最漂亮的校园(以前我的答案一直是浙大来着)。

吃完饭后,按照原定计划,去家乐福购物。其实真没必要去那么远的家乐福,学校附近也有大型超市的。我去家乐福购物的目的,就是表明我对那些缺乏理智和判断力的抵制家乐福的愤青们的不屑,以及与他们的不同。不过,在我第一次进了家乐福以后,以后我可能真的不会再去了,因为我想买的东西——巧克力和糖果之类——家乐福里的种类和口味都很不全,比我上次去的沃尔玛差远了,而且有些服务人员的态度不太好。有人告诉我杭州什么地方的大型超市比较好吗?

这时大约是下午三点,还打算去华家池的图书馆借一本书。很不幸地,由于错过了一个路口,绕了不少远路。翻阅万水千山终于赶到华家池图书馆以后,楼上贴着的小小一张白纸让我陷入无尽的绝望,上书:19日、20日闭馆,详见!@#$%……

四点钟出了华家池,想起晚上四点钟的新手赛,骑车狂奔一个半小时赶回紫金港。终于停下以后,有种双腿已经完全不属于自己了的感觉……

随便吃了点饭,浑浑噩噩地提前三分钟到达机房,觉得自己的雄心壮志大概要泡汤了。结果嘛……看 rank list:

Rank Handle Solved A B C D E F Penalty
1 moondy 6 8(1) 39(1) 28(2) 57(2) 118(2) 90(1) 400
2 asmn 6 12(1) 36(1) 25(1) 47(1) 160(7) 81(2) 501
3 dd_engi 6 23(1) 61(1) 71(3) 33(1) 113(4) 81(3) 522
4 EZdestroyer 6 16(1) 33(1) 51(2) 60(1) 154(1) 126(6) 560
5 Ouyang_Jialin 5 5(1) 30(1) 20(1) 39(1) 8 56(1) 150
6 navj 5 3(1) 18(1) 41(1) 71(1) 11 105(2) 258
7 liu3063031168 5 13(2) 27(1) 50(1) 84(3) 0 172(1) 406
8 rpggpr 5 18(1) 32(1) 47(2) 171(1) 2 140(2) 448
9 relive 4 7(1) 44(1) 28(1) 68(1) 0 2 147
10 hazy 4 12(1) 49(1) 33(1) 72(2) 0 3 186
11 classT 4 4(1) 29(1) 20(3) 72(4) 0 8 225
12 jay23jack 4 48(1) 47(1) 48(1) 69(2) 2 1 232
13 yuzhirenzhe 4 21(3) 34(1) 46(1) 70(3) 4 8 251
14 aaahexing 4 27(1) 60(1) 39(1) 103(5) 0 4 309
15 winsty 4 19(1) 45(4) 64(2) 87(2) 0 4 315
16 vivyli 4 10(2) 46(1) 89(1) 154(15) 0 3 599
17 milki 3 13(1) 28(1) 62(1) 11 2 2 103
18 owen200402 3 19(1) 43(1) 90(3) 0 0 2 192
19 hsys 3 26(1) 19(1) 4 155(1) 0 3 200
20 aaron35203432 3 8(1) 7 41(3) 117(2) 0 0 226
21 wanwei 3 11(1) 100(7) 2 32(2) 0 0 283
22 gaohaidong 3 20(2) 52(1) 4 147(6) 0 0 339
23 pp85365640 3 136(5) 71(1) 122(4) 2 0 0 469
24 retadykay 2 14(2) 39(2) 2 0 0 3 93
25 pkwgl 2 36(3) 53(1) 1 7 0 0 129
26 wyest 2 13(1) 144(3) 0 5 0 2 197
27 ljzhao 1 17(2) 2 2 0 0 0 37

今天题相对较简单,竟然6题全AC了!生活真美好啊。不过真是可惜,我明明是第一个AC 6题的……随便交的策略导致了太多的罚时。继续努力啊!

Comments (1)

20080406比赛总结,及其它

中间电脑坏了耽误很多时间,做了一会儿肚子饿了又跑去吃饭了,一共只有大约一半的时间在做题,然后AC了2/6题。没什么不满意的,但显然应该能做到更好。通过这次比赛也了解了一点其它人的水平,呵呵。

个人赛的确很不爽,看题不仔细的弱点让我很吃亏。A一开始没看到头尾字母的条件,花了过多的时间。B这种蘑菇题本来就不是我可写的。交C的时候电脑坏了,本来可以一次AC的。D到最后时想到了双向搜索,不过由于肚子饿了就放弃了。E看到了超大的数据范围却没看到对结果的大小有限制的条件,以为不能用朴素的递推来写就没碰。F属于太久没看网络流相关的东西了,朴素的最小割都没看出来。

应该花更多时间来看题,保证看清楚了没有漏掉条件,不要把题想难了。这次在没有全力去做的情况下Rank11Rank7(不含Staff成员)、题数第二梯队,下次要争取做到题数最多,Rank1也绝非不可能的事情。

最近在做Python Challenge,太有趣了,昨晚做到一点多过了六关,推荐给所有想学Python的同学。

下周去乌镇玩,届时肯定会发大量照片。人生美好,提升效率,就这样。


For Beginners I
Length: 3:0:0
Time Escaped: 3:0:0
Rank Handle        Solved A       B      C      D      E       F  Penalty
1    ll861112      3      37(1)   0      18(1)  170(4) 0       11 285
2    navj          3      28(8)   0      67(2)  3      147(11) 0  602
3    Ouyang_Jialin 2      33(1)   0      46(1)  1      10      0  79
4    hazy          2      98(1)   2      111(1) 0      0       1  209
5    yuzhirenzhe   2      77(1)   145(1) 1      2      0       0  222
6    Jiangch       2      99(3)   0      108(5) 0      0       0  327
7    dd_engi       2      136(6)  0      84(4)  0      0       0  380
8    EZdestroyer   2      12      0      107(5) 1      159(8)  0  486
9    ljzhao        1      30(2)   0      8      0      0       0  50
10   owen200402    1      0       0      77(1)  0      0       0  77
11   retadykay     1      58(2)   0      4      0      0       0  78
12   rpggpr        1      5       0      2      0      52(5)   0  132
13   milki         1      4       117(2) 4      0      0       0  137
14   hsys          1      97(11)  0      6      0      0       0  297
15   classT        1      117(10) 0      4      0      0       0  297
16   moondy        1      99(11)  0      0      0      6       0  299
17   pkwgl         1      140(9)  0      4      0      0       0  300
18   jay23jack     1      176(12) 0      6      0      0       0  396
19   wanwei        0      9       0      2      0      0       0  0
19   relive        0      2       0      7      0      0       0  0
19   gaohaidong    0      5       0      2      0      0       0  0
19   vivyli        0      11      0      0      0      8       0  0
19   liu3063031168 0      11      0      0      0      5       0  0
19   wyest         0      1       0      3      0      0       0  0
19   pp85365640    0      3       0      0      0      1       0  0
19   aaahexing     0      20      0      0      0      0       0  0
19   aaron35203432 0      7       0      1      0      0       0  0 

Comments (4)

08校赛照片

早上没吃饭……幸亏有ww MM带的面包……

似乎表情很萧瑟,手里拿着面包就有点不伦不类。

Fire灿哥亲切交谈……

第一个气球!

第二个气球……

四个气球了!

最后合影……不知道为什么多了一个人。。。

Comments (25)