Skip to content

Tag Archives: ACM-ICPC

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方面的书目。最近一本《数学分析原理》让我多少发现了纯数学的美感,虽然这学期应该不大可能了,但以后还是要读些纯数学的经典教材的。物理是这学期多少令人头疼的科目,得抓紧看一下,希望能培养出兴趣。 好吧,读书去了。

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加油!

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 […]

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新手上路。。。- – ~~~~~~~~跑题完毕的分割线~~~~~~~~ 总结一下已知的缺点和解决方案: 思维广度不够。一些完全在能力范围内的题目,不知为何当时就是想不到。解决方案:似乎只能多做题多思考吧,切ZOJ2.0上的题目。 对STL不熟悉,导致每次用到几乎都要查文档。解决方案:抽空把文档看一遍,多用。 数学功底不够,尤其是组合数学很需要加强。解决方案:再细读一遍《组合数学》。 计算几何和数论根本不会。解决方案:不会就学呗。计算几何看lrj的书好了,手头还有一本清华社的《计算几何——算法与应用》;数论还不知道该看啥。 某些算法(比如说网络流)的实现,特别是应用,遗忘得太多了,要重新拾起来。解决方案:仔细重读一遍Weiss的书以及CLRS好了,这次读英文版的,注意习题。(或者读别的算法书?) 看题不仔细。解决方案:比赛时别太匆忙,多花点时间仔细看题利大于弊的。 体力和意志力不行,每次比赛都坚持不到最后就不写了。解决方案:还不知道。找人组队可以很大程度上弥补体力的不足。但如何培养“不到最后一刻决不放弃”的意志力呢? 当然啦,上面光说缺点了,其实我的优点更多,比如说代码写得快、算法会得多……还有其他好多好多啦都说不完的。但是我这个人这么谦虚,是绝对不会对别人炫耀甚至提起自己的优点的。我一直都是那样的自省、内敛与深沉……(以下省略二千字- -) 感言: 感谢 Channel [V]、MTV……哦,不好意思拿错稿了掐了别播啊。 不到半年的ACM/ICPC经历,让我懂得的最重要的事情,是团队合作。我知道了,ACM不是单打独斗,个人能力很重要,但良好的团队合作更重要!(本段做字正腔圆感情充沛状,末尾语调上扬,眼神坚定。) 需要做的事情还有很多,很多东西还要学习,不仅是知识方面,也包括“如何平衡ACM与其它各种事情的关系”之类命题。但是快期末考试啦,除了考虑出题以外,考完之前就不安排ACM方面的计划啦,考试完了就该暑期集训啦。 所以,千言万语,赶紧汇成一句话:期待暑期集训的精彩吧! 梦想: 我要登上 ACM/ICPC World Final 的领奖台。 附:[转载] For […]

省赛总结

坐了一夜火车,在昨天上午十点多赶到紫金港校区,浙江省程序设计竞赛十二点即开始,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的那次就放了一本圣经放在键盘旁边,然后感到圣灵充满无往不胜,所以我打算以后每次参赛都把圣经拿去,作为我的……吉祥物。