ICPC Rank      School      Name Solved Time     A         B         C         D         E         F         G         H         I         J     Total att/solv
* 上海交通大学 Luminer(team43) 10 1208 1/243 1/26 1/211 1/164 2/50 2/103 1/121 3/68 1/125 1/17 14/10
* 上海交通大学 Rivercrab(team100) 10 1344 5/233 3/107 1/189 2/76 4/86 2/130 1/128 1/11 2/120 1/24 22/10
1 上海交通大学 Phosphor(team82) 10 1659 4/299 1/84 1/262 1/172 2/65 1/180 3/216 1/38 3/114 2/49 19/10
2 清华大学 machinator(team94) 9 1567 0/– 4/257 1/287 1/234 1/84 2/197 1/175 2/54 2/135 1/24 15/9
3 浙江大学 ArcOfDream(team28) 9 1686 0/– 1/287 2/208 2/273 7/222 1/74 2/139 1/27 2/195 2/41 20/9
4 山东大学 Code_Geass(team114) 8 1031 0/– 1/123 1/106 1/– 1/15 2/175 2/189 1/54 3/253 1/36 13/8
5 清华大学 T.B.O.G(team69) 8 1036 7/– 1/65 3/– 1/213 2/116 4/165 1/92 2/37 3/159 1/49 25/8
5 哈尔滨工业大学 DPS(team39) 8 1196 5/– 1/98 0/– 2/189 4/84 2/174 1/118 3/69 3/244 2/20 23/8
6 中山大学 SYSU_Vermouth(team52) 8 1312 0/– 2/120 2/257 0/– 6/153 1/113 1/182 3/73 1/203 1/31 17/8
7 华东师范大学 ecnu_Puzzle(team73) 8 1457 0/– 1/264 2/282 1/167 3/191 1/159 1/211 2/57 0/– 2/26 13/8

赛前准备

今年我们队最初的Regional计划是到成都热身——在福州出线——去东京锻炼,只不过最后因为某些原因成都换成了杭州,又因为撞船事件东京变成了河内。福州赛区无疑是我们最重要的一场Regional比赛,很遗憾的是,作为我们最重要的一场比赛,却因为考试、作业、Project和实验室任务等各种事情没能充分的准备。首先要感谢LCLL和frozen,如果没有他们的帮忙,我们甚至可能连在比赛前两周里训练一场的时间都没有。

我们忙里偷闲训练的几场,训练的成绩还算满意,但也暴露出一个问题——慢热。我们前半程过题的速度非常慢,训练的这几场,都是有好几道简单题的比赛,可是我们却卡在上面,有时候三人各卡一题,甚至Resolution都4题了我们才1题。不过因为最后成绩还可以,我们对此并没有太在意,可能认为只是训练时不够集中罢了,谁知到了福州我们梦游了半场比赛……

出发的前一天,我们队三只还在218匆忙准备越南用的模块(越南对带进场的模块和World Finals的限制差不多),一直到凌晨才搞好。此后的九天,我们队的状态都可以用一个字来形容——困。

初到福大

ArcOfDream + Resolution在hhanger的带领下,一行7人乘D3201出发前往福州。记得免研面试的时候,老师用英语问我,福建通动车了,我有什么感想,我只能回答“表示对生活影响不大”。动车确实很快,D3201全程只要7h+,而2249却要25h+,可是我只能乘时速50km的2249回家,还要转汽车。真希望家里早日通铁路,如果这样的话,到福州还能抽空回家一趟。

我们所住的梅峰宾馆无论离南站还是福大都很远。福大的给每个学校安排了一个mm志愿者,这实在是太赞了,希望以后的承办学校都能引以为榜样 :D 福大的食堂灰常灰常实惠,这么多年到处跑吃过n个食堂之后,福大食堂的实惠还是让我们相当orz。给力的食堂加上麦当劳、澳门街和小肥羊,在福州我们每顿都吃得相当饱。

试机赛居然有5道题,结果我D还想错方法了,被moondy点出正确算法后惭愧到死。C我觉得虽然烦点,不是太难,不过欧阳和moondy还是让我别写。judge不但没有-O2,还不返回RE,这还是有点郁闷的(越南也是这样)。

开局混乱

比赛一开始,老样子欧阳负责登录,moondy看前三题,我先看了D,没什么想法,又看了E,一看是费马点,很熟悉,就让欧阳写。查了一下quadrangle的意思是四方院子/square,就以为是正方形,看了sample也都是正方形,于是费马点就是中心。欧阳写完提交,结果CE,发现语言选了GNU C,改成C++再交,结果WA了。于是估计quadrangle是指普通的四边形,于是我们选择了先放着,继续看题。

看到场上有队伍过了H后,moondy给我讲了题意,我给moondy分析了算法后,moondy上去敲,H1y(27)。然后欧阳写J,在WA了一次后moondy看代码找出了一个脑残错误,改过之后J2y(41)。不久模拟煺火版的E也敲好了,提交后还是WA,这时候就有点摸不着头脑了。

读题的时候就发现F题居然是背景和算法都和一个星期前ZOJ Monthly的D题(ZOJ3430)一模一样的题,我还写了解题报告。不过当时认为这不是开场该写的题,可是现在这种情况,只好让moondy上去敲好AC自动机模板,然后我写main函数,还算顺利,F1y(74)

中段梦游

随后是我参加比赛以来,最为郁闷的两小时。首先是看到已经有无数的队伍通过了E题,包括Resolution的1y,这说明如果需要模拟煺火,模板应该是没问题的。可是我们各种尝试了多次,始终是WA,其中接近AC的一次TLE了。我们考虑了题意,考虑了手抖敲错东西,甚至考虑了sqrt的精度,可都没有结果。我当时就想到了考虑费马点应该是对角线交点或4个顶点,但觉得一这没有比模拟煺火好在哪里,二心里也开始虚了,不想浪费时间验证。我们也只能在WA了无数次E后告诉自己和队友,先放着先放着。

如果只是E,我想我们跳出泥潭,转而先考虑更有前途的几题应该不是问题。可悲剧的是,当时另一道过得非常之多的题是B。B题一开始moondy还把题目中的最小看成了最大,我重新读题后才发现,我们只看到模板里两两点对间最大流的算法,也知道结果其实与S无关,但我们并不会全局最小割。如果只是几个队过这道题也就罢了,浙大的队伍已经对前面的队伍都过但自己不会做的题目习以为常了。不过通过这题的队伍非常多,而我们三个人居然都毫无头绪,说实话,真是自信心受挫。

这时候其它题都没有人过,我当时甚至以为其它题都很难。这时候我们也遇到了前所未有的情况,比赛刚刚开始,我们的机器居然闲了下来。这是一个危险的信号,无奈,只能让欧阳上去敲C题这个本该放到后面写的计算几何。

时间一分一秒的流逝,而我和moondy依然纠结在B和E中。虽然也说看看其它题,但不知怎么的居然完全没有思路。我基本上可以说就是对着题目发呆而已,完全没有进展。B题只是yy了一些复杂而没有保证的想法,中间还调了几次E。

这时候moondy发现G题过了不少队伍,重新回头看G才发现这是道如此naive的题,可是负责看这道题的我却只是随便看看就跳过了……moondy马上去写G,可惜有个naive的bug结果WA了一次,之后G2y(139)。这是我们在比赛中段唯一的一个AC。比赛过去3小时的时候,我们只有4题。

后程发力

欧阳的C写了很久,而此时的我们已经掉到了board的很后面,如果就这样比赛结束的话,就真没脸回杭州了。I题欧阳同我讲过题意和正确的思路,事实上我自己就在去年的ZOJ Monthly出过一道更为复杂的题(ZOJ3227 Perfect Cherry Blossom)并写过解题报告。没有及时写这一道题也是我的失误,于是我彻底扔掉B和E,开始推I。I的代码并没有写多久,通过sample和几个自己造的数据后却WA了,于是打印检查。欧阳继续写C,而我给moondy讲I的代码。

I看了好久,找不到错误在那里,然后很不幸的是欧阳的C也WA了,题数远远落后再卡两题,着实郁闷。突然,我发现了I的纱布错误,我把dp = min(a, b)写成了dp = a, dp = b,我不知道当时我的脑子有什么问题,犯下了这么纱布的错误还查了这么久,改过之后I2y(195)。洗手间回来的时候我和队友开玩笑的说,我们把后一半题AK了,被前一半题AK了。

然后moondy帮欧阳对C题的模板,我则让欧阳给我讲他的main函数。讲的过程中发现坐标变换一处脑残错误,最后没有发现别的问题,提交后C2y(208)。这时候我们是6题最后一名。

把卡着的题搞定后,又要重新面对B和E了,moondy在想B,而我决定试试之前对E的想法,让欧阳先敲需要的几何模板。虽然我的想法是对的,但我构造的几组数据,模拟煺火也没有问题,不过我还是提交了,这样悲剧了近整场比赛的E题终于在封board前E7y(222)。毫无疑问又是7题的最后一名。

最后moondy对于B也只有不靠谱的算法,于是考虑水水B题,moondy上去敲Dinic的模块。而我开始想过了比较多的D题。我放弃了高斯消元法出发的思路,转而开始考虑区间运算。我从最特殊的情况开始,慢慢推出了比较一般的情况,最后终于想到了正确的算法。于是我上机写D,写得还算顺利,简单调试后通过sample,测了一两组数据没问题,提交却WA。于是我写暴力程序对拍,对于很强的情况都没有问题,于是只可能是边界问题或脑残错误了,果然,欧阳指出我答案忘记取模了>_<,改过提交D2y(273)

最后的时间显然来不及考虑A题了,全力攻B。欧阳想了一个比较靠谱的水法,和我之前的某个想法也比较接近。moondy敲完程序过sample后就提交了。我让moondy改参数继续交,准备同WA和TLE做斗争了。而欧阳让moondy打出一些中间值,以确保程序没错。正在moondy修改程序的时候,judge返回了一个yes,B1y(287)。只听到后面传来hhanger很大一声“ym”,不过后来才知道欧阳和moondy都没有注意到= =b

在比赛的最后两个小时里,我们连y五道题,最后总算爬到了rank第五,icpc排名第三。

比赛小结

整场比赛可谓有惊无险,中间梦游的两小时,卡B和E,居然“无题可做”,确实是从未遇到过的困难。好在最后两小时跳出坑来,就结果而言,算是保住了出线这个底线。再回想比赛的过程,死在B和E上无疑是本场比赛的败笔,事实上我们可以更早的去想G、I和D,虽然这样做也要冒一定的风险。多次比赛和训练的经验也告诉我,比赛中过的人少的题未必就是难的,有些过的多的题对自己而言未必容易,也有可能是数据水。不过赛后再来想,这场比赛对我和我们队,无疑都是一次非常宝贵的经验。接连两场国内的Regional,我们都比的不太好,看来我们还有许多需要调整的地方,得回杭州好好练练。福州赛区成为我在大陆参加的最后一次Regional,我在大陆Regional的最好成绩定格在了ICPC排名第三,去年的合肥和今年的福州都多少留下了一点遗憾。总结经验,继续努力。

20 Responses to “ICPC Fuzhou Regional – 萎靡开局,福州梦游 by watashi@ArcOfDream”
  1. xiaodao says:

    。。。。yyymmmmmmmm .. .. > < ….

  2. C8Luka says:

    有么有解题报告来着。。。期待ing

    • watashi says:

      木有,主要几题的思路里面都有了,没拷比赛时后的代码
      再后来听说这套题没什么原创性,都是左抄抄右抄抄OI原题来的,也就没爱了

  3. lxyxynt says:

    ymmmmmmmmmmmm!

  4. AekdyCoin says:

    ym………

  5. zym1010 says:

    yyyyyyym!!!!!!!!

  6. VegetableB says:

    队长失职很严重啊……

  7. VegetableB says:

    F为啥还要两个人来写?

  8. Navi says:

    bgしろ。ファイナル男
    final金牌的塔梅你,bg吧…

  9. LCLL says:

    BG!

  10. LCLL says:

    BG吧

  11.  
Leave a Reply