原文最初发表于2009年10月14日,并消失于地震

Rank 校名 队名 题数 时间 ICPC奖项
3 浙江大学 yukkuri 5 434 Gold Medal

10月9日(金)

出发:杭州->合肥

杭州离合肥这么近,可是由于某些脑残的报销规定,我们不得不选择早上5:30的火车。我不幸的忘记了国庆假期后熄灯拉电的规定,结果没能好好收拾行李,睡了3个钟头之后就起床到了计算中心218。看时间还早,于是玩了回东方星莲船,第一次带着一把残机到了第六面,眼看就能Clear了,结果被一个魔爪抓去了火车站。到了火车上悲剧的发现我们八个人中过半的铺位已经被补票补掉了,折腾了半天,才总算换到了铺位可以接着睡了。午前就到了合肥,不过无事可做,只能在宾馆里接着宅。

10月10日(Fire)

@USTC

开幕式好早啊好早啊好早啊,一个上午好无聊啊好无聊啊好无聊啊,USTC的饭菜好实惠啊好实惠啊好实惠啊。最后bs一下叫嚣盖棉被,结果被jay哥打得满手通红就回去睡觉的圡Fire。

试机赛

进入试机场地,发现桌子果如winsty所说很小且很晃……

A
A是我看的题,比较简单,很快写完测完sample便交了,在pc^2里手抖了好半天才交上……run id 3,1y。据说run id 2的提交因为数据还没有准备好得到了RE,= =b。

B
B是寒mm看的题,常见模型,和他讨论后交给他写,后来发现写的复杂了,改过之后也过了。

C
C是jay哥看的题,不算难,但要花点时间写,还有些要注意的情况。折腾了挺久最后一小时过的,不少队伍都比我们先过了,不过最后过这题的队伍也不多。当然,如果在正赛的话我会去写这题的。

然后试验发现可以测TL,编译选项不但有-O2或更高级别的优化,还有-Wall(-_-b)。传说中的PE是怎么用力也搞不出来的,其余没什么发现。不过ForWarD过来说裁判比较业余,他们三道题都判错过,最后一题数据范围也有问题。悲剧的是正赛最后一题数据范围依然有问题,而我们倒在了那里。

看了一下队伍座位的对应表后发现合肥大概是大陆不包括旅游队最弱的赛区了。今年作为一个打酱油的老人,定的目标也就是用力给队友搞个金,ms没什么压力就能实现了,当然还是yy尽量好的成绩的。

最后补个8g,据说郭老对moondy念念不忘……

10月11日(*)

正式赛

正式比赛的开场相当的乱,键盘随便动……于是水寒先上去敲vimrc,打开pc^2,看还有点时间又让jay哥敲他习惯用的header。比赛开始后,水寒登pc^2,然后我负责看A-D,水寒EFG,jay哥从后往前看。实际上我跳过了A看了B,B的题意瞄几眼便能看懂,马上就想到了Java的BigInteger.isP*Prime,不过没有马上写。再回过头看A,A的题意也不难,而且算法是马上可以想到的,却不是能马上写的。再翻到C,一看好长,于是决定去写B。

BD
B用NetBeans写了个跑表的程序,然后1y了,当然实际不跑表也是够快的。看Ranklist发现无数的队伍过了D,于是问D题意,才发现和试机时的A基本一样(个人觉得出这样的题很不合适- -,试机的时候大家过得还是有先有后的,结果到了正赛噼里啪啦全过了),于是基本一样的算法写了调过sample后1y。

比较快的两题之后,我们三人开始讲题,除了H(エッチなのは大嫌い!)都看了,I没看出题意的不同之处,C的规则也不是很清楚。寒mm决定想想C,我也指出A是迟早要过的题(悲剧的事实是最后也没有过)。

E
E是一个很明显的多串匹配,用模板的AC自动机就好了,于是由jay哥搞定AC自动机,我去写其余的部分。这是我第一次用这个模块,以前都是自己写的,结果传说中的模块bug依然还在,我大概改了之后,测了两个相同的模板串和一个模板串是另一个模板串子串的时候都没有问题,交,返回RE,发现是数组开小了>_<。立马改过,交,2y。

中间寒mm准备过写C,不过题意不是很清,问judge,judge也是No response。看Ranklist也是有提交没AC,于是我觉得不要冒险的好,后来judge response告诉我们这是一个大自然,没碰是对的。

G
上交早早过的G看了看不是很有想法,于是我先去码A的代码。码的时候水寒谈他关于必胜必败的想法让我对这题有了点思路,于是我放下A攻G,很快就推出了正确的做法,于是交由水寒写求sg函数值部分的代码,而同时推出剩余的dp方程。最后我改过几个bug调过sample后就交了,judge没有返回我就发现自己处理s < n时会出错,结果返回的果然是WA。在for循环里加上一个条件后再交,2y。这时候我们队做到的Ranklist的bd。

J
J是和今年宁波办的全国邀请赛中一道题基本一模一样的题目(……),而我当时在Tri过了那道题,所以我去写J。写了有些时间后交,WA了,于是打印下来调,jay哥和我一起看代码,想test case。看了一段时间后发现dp的一个bug,改过之后再交,结果还是WA。(rejudge之后这次应该AC了)直到比赛结束jay哥想了很多case,我也看了无数次代码,期间也有过一念是否数据越界的想法,不过还是没有这样改一改交的魄力。现在想来如果当时像我们平时训练一样加点assert什么的就不致如此了。结果是我被这道题玩了半场比赛……最悪

A
本来我是yy过了J就写A的,最后齐力攻A避免WA。结果我卡在了J上,A是寒mm写了,逻辑上很漂亮,可以WA了,发现了一个可能NaN的地方,改过之后也还是WA,后来都是寒mm一个人在看A,我们在看J,效果很差。

I
I就没看对题意,决定写I的时候也就确定了我们这场比赛的失败。I先是写错过了sample,submit后WA,改过之后才发现题意理解错了。

比赛结束前无力的提交了几个A和J,没有任何惊喜,只有失落。

icpc2009hefei_runs

icpc2009hefei_runs

等待

比赛结束后过了5题的ForWarD过来问我们的情况,说了J数据可以超范围的情况。于是让Fire联系裁判组要求rejudge,当然,如果rejudge我对J能过还是有信心的。之后我,frozen,Fire和于指导就在草地上打升级,确切的说是消磨时间。颁奖前Fire接到了电话说我们的J过了,ICPC排名第三。当时我的心里真是哭笑不得。

颁奖&晚宴

颁奖很仓促,因为有不少队伍要赶当晚的火车。颁奖时才发现来合肥的都是loser,ym某人生的赢家 orz

颁奖的时候居然大多数队伍队伍名都是用英语读的,不过我们去添乱了,我们队成了唯一个队名不会读的队 ~ ~ >.< T_T。其实我们的队名yukkuri -> ゆっくり -> 油库里|馒馒来(东方二次创作同人),也有取慢慢来,一步一个脚印之意。

ゆっくりしっていてね!!!

ゆっくりしっていてね!!!

晚宴是在另一个宾馆吃的,第一个菜是西湖牛肉羹(点点点),不过没有食堂三楼的好,开场比较华丽,后面有各种乱入。另一个发现是,虽然Fire一再强调说给大家定了个更好的宾馆,但这大概是根据他风味的饭灰长好吃的标准判断的吧。

还有一点就是,出来混跟着于指导是没错的,其他人都不靠谱。回去路上,我们的科大交流生完全带错了路,还把THU的也给带来了,最后我们只好解释到我们是去仰望星空的。

10月12日(月)

返程:合肥->杭州

恩恩,果然出来的时候还是七个人一起玩找朋友最有趣啊。

小结

被数据郁闷的,但比赛还是相对公平的,主办方也是用心的,不少强队也在J上WA了不少次,但他们迈过了这个坎,而我们在这里倒下后就没有爬起来。吸取教训吧,回想起来我们有无数的机会能搞定J的问题,尤其是联想我们多次训了中的数据问题。前面还是挺顺的,mark一下吧,从组队到现在我们队也有了很大的进步。

悔しいだけど、まあ、悪くない。

	恭喜中大SYSU_Blover夺冠!
	恭喜所有赢得WF ticket的学校!
	恭喜ForWarD夺金(winsty和frozen记得bg)!
	恭喜hsys和jay23jack获得金牌,一样记得bg!
	感谢所有在88和98为我们应援的朋友们!
	感谢Fire和于指导带队和训练,给了大家很多帮助!
	祝所有acmer在接下来的赛区中取得好的成绩!
	祝浙江大学acm代表队在合肥赛区旗开得胜!

封board时的Ranklist:

Rank Name Solved Time A B C D E F G H I J Total att/solv
1 team69 AlphaCentauri 清华大学 6 563 1/123 1/79 0/– 1/5 1/25 0/– 2/62 0/– 2/229 5/– 13/6
2 team52 Catalyst 北京大学 5 502 1/161 2/100 0/– 1/10 1/49 0/– 2/142 0/– 0/– 4/– 11/5
3 team78 UESTC-floyd 电子科技大学 5 536 0/– 1/18 0/– 2/50 1/42 2/168 2/198 0/– 3/– 0/– 11/5
4 team73 FreeRadiant 武汉大学 5 592 4/228 1/34 0/– 1/15 1/80 0/– 3/135 0/– 0/– 0/– 10/5
5 team21 SYSU_Blover 中山大学 5 669 4/181 1/96 0/– 1/4 1/144 0/– 1/184 0/– 0/– 0/– 8/5
6 team17 DivinePapier 清华大学 5 820 0/– 1/181 0/– 1/22 1/91 0/– 2/226 0/– 0/– 4/220 9/5
7 team67 Montage 北京大学 5 833 2/218 1/123 0/– 2/13 1/193 0/– 5/166 0/– 0/– 0/– 11/5
8 team95 Rhodea 上海交通大学 4 147 0/– 1/56 0/– 1/12 1/48 0/– 1/31 0/– 0/– 3/– 7/4
9 team92 yukkuri 浙江大学 4 261 0/– 1/14 0/– 1/20 2/64 0/– 2/123 0/– 0/– 2/– 8/4
10 team83 不怕烫 北京邮电大学 4 272 0/– 1/14 0/– 1/53 1/36 0/– 2/149 0/– 2/– 0/– 7/4
11 team13 ForWarD 浙江大学 4 303 0/– 1/36 0/– 1/20 1/63 0/– 2/164 0/– 0/– 0/– 5/4
12 team51 maybe 西安电子科技大学 4 305 0/– 1/7 0/– 1/15 1/60 0/– 1/223 0/– 0/– 0/– 4/4
13 team23 Trumps 复旦大学 4 359 0/– 1/50 0/– 1/9 1/142 0/– 2/138 0/– 0/– 3/– 8/4
14 team8 ZSL 中南大学 4 401 0/– 1/85 0/– 1/36 1/69 1/– 1/211 0/– 0/– 0/– 5/4
15 team61 A.C.E. 复旦大学 4 432 0/– 3/156 1/– 1/25 1/56 0/– 0/– 0/– 0/– 3/115 9/4
16 team30 HappyHeaven 复旦大学 4 445 4/208 1/8 0/– 1/13 1/156 0/– 4/– 0/– 1/– 0/– 12/4
17 team29 Falcon 北京大学 4 452 0/– 1/91 0/– 2/33 1/144 0/– 1/164 0/– 0/– 1/– 6/4
18 team41 SCAU_Arctic 华南农业大学 3 80 5/– 1/25 0/– 1/18 1/37 0/– 0/– 0/– 0/– 1/– 9/3
19 team14 BeyondGod 武汉大学 3 82 0/– 1/23 0/– 1/9 1/50 0/– 0/– 0/– 0/– 0/– 3/3
20 team84 Optimus Prime 南京大学 3 91 0/– 2/17 2/– 1/5 1/49 0/– 0/– 0/– 0/– 0/– 6/3
21 team27 ACMagic 北京交通大学 3 95 0/– 1/18 0/– 1/20 1/57 0/– 0/– 0/– 0/– 0/– 3/3
22 team26 Legenddesert 华中科技大学 3 96 0/– 1/24 0/– 1/12 1/60 0/– 0/– 0/– 0/– 0/– 3/3
23 team87 TJU_HanoiTower 天津大学 3 102 3/– 1/36 0/– 1/8 1/58 0/– 2/– 0/– 0/– 0/– 8/3
24 team66 HDU-VS 杭州电子科技大学 3 108 0/– 1/12 2/– 1/21 1/75 0/– 3/– 0/– 0/– 0/– 8/3
25 team93 FreeTrio 武汉大学 3 148 0/– 1/32 0/– 1/19 2/77 0/– 0/– 0/– 0/– 0/– 4/3
26 team20 TJU_Kate 天津大学 3 155 0/– 1/76 0/– 1/14 1/65 0/– 0/– 0/– 0/– 0/– 3/3
27 team10 Castor 华东师范大学 3 159 2/– 2/43 0/– 1/16 1/80 0/– 0/– 0/– 0/– 0/– 6/3

Final Ranklist:

Rank 校名 队名 题数 时间 ICPC奖项
* 清华大学 AlphaCentauri 7 870
* 北京大学 Catalyst 7 1319
* 复旦大学 Trumps 6 874
1 中山大学 SYSU_Blover 6 1061 Gold Medal
2 北京大学 Montage 6 1271 Gold Medal
3 浙江大学 yukkuri 5 434 Gold Medal
* 电子科技大学 UESTC-floyd 5 536
4 武汉大学 FreeRadiant 5 592 Gold Medal
5 浙江大学 ForWarD 5 596 Gold Medal
6 清华大学 DivineRapier 5 728 Gold Medal
7 北京大学 Falcon 5 728 Gold Medal
* 复旦大学 HappyHeaven 5 842
* 上海交通大学 Rhodea 4 147
8 北京邮电大学 不怕烫(_0xDEADBEEF) 4 272 Gold Medal
9 西安电子科技大学 maybe 4 305 Gold Medal
10 中南大学 ZSL 4 401 Gold Medal
11 天津大学 TJU_HanoiTower 4 410 Silver Medal
12 复旦大学 A.C.E 4 432 Silver Medal
13 北京大学 Default 4 578 Silver Medal
14 福州大学 ACOrz 4 594 Silver Medal
15 山东大学 new born 4 638 Silver Medal
16 中山大学 SYSU_CoffeeBean 4 668 Silver Medal
17 国防科学技术大学 JavaMHope 4 824 Silver Medal
18 华南农业大学 SCAU__Arctic 3 80 Silver Medal
19 武汉大学 BeyondGod 3 82 Silver Medal
20 南京大学 Optimus Prime 3 91 Silver Medal
21 北京交通大学 ACMagic 3 95 Silver Medal
22 华中科技大学 Legenddesert 3 96 Silver Medal
23 杭州电子科技大学 HDU-VS 3 108 Silver Medal
24 武汉大学 FreeTrio 3 148 Silver Medal
25 天津大学 TJU_Kate 3 155 Silver Medal
26 华东师范大学 Castor 3 159 Silver Medal
27 杭州电子科技大学 HDU-Sailormoon 3 170 Silver Medal
28 电子科技大学 UESTC-try 3 172 Silver Medal
29 中国地质大学(北京) newHope 3 215 Silver Medal
30 福州大学 3CTriangle 3 216 Silver Medal
31 北京交通大学 Archmage 3 231 Bronze Medal
32 哈尔滨工业大学 Edgar 3 242 Bronze Medal
33 中山大学 SYSU_Cattail 3 247 Bronze Medal
34 西南民族大学 Codedelight 3 250 Bronze Medal
35 山东大学威海分校 dragon warrior 3 272 Bronze Medal
36 北京航空航天大学 DDR4 3 282 Bronze Medal
37 华中科技大学启明学院 hustSlowHand 3 301 Bronze Medal
38 厦门大学 HopeAndDream 3 316 Bronze Medal
39 湖南大学 CoreCoder 3 335 Bronze Medal
40 哈尔滨工业大学 KeepStar 3 339 Bronze Medal
41 东北林业大学 leifeng 3 340 Bronze Medal
42 南开大学 Hot 3 351 Bronze Medal
43 南京理工大学 Jupiter 3 356 Bronze Medal
44 华东理工大学 Overmind 3 362 Bronze Medal
45 北京交通大学 FinalFantasy 3 370 Bronze Medal
46 浙江工业大学 _Codec 3 372 Bronze Medal
47 上海交通大学 TeaM 3 405 Bronze Medal
48 合肥工业大学 AC_Combo 3 409 Bronze Medal
49 上海大学 Larva 3 410 Bronze Medal
50 国防科学技术大学 AlpCRush 3 418 Bronze Medal
51 华南理工大学 SCUT_MAJORD 3 434 Bronze Medal
52 清华大学 E.W.F 3 435 Bronze Medal
53 北京邮电大学 推土机(iessur-912) 3 453 Bronze Medal
54 吉林大学 aura 3 457 Bronze Medal
55 天津大学仁爱学院 Tjrac_Aplomb 3 498 Bronze Medal
56 大连理工大学 Bombe 3 504 Bronze Medal
57 同济大学 一家老小向前冲(AllFamilyHandsRush) 3 511 Bronze Medal
58 西南科技大学 feeling 3 556 Bronze Medal
59 西安交通大学 Tsacomy 3 560 Bronze Medal
60 南京邮电大学 PUMA 3 567 Bronze Medal

3 Responses to “ICPC Hefei Regional - 悲剧?喜剧? by watashi@ゆっくり”
  1. EUYUIL says:

    博主你好。我想请问一下,2009年合肥赛区现场赛的D题(Laser in Cuboids),就是被长方体的体对角线穿过的小正方体个数那一题,思路是怎样的。现在我可以求得2维的情况,不知道怎样运用容斥原理来求3维。网上的题解太少了,只是提到是用容斥原理。感激不尽!

    • watashi says:

      看一下容斥原理其实就明白了,其实二维的时候已经运用了容斥原理啊,本质上就是多还少补么
      1D: X
      2D: X + Y – (X, Y)
      3D: X + Y + Z – (X, Y) – (X, Z) – (Y, Z) + (X, Y, Z)

      • EUYUIL says:

        好像懂了……我原来有猜想2维的时候,假设长方形 a x b, 如果 a 与 b 互质。然后这个长方形的对角线穿过正方形有 a + b – 1 个;如果不互质的话,就可以拼接 gcd(a, b) 个小长方形:

        inline int count_squares(int a, int b)
        {
        int gcd = gcd_euclid(a, b);
        a /= gcd; b /= gcd;
        return (a + b – 1) * gcd;
        }

        似乎这东西乘开之后就是……容斥原理算出的结果……
        多谢啦~~

  2.  
Leave a Reply