区域赛总结-哈尔滨2008
3 评论16次阅读2008.10.21 9:10; 作者:Felicia
一只猫眼中的区域赛
1
我们今年的指导思想是学习alpc,练习Final风格的题目,我们队偏重代码题和几何题。按照这个直到思想,在第一场区域赛之前,我们做了50场以上的正规模拟训练,可以说准备的非常充分了。去哈尔滨之前的最后几天,实话说我们没有好好训练了。最后一次比赛做的是Final 2007,中途遇到一堆事情,以至于我们只做了一题后gg。之后两天就没有做任何系统训练了,只是打打标程,买点东西,顺便照顾一下奖学金的事情。
2
去哈尔滨需要经过漫长的火车旅程。我闲得无聊,主要时间用于看一本yy小说,玩魔方,以及看看洛克带来的Game Theory论文。惊奇的发现我的手机能漫游,于是给Ader发短信……
3
10月9号下午我们抵达哈尔滨,天气不如想象中的冷。休息一晚后,第二天是注册。志愿者MM欺负我,给我M号的衣服。10号当天我们过的很闲适,早来一天真好。我忽然对Game Theory产生兴趣,向洛克讨了论文看,发现这个比具体数学简单多了。10号晚,和洛克一起去哈工程图书馆上网,等了很久等到位置,先把mmd交代的java读入和读文件资料查好,然后把下午想出做法的A Funny Stone Game(北京2006赛题)在uva上交过了。期间遇到Bamboo大牛,景仰了一番。
4
11号早上开幕式。完毕后抽签。董core的rp比较好,抽到了奖品。我执行我的rp下溢计划,抽到了个垃圾位置,并且没有中奖。
下午是练习赛。因为位置垃圾,看不到大屏幕提示,只能本机刷rank。这次用的Open Solaris不怎么样,开GVIM/xterm巨慢,导致我们平常用的GVIM/xterm根本无法使用。SUN的工程师来调试了一会儿也没有解决。我们只好用Net Beans来搞了。幸亏Net Beans用起来还不错。
晚上很早就睡了。
5
早饭我吃了米饭,饭后喝了红牛,貌似我每次喝这个都爆rp,希望这次也会吧。
正式比赛开始前看到ECNU的队,恰逢洛克去上厕所,他回来后我想了想没敢跟他说。然后我提醒自己一定不要写第一个题,多看题,发挥我的优势。
比赛开始前mmd利用时间敲了vimrc和配置环境。我在纸上写题目State和注意事项:不要想一个题太久,写一个题之前至少有两个人知道算法等。
比赛开始后mmd看H,洛克看C,我看J。mmd觉得H是个图搜索可做,我觉得J是个几何+DP可做,洛克看了一会儿貌似没看懂题意,给我和mmd说了一次错误的题意。讨论了一下觉得mmd可以去做H,就让他上去写了。
过了一会儿洛克把C看明白了,跟我说了正确题意和一个求最短路后匹配的思想。因为mmd在机上,就没跟他说。此时我看了一下mmd的进展,发现他只写了个读入,感觉有点不妙。我稍微看了一下A。
在21-25分钟的时候我看了一下rank,发现有四个队过了I,包括SLASH。我赶紧看I,立刻发现是简单题。我们以前个人赛做过的,我还记得我和yama讲过做法。于是我就和洛克讨论了一下,说了一个n^2logn的算法,洛克很快写了。此时pc^2出现问题,我们无法提交,只得找来staff,据其说是要重启pc^2,重启后又交了一次,发现不见了,只好又重启又交……然后诡异的发现上次交的run又在了。此时洛克和mmd都比较郁闷。接下去judge迟迟不给我们返回结果,让我们提心吊胆。洛克写I的时候,我和mmd讲了C的题意,还没讲洛克的算法,mmd就想了一个最小费用流,不需要改变题目中的图就能做。我觉得非常优美,就说可以做。当时我们根本没考虑时效问题。然后mmd就去敲费用流了。66分钟的时候我去上厕所,回来看见SLASH挂了两个气球了,我们还是0题,我想了想没敢跟他俩说。之后我继续看题,想了一会儿J,又看了看A。mmd对于judge的问题非常生气,屡次叫来staff,并跟staff吵了起来。
洛克此时读了D,发现是裸的高斯消元,但是要高精度。我把A看完后推好了式子给洛克讲,可以二分,但是可能会超一点long long,要高精度。我们只有mmd会java,目前mmd又在写C,我当时说了一句mmd压力会不会太大了……然后我想了一下说A题可以不用高精,打表就行了。洛克有点怀疑,我说我确定可以。mmd写完C后下来看代码并画样例,洛克上去写A。他写的很快,一会儿就写好了,过样例后打印代码下来看。mmd那时一直情绪不好,跟staff吵着要判我们的I,staff说正在判A,要我们耐心等。正吵着的时候我们的I过了。mmd上去调试C,过样例后交了个TLE。洛克仔细看完代码改了一下二分的时候可能超int的地方,把A交过了。
洛克写A的时候我看了F,发现不难。洛克写完A后我跟他讲了F的模型,他直接说以前做过类似的比这个更难的题,然后就写dp方程,写完之后问我看懂没。我看了一下,没仔细想是不是对的,只是感觉可以。洛克很自信的去写了F,很快过了。
此时我和mmd意识到C的时效问题。我和mmd讨论,mmd说他的费用流很快,如果是费用流的题不可能超时。我想起我还没跟他说洛克想的最短路的思想,赶紧说了。mmd又思考了正确的做法,上去写KM。
洛克写F的时候我看了一下题目State,发现只有B和G没有看,就把G看了。G的题意非常晦涩,我看了很久,并手画了两个样例才弄懂他要说啥。(顺便说一下,这个出题的英语写的很奇怪,比如J题的凸多边形的表述方法跟平常不一样,把IronGods囧住了)洛克过F之后我跟他说G的题意,然后他说了一个DP方法,我感觉不对,然后想了一个记忆化搜索,两个人感觉都很优美。于是洛克上去秒之。一次通过。在洛克写G之前mmd的C题wa了一次,洛克写G的时候mmd打印代码看出一个SB错误,在洛克写完的时候mmd也把C的错误修正且交过了。此时还有大概2小时,我们刷rank,IronGods6题,我们5题排第二,感觉真的很有希望啊。不过后面的4题队伍有罚时很少的。
目前形势应该是6题金牌,因为G题估计会有一些队过掉,D题也是。B题那时候过的非常少。我们三个人讨论了一下之后决定我准备D(mmd和洛克均称不会高斯消元),mmd写H,D的优先级高,一旦我准备好mmd立刻下来让我。一会儿我认为自己想好了,把mmd赶下来,我上去写D。这个时候洛克看了B,但是不知道怎么做。我写着写着发现我不熟悉java,Net Beans里头全是编译错误提示的红线。我很囧的说,我貌似一个人搞不定D啊。这下mmd和洛克也囧了,于是三个人一起搞D。我写了大概30分钟左右吧,终于写好了草稿,mmd上来改掉编译错误,并写好了分数类。调过样例后打印代码看完交之。此时是235分钟。很不幸的D返回了wa。于是三个人看代码想trick。洛克看了题目之后想到可能是我把整数按照分数输出了,一看果然如此。赶紧改掉,交之。此时是258分钟。等了很久不幸又返回wa。这样弄的我们都很着急,拼命想trick,在机上乱测数据,都没发现错误。我去翻SJTU标程,发现他的实现方法跟我不一样。洛克把我摁到椅子上要我去测数据,我说我不知道测啥,他说他测,上去后他也不知道测啥……我想了很久之后终于想到可能是我输出的时候顺序弄错了……囧。我立刻改掉,感觉这下肯定对了,还没测样例,就说这下对了,交不?洛克说交,mmd第n次上厕所回来跟着说交,我就交了。之后立马后悔,因为一测样例发现漏输出回车……白白浪费20+的罚时……加了回车之后又交,过了。
此时是285分钟。因为后两小时我们3个人都在搞D,没有管其他题,现在已经没时间开题了。于是3个人吃香蕉,喝水,聊天,看后面的一家老小向前冲在那囧。送D的蓝色气球的MM说,我们排名前5,感觉比较happy。
就这样happy到比赛结束:)
6
颁奖前董老师说ZJU申诉后排到我们前面,罚时比我们少十几分钟,很是为那次SB提交后悔。后来看了rank才发现是董老师看错了。
颁奖的时候得知HUST_STI和SLASH分列银牌前2,被雷到了。当然更雷的是,What’s up以微弱优势排在了IronGods前面……Bamboo一脸囧相去领奖。
7
比赛情况分析:
我们前期因为judge和board的问题郁闷了很久,但是调整过来后仍然能在中期快速过题追上其他队,这不能不说我们得益于暑假艰苦的50+场训练。
后期的D题和B题暴露出我们的问题:数学能力不足。数学本来是我负责的部分,但是我本身数学能力不是太好,想的也不快。我训练的时候做的数学题也不够。这导致了我们队数学能力欠缺。还有我的java写的不好,需要mmd帮忙,浪费了他的时间。如果我能独自1Y那个D题,我们的境况就会好很多……
比赛的题目没有几何题(只有个J有点用到几何),我们的强项没有发挥出来。在没有遇到强项题的情况下,能做到这个成绩,我认为很不错了。
8
对今后训练的建议:
多加强数学方面的训练,把中等和简单的数学题搞定,尤其是我。
继续以前的光荣传统,保持每星期4场以上的模拟训练题量。
适当注意一下java。
保持计算几何的优势。

michael | 1F
十月 21st, 2008 at 14:12
mmd和洛克均称不会高斯消元
….
貌似你被欺负了…
Louty | 2F
十月 30th, 2008 at 18:35
很郁闷地想知道我们的D结果是什么。。。。。。我大概还剩4-5分钟的时候才交的,哈工程就不给我们返回答案了。
Felicia | 3F
十一月 1st, 2008 at 22:42
他们说是最后5分钟不判题,等比赛结束再一起判的……这个估计只有去问哈工程的人了