楼教的ACM之路电子科技

采纳假日空闲之时,将这几年GCJ,ACM,TopCoder 参预的有些重大比赛作个
想起。前些天是GCJ2006 的回想,明日光阴上更早一些呢,我现在还清楚记得3 年
前,我刚好参加ACM 时在座香港(Hong Kong)市赛区2005
和青岛赛区2005 的情况。
2005 年ACM-ICPC——酸甜苦辣
自我进入南开大学始发本科学习的年华是2004 年8 月,在进入南开大学的第一
年里,由于底子课学习相比较紧张,再增加统计机系不容许大一学生自带电脑,我没
有参加2004 年的ACM 比赛。不过在大一一年中从不停息这上头的演习,对ACM
或者热情高涨。
大体在2005 年7 月中,与同班同学shell(贝小辉)和superzn(张宁)一起
决定组队加入ACM 竞技。对于队名没有太多的想法,就随便取了一个字典序靠前
某些的bomber。随后举办的几场磨炼中,我的编程状态从来维持得很好,陶冶比
赛的主要方式都是:我主写程序,shell 和superzn
负责翻译难点,思考算法和测试。
那种组队格局平昔沿用到大家前边的富有竞技中。
2005 岁末,我们提请参预了2005 年的首都赛区和德班赛区的竞赛。顺遂通过
了预赛进入了现场决赛。记得及时佐世保市赛区预赛的时候,我和superzn
一起在参与
百度之星程序设计大赛,shell 依靠一人之力过了6
题,最终以第二名的身价插足
京师赛区实地比试。
上海赛区:
2005 年的都城赛区地点设在邻近的上海高校,由于交通非凡方便,大家并未
和大多数选手住在一起,可是也没有临场Java-Challenge 和早晨的演出。
操练赛从前,说到比赛地方抽签,本身意义不是很大,但是邬老师神奇的RP
把五只清华的枪杆子抽在同步,结果陶冶赛举办了一半,另一只南开的行伍THU1
(队员是:吴景岳,栗师和金凯,好像后来队名改成了DreamCatcher,不是很确
定)被要求换到一个比较远的地点,理由是多少校园觉得那样不创造。后来众多赛
区也应运而生过阵容座位在共同的状态,邬先生的RP 果然不是盖的。
回忆训练赛时和南开的LemonTree(盛城)一起在场馆里游荡,结果果然不到
10
分钟就被要求回座位了。还有当时比赛场面是一个篮训练场,有些阵容把气球放
飞之后气球就飘在天花板下了,主任判李文新教授还威迫大家说,假如前几日专业比
赛把气球放飞,就不算通过相应的标题,除非有点子把气球取下来。
然后就是比赛的进度了,下边有底纹的文字是自个儿找到的即时留给的比赛总计:
E:连忙排序。5 分钟1Y。
本人想5 分钟的年月可以争取这几年ACM 国内赛区的最快出题记录了呢。
G:二分答案+最小生成树。25 分钟1Y。
那题就是经典的最优比例生成树问题,大家一样觉得那题相比较简单。但是新兴
被李文新老师批评了,说法是误导其余的武力。不过说到最优比例生成树难题,
TCO2006 的时候fwj 和tomek 竟然都并未见过那道难题,那题可是来自POI
呀。我
想我们认为这道难点不难的第一原因是大家都在冬令营上见过那到难题,假诺第一
次看见,想出算法可能确实需求一些时间。在那边向被大家影响的军旅的道歉,最
终G 提交了200 很多次,然而唯有8 个武装AC。
C:二分图最大匹配。42 分钟1Y
难点须要测算一张图的小不点儿覆盖集,可能唯一的tricky 是意识图是二分图。
D:遭受了必然的困顿,发现A 很简短,于是先放一下
D 是一道相比综合的标题,设计有些粗略的乘除几何和字符串处理的知识。
A:不难的几何难点,出现了一个初级错误,提交了3 次均为WA。
A 是日田市赛区最不难易行的题目,我的程序里犯了一个很低级的错误,可能也是经
验不足造成的啊。
D:重新写,然而尚未设想一种情形,WA 了1 次。
87 分钟,哈工大的Abuacus 过了4 题占据了Rank1。由于军队方式的案由,大家
在还有为数不少不难易行难题的情景下卡住了长达30 分钟。
A:shell 突然发现了A 程序中的低级错误,105 分钟AC,重新夺回Rank1。
那是很首要的一步,现在测算倘使没有这一个意识,后果或者岂有此理。
B:二分答案+2SAT。129 分钟AC。
B 是一道分明的2SAT 问题,由于标题相比长,大家平素不很早发现这道简单题。
D:发现了D 的尚未设想的景况,140 分钟AC。
看了一个board,那时Abuacus,Eccentric 都唯有4 题,可以在率先次到位正
式比赛就马到成功6-4
的超越,当时情感很打动,但是鉴于缺少经验,也影响了接下去
的宣布。其实,现在回看起来,这一次比赛其实是一个很好的AK 的火候。
F:DP。程序比较复杂,WA 了4 次。
F 是一道相比较复杂的动态规划的题材,其实WA 的案由是一个应该用int64 的
地点,我们使用了int,这么些地点确实很难发现。
H:F 一时无法AC,只能转功H。H 就是司空见惯的模拟题。开始并未考虑坦克和
炮弹可能在1/3 秒相遇,WA 了1 次。
比赛还有一个钟头,封板。
H:shell 发现了坦克和炮弹可能在1/3 秒相遇的状态,250 分钟左右AC。
对此大家那种组队格局,当主写程序的选手状态不好的时候,很简单并发连续
卡题的图景,那种场所的面世很不便民水平的正规表明。在新加坡赛区的较量中,我
们很幸运没有出现三番五次卡处的事态。
记得,当时香江市赛区的Judge 的自动的,就是说倘若结果是AC,速度就会非
常快,否则由于人的参预,无法AC 的交给往往须求等一段时间。大家第2
次提交
H 之后,没有拿走长足的死灰复燃,以为早已WA 了,于是自己和superzn
继续测试一些
数量。但那时,突然有一个mm 从左边走过来插气球,那一个气球也变为了全场唯
一的黄色气球,那几个意外之喜最后成功了第三个分区赛亚军。
F:上面就是忧伤地提交F,一直战斗到最后一刻,WA 了14 次,留下了巴黎
赛区最大的不满。
在最终时刻我们似乎察觉了卓殊int64 的荒谬,不过当下思路已经相比混乱了,
没能改对。F 的难点也导致没有时间写I,当时一旦直接重写后者换superzn
来写F,
完全可以在竞赛截至前AC。
比赛的几乎进度如上所述,那么些神奇的气球,我现在依然历历在目。最后有4
个队伍容貌攻破7 题,Abacus 的组合应当是盛城,timegreen 和suzhan
吧,Eccentric 中
本身只记得辛韬,ZSU_Panku
中本身纪念Savior(陈实)。上述的老朋友之后会面的机
会就很少了,分区比赛也改成了我好内需老同学紧要的沟通机会了。
我ACRush 的ID 臆想就是那时开首接纳的呢,转眼就曾经3 年多了。
比赛前后还记得时常与南开高校的吴永辉先生聊天,在那未来的每一次比赛我都
能看出她年轻的人影。
现行回首起东京(Tokyo)的分区赛,很幸运可以在第四遍到位ACM 正式比赛就收获分
区竞赛的亚军。我想是由于现场氛围对广大武装都有不小的熏陶啊,当时众多部队
都卡在几道相比较繁琐的难点上了,标题的算法性都不是很强。我大概从那时候才刚刚
接触TopCoder,如若可以早一些,相信会更适应那样的竞赛。
阿德莱德赛区:
2005 年的ACM 圣彼得堡赛区竞赛在西藏大学进行,马那瓜赛区的时刻就在首都赛区
为止后一周,最初接纳波尔图赛区的缘由很大方:我自己家在圣何塞。实际上也大都,
自身随部队(当时THU 派了3 只阵容插手德班赛区的交锋,除了大家队之外,
b142857(侯启明),zhy(周源),ysy(杨
思雨)组队,其它一只由汪汀,王俊
和黄源河构成)一同到达瓜亚基尔车站之后就即刻回家休息了,直到比赛前才重回。在
香港到坎帕拉赛区之间的七天中,我的情形就在
不断下跌,在家庭完全失去了竞赛
的空气,回到赛管再也找不到觉得了。一场悲剧即将上演。大家先看看比赛进程吧,
上面有底纹的文字是自我找到的当即留给的比赛 总计:
G:初看很简单,可是调试了30 分钟没有结果。
G 是一起数学难题,其实《具体数学》书上有肯定的公式,不过大家选择的递
推方法应该也足以取得正确的结果。程序中犯了有的低级的荒唐,由于实在不在状
态,调试了30
分钟还并未找到错误。那里还暴光了一个组队格局的难点,在后来
的组队格局中,如若像那样没有想知道算法的标题队友是毫无疑问不容许我去写的。
A:模拟。41 分钟AC,当时早晚没有想到那是唯一一道1Y 的题材。
A 是一道模拟题,1Y 的时候已经很晚了,排行也很靠后。
C:图论。可是出于堆栈逸出RTE 了5 次,浪费了汪洋的时间。
C 的标题有关树中祖先关怀的论断,标题很粗略,完毕的主意也很简单,就是
因而一遍DFS 来总结。不过大家忽视了一个有史以来不曾赶上过的难点:堆栈溢出。
与此同时,堆栈在当地机械上运行进度中,Eclipse 提供了8MB
左右的库房,所以没有
溢出,不过在交付未来的环境下运行就溢出了。而且每一遍RTE 之后,我们向来在
品尝修改数组的轻重缓急,一贯尚未找到根本原因。调试C
的还要,我也尝试修改G,
结果G 也错了8 次之多,并且始终都是WA。
I:shell 在我郁闷地调试C 和G 中AC 了,此前WA 了一次。
I 是动态规划难点,WA 五遍可能是忽视了一些境界景况。
D:网络流,没有想到先贪心举行优化。TLE 了5
次最终没有通过。
D 就是计量最小割,大家事先准备了先流推进算法,可是依照那道难点的模子,
先流推进算法蒙受最坏情状:二分图。由于当时dinic 还不是很盛行,大家TLE

5 次还未曾经过。
闹心地调试D 和G。
E,B:都尝试过,可是都出现了不明的题材。
在紧接着的时日里,不断调试D 和G,然则一向无法AC。之后又尝试E 和B,E
透过分支的措施可以拍卖,B 是数学难题。正常的话E 和B
并不是很不方便的题材,
但是及时曾经相当混乱,连样例都不曾经过。
终极大家只过了3 题,排在21 名,经历了自家加入ACM 以来最惨痛的破产。
这一次失利首要归过与我状态太差,基本上什么难点都不可以布帆无恙通过。当然标题标选
择也有很大的标题:G
确实不是难点,可是出于未知的原由平昔不可以透过,后来自己
把纸上的顺序敲在ZJU 上就AC 了,至于现场为何不可能AC
我今日仍旧不可以知晓。
假诺说第一题的抉择直接影响了大家的信心,那么D 的库房溢出则统统打乱了本人
们的点子。对于我们的组队情势,卡出2 题已经超出了极点,我们不可能再品尝
任何题材。
Abacus 也来临了底特律,他们最初展现了强劲的事先优势,在2 小时就达到了6
题;b142857(侯启明),zhy(周源),ysy(杨思雨)的队伍容貌彰显得一定大胆,
在结尾一小时超过了Abacus,夺得了亚军。
阿德莱德赛区的挫败至今仍是内心疼苦的追思,然则那么些教训也是对本身后来的学
习生活的一种警示。
总结:
2005 年是自个儿先是年到位ACM-ICPC 的较量,两场ACM 分区赛,大家经历了夺
冠的欢愉,也经历了环顾四周等待竞赛停止的无奈。2004
年南开没有获取任何分
区赛的季军,2005
年哈工大打了个地道的翻身仗,先后在圣多明各,上海和伯明翰夺得冠
军,而且是三支不相同的大军。
四个赛区的G 都是有传奇色彩的题材。日本首都赛区中,我们25 分钟1Y 了G,
造成成千上万人马跟风败北,最后落得了208 提交8AC 的低通过率。不过,马斯喀特赛区
中,G
从比赛一初阶就占据了俺们大批量的光阴,直到最后都未曾经过,估算至少浪
费了三个钟头左右。真所谓成也在G,败也在G。
新加坡赛区后,POJ 的论坛上传闻说自己已经说过“起身去厕所,不许碰键
盘。。。”,很向往那几个同学搞笑和拉扯的底子,大家即使定下了以我主写程序的
组队方式,不过也极度器重合作和各种人在部队中的主要功能。
随即北大没有团队校内PK 选择,拔取了卡尔加里赛区的亚军队THU1 参预满世界总
决赛,当时半决赛队伍容貌是以参考第二赛区的战表控制的,现在回想起来也是很有理
的。由于最终大家决不可能得到机会到位全球半决赛,接下去多少个月我们情感低沉,
bomber 从当年也就公布解散了吧。
2005 年的比赛进度中,我看到了巨大的故交。用吴永辉先生来说,
ACM 竞技可以当做一些老朋友一起进行的一场智力游戏。
附新加坡赛区前5 名:
1 Tsinghua University=>bomber First Place 7 788
2 Fudan University=>Abacus Second Place 7 983
2 Shanghai Jiao Tong University=>Eccentric Second Place 7 1084
3 ZhongShan (Sun Yat-sen) University=>ZSU_Panku Third Place 7 1194
4 Peking University=>Monkey King Fourth Place 6 768
找不到马那瓜赛区的排行了,只发现了这几个:
21 THU *bomber3 501 1/41 0/– 6/197 5/– 0/– 0/– 8/– 0/– 2/143 22
谢谢韩家龙同学的热情帮扶,找到一个名次的链接是:
http://acm.zju.edu.cn:8080/icpc2005/ranklist/index.html
选拔沐日空闲之时,将这几年GCJ,ACM,TopCoder 参与的一部分紧要比赛作个
回溯。GCJ2006,ACM2005 和TCCC2006 之后, 2006
年对于我来说是一个大丰收,
前几天上午先想起Mobile Robot 创造先期的业务吗,前几天再下结论惊心动魄的ACM

海2006 和ACM 西安2006 吧。
2006 年ACM-ICPC(上)——Mobile 罗布ot 的建立初期
回看到2005 年南开没有协会校内PK 选用,采用了金奈赛区的季军队THU1 参
加全球季后赛,bomber 从那时候也就昭示解散了。
早在2006 年底,THU1 准备参与ACM-ICPC 2006 世界季前赛的教练时,大家的
军旅就已经创设了。队伍容貌其他两名健儿是一头参加IOI2004 的geworm(鬲融)和
wd.h(胡伟栋)。
Mobile 罗布ot 的组队比赛:
至于Mobile Robot 的队名,我们是为着记忆2004 年4 名参预IOI 的选手首先
次合营的时候使用的帐号,若是回到2004 年的PKU
月赛,也许能够阅览thmr3191
的人影,这么些ID 最初是我们4 人一起使用的。其中thmr 就是Tsinghua Mobile
罗布ot 的缩写。当然大家以为Mobile Robot 读起来也正如不难上口。
Mobile 罗布ot 成立未来做的率先件事情就是相当THU1 准备World Final2006 的
锻练,先后模拟比赛了三次Northeastern
Europe(NEERC)的题材。这五遍锻练中,
咱俩武装的要害形式都是:
(1) geworm 全程负责读题,思考算法和出多少;
(2) wd.h 和自身在竞赛前2 个钟头一起攻简单的题材;
(3) 2 钟头后wd.h 就伊始死磕难点,我主写程序一向到3 个半小时左右,结
合wd.h 对难点的握住,大家开端合攻难点。
那种拖后安康的打法,对于NEERC 的题目难度格外适宜,两场竞赛大家都做
到了AK(全过11 题)。那种组队形式也一贯沿用至准决赛。当时wd.h 的景色很
好,对于NEERC 的标题难度,我以为世界上很难有阵容可以有信心完结AK。
武装创建初期的顺遂使大家更有信念,大家应用署沐日子展开了一些必不可少的训
练以迎接2006 年下七个月的ACM 分区竞赛。
国都赛区预赛——网络赛赛网络:
2006 下八个月有3 个国内赛区,蕴涵巴黎,新加坡和西安,其中上海赛区开首举
行。2006 年巴黎赛区的地方设在了哈工大大学,那也是本人唯一几次涉足协会ACM

区竞赛的时机。
10 月 中旬进行了香岛赛区互联网预赛,网络预赛的参加者是享有报名参加巴黎
赛区的人马,以控制哪些队伍容貌具有加入现场比试的身份。那段时间,大家军事紧要
生气放在了
准备竞赛上,我们都尚未加入互连网预赛的命题和测试平台工作。由于
交大距离上次承办分区竞赛一度相隔很多光阴,直接促成网络竞技进程中出现了严
重的网络问 题,在此间作为浙大ACM 队的一员向遇到震慑的军旅道歉。
不 过,我也是作为“局别人”来打探本次互连网堵塞的,因为自己实在尚未加入
任何与网络赛有关的移位。现在回顾起来,我觉着平台的平静是一个不足推卸的
由来,不过关键应该归纳于题目叙述和样例的筹划,当然还有测试数据的不当。
设想那样一种意况,要是一个竞技进程中,从某一时时起,突然增添1000
个提交
需求rejudge,然后所有军事还都在这一随时起尝试提交,我想现有的绝超过一半OJ

很难在1 小时以内平息那几个付出吧。再举一个更夸张的例子,要是OJ
准备的测试
机械的测试速度已经完全跟不上提交的速度,那么卡住是不可幸免的。我们通过网
络预赛的教训总计出一些互连网预赛标题标主要经验:
(1) 对于不难上手的难点,测试样例一定要丰裕强。
(2) 对于简易的题材,必须密切确保测试数据是天经地义的。
(3) 标题叙述必须没有其余歧义,幸免选手经过付出来持续尝试各样掌握。
设若难题可以很管用控制提交数目,对于测试系统的渴求其实不是很高。例
如复活赛和现场决赛的时候,测试系统会大多数时光处于空闲阶段。反之,假诺提
交处在上述病态的场所下,只有可怜标准的测试系统才能胜任那样的挑战,当然不
概括我们的测试系统。
一句话来说,对于互连网难题我看成清华ACM 队的一员深表歉意,如果还有下三回的
时机,大家必然努力做得更好。
京师赛区验题赛:
如若说互联网预赛进程中,网络出了一些题材,那么,决赛则是结果更高于我
们的预期之外。在新加坡赛区现场赛此前些天,大家3 支阵容举行了验题赛,竞技
即使不规范,可是经过依旧很强烈。
先列一下决赛的9 道标题吧:
A. Robot
B. Animal Run
C. Another Minimum Spanning Tree
D. Connect It, If You Can!
E. Guess
F. XAR
G. What a Special Graph
H. Ruler
I. A Funny Stone Game
现场赛唯有BEHI 那4 道题目有部队成功通过,不过在验题赛中大家军队的进
程完全不是那样,下边是我们的做题情况:
22 分钟 A 题,数学方法,1Y
率先,大家3 支阵容在30 分钟以内都1Y 了A 题。A 题是一道中间难度的数学
题,可能A 题必要明确高次等差数列的求和公式,而且经过枚举来顶替部分如若
可以大大简化难题。现场比试时有点队伍容貌做了不正确的若是导致平昔WA。
回忆及时zhuzeyuan 使用了一个意想不到的贪欲方法,后来被OpenGL 找到一个反
例,这么些测试用例被添加到正式比赛的测试数据之中,这一个反例也变为了现场赛中
使得众多提交WA 的紧要数据之一。
30 分钟E 题,贪心,1Y
E 是2006 新加坡赛区最简单易行的题材,只必要直接的贪心法就可以化解。
52 秒钟H 题,深度优先搜索,1Y
H 是一道搜索题,题目时限不是很紧,不需求太多的优化就足以由此。
75 分钟I 题,标准的博弈SG 难题,1Y
I 是业内的博弈难点,通过总括SG 就能够收获结果。那题其实有一个险恶的
地点,就是当某地点石子为大于0 的偶数时,也亟需考虑以确保结果的字典序最
小,好在我们当下规避了这几个陷阱。现场众多三军调入这一个陷阱中,耽搁了一部分时
间。
129 秒钟B 题,最短路径难题,3Y
B 是一张平面图的最大流难题,由于图片相比较有风味,所以可以建图来计量最
小割。然而那张图有106 个点,2*106
条边,最短路径需求用堆来扶持达成,首先
是因为数组开小了RTE 了一回,然后由于用map 完成TLE 了一遍。那题浪费了很多
时间。
G 题,完结和调试了30 分钟,超时
G 是2006 香江赛区最困顿的题材之一,标题叙述很简短,判断一张图是或不是为
co-graph。我们算法的复杂度是O(n*m/32)的,可是出于数量个数相比多,程序运
行时间远超越了年限。
C 题,贪心法完成50 分钟,WA
C 题是总结平面图曼哈顿最小生成树,直接总括是O(n2)的,可是难题中n 接
近100000。我利用了一个利欲熏心算法,其实和规范算法差别不大,可是照旧促成
WA。其实提前写C 不是很合理的选取,当时从未有过放在心上到D。C 和G
难度相差无几。
230 分钟F 题,构造,1Y
F 题是很变态的布局难题,那题完全是wd.h 做的,我至今还不是很驾驭算法。
250 分钟D 题,统计几何,2Y
D 题是一道相比较复杂的计量几何,当判断一条直线是还是不是通过一个多边形的时候
忘记考虑了一种处境,WA 了1
次。现场众多武装实际都只忘记考虑了这一种处境,
可是可惜没有武力该正确。
本场竞赛最终我们阵容以7 题截止,别的两队也都经过了7 题。大家由此也
不曾改动标题难度,随后让我们没有想到的是:一场极低通过率的交锋快要上马了。
京师赛区现场赛:
实地比试中,我负责在某一个房间为参赛选手送打印材料,竞技60 分钟左右
出于技术难题到Judge 室处理部分题目。经过5 个钟头的竞技,最后中科大
Student 队由此4 题得到亚军,阿比让大学btALT 通过3 题得到季军,香港(Hong Kong)大学
RPWT,广东高校gogogo 和多特Mond航空航天高校Love Wisdom 也都通过3 题分列3-5
位。
末段Student,btALT 和Love Wisdom 进军常规赛。
回顾竞赛现场进度,首先让大家意外的是E,E 是2006 巴黎赛区中最简
单的题材,贪心法的不二法门插手比赛的同学都想开了,不过有一个小小的的底细,对于
实数相比较大小时,须要加入一个微小量eps 来控制精度。E 题没有加eps
的交给占
到总提交的50%以上,大家称为“经典提交”。这么些小tricky 不慎导致成千上万武装
缓缓无法通过第一题,对许多大军的图景有不小的影响。
其次是A,A 题收到了广大军旅的交由,然而最终都没有武力通过A。原因是
大家做了一部分不保障科学的比方,当时大家都通过枚举的方法防止了那些如果。
其余,有一对军旅提早接触了F 和G,并深切地陷入其中。中科大早在240 分
钟就通过了第4 题,不过其后他们在G 上费用了众多朝气蓬勃,大家居然想跑到她们
那边告诉她们G 是最难的。
记得180 秒钟到240 秒钟,大家只收取到了不当先10 次提交,每一遍我们听到
交由的动静,所有Judge 一起源鼠标抢测试权。后来,在TCCC2006 上和Ying
说起
此事,据她说和2004 年的斯德哥尔摩赛区有不可枚举相似之处。
总结:
恭喜所有得到好战绩的武力,恭喜Student,btALT 和Love Wisdom 进军总决
赛。并重新对互连网赛给大家带来的紧巴巴致歉。后来北大举行了名为复活赛的较量,
自身想复活赛应该就是从当下起始出现的啊?
那儿北大一共有6 支军队,但是只加入五个赛区的比赛,造成每个赛区从前
都要拓展小范围PK,最终只有4 支军队有机会参预ACM 分区赛。Mobile 罗布ot

立之初相比顺遂,得到了在座多个赛区竞技的时机,迎接Mobile 罗布ot
的将是上
海和罗利赛区的挑衅。
俺们3 人可以走在共同,要谢谢吴文虎先生的支撑,组队初期即便尚未经历
大战,可是那一个安心乐意的时段至今都很难忘怀。
附新加坡赛区名次
1 University of Science and Technology of China=>Student First Place
4 628
2 Xiamen University=>btALT Second Place 3 417
3 Peking University=>电子科技 1KU
RPWT Third Place 3 460
4 Zhejiang University=>gogogo Fourth Place 3 471
5 Hefei University of Technology=>Love Wisdom Fifth Place 3 477
6 Fudan University=>Yin-Yang Sixth Place 2 204
7 Tianjin University=>TJU_Rhythm Seventh Place 2 212
8 Beihang University=>L3 Eighth Place 2 254
9 Peking University=>电子科技 2KU4
Ninth Place 2 275
9 Harbin Institute of Technology=>IAC Ninth Place 2 282
10 ZhongShan (Sun Yat-sen) University=>ZSU_Pyrenean Tenth Place 2
288
11 Zhejiang
University=>电子科技 3hoebus
Eleventh Place 2 311
11 University of Electronic Science and Technology of
China=>Gryffindor Eleventh Place
2 319
12 ZhongShan (Sun Yat-sen) University=>ZSU_Himalayas Twelfth Place 2
324
12 Fuzhou University=>OrOrz Twelfth Place 2 412
13 Beijing University of Posts and Telecommunications =>Vitamin
Thirteenth Place 2 432
14 Ningbo Institute of Technology,Zhejiang University=>impact
Fourteenth Place 2 435
15 Huazhong University of Science and Technology=>rodimus Fifteenth
Place 2 442
16 Nanjing
University=>电子科技 4HOENIX
Sixteenth Place 2 459
17 Fuzhou University=>Laplacian Seventeenth Place 2 467
17 Fudan University=>Shuangwaiwai Seventeenth Place 2 500
17 National University of Defense Technology=>Robust Seventeenth
Place 2 517
18 Fudan University=>Free Wings, Yeah! Eighteenth Place 2 518
18 Hong Kong University of Science and Technology=>HKUST1 Eighteenth
Place 2 692
选用沐日空闲之时,将这几年GCJ,ACM,TopCoder 参加的片段重大竞技作
个回想。GCJ2006,ACM2005 和TCCC2006 之后,2006 年对于自己的话是一个大丰
收,后日早上回看了Mobile 罗布ot 成立先期的事体呢,前天头阵惊心动魄的ACM
上海2006 吧。
2006 年ACM-ICPC(中)——Mobile Robot 东京对决
追忆到,当年北大一共有6 支部队,可是只列席八个赛区的比赛,造成每个赛
区从前都要拓展小范围PK,最后唯有4 支军队有时机出席ACM 分区赛。Mobile
罗布ot 建立之初比较顺遂,获得了参与多少个赛区竞赛的火候,迎接Mobile 罗布ot

将是新加坡和西安赛区的挑战。
比赛前:空前的雍容高雅阵容
记忆交大高校起身Hong Kong赛区的岁月是10 月20 日夜晚,至于怎么能记得那样
精确,是因为在那从前我经验了确实意义上的“赶高铁”。10 月18 日TCCC2006
在布宜诺斯艾利斯落下帷幕,19 日从巴塞罗那机场起飞会北京,飞机着陆时间是20
日深夜
2 点半,进海关之后一度快4
点了,我当时乘坐机场大巴直奔火车站与大部队会晤,
中间都不曾时间回寝室。
赶来中亚餐馆电视发布获得参赛阵容名单的时候,就爆冷发现上海2006 的参赛队
伍实力达到了几年来一个不可逾越的极端。巴黎武大的1234
队都出现在了花名册中,
再有南开和哈工大的Final
队都来了,那么些还不够,鞍山一中的Loner(周冬),香港(Hong Kong)微
软ATC 的lympanda
也列席比赛。日本首都北大直接是这几年来清华国内最强大的对手,
当今复旦又占据主场优势,实力深不可测。巴黎微软ATC 就算是旅游队,可是
lympanda 凭借在TopCoder 上的显示,没有人敢轻视那位无冕之王的实力。
对此新加坡赛区,南开也指派了豪华的阵容,参赛的有3 支军队,除了Mobile
罗布ot(我,geworm(鬲融)和wd.h(胡伟栋))之外,还有鼎盛时期的Shangri-La
(b142857(候启明),lxd(林希德)和zhuzeyuan(朱泽园))以及新兴的武汉赛区季军
GotoFly(zcgzcgzcg(朱晨光),wangjun(王俊),tedcn(龙凡))。记得操练赛在此以前,
世家齐声围圆桌吃饭,朱晨光突然和一旁的王俊说,好像就我们三个尚未到场过
IOI,然后另一面林希德补了一句,就大家三个不是金牌。
自己先是次有机遇敬仰候启明的时候,是友善首先次参与NOI——NOI2002 圣多明各,
候启明以满分的战表获得亚军,当时的亚军就是林希德。之后的冬令营,我以非正
式营员参预测试神奇得得到第三名,但更要紧的是冬令营测试的冠亚军就是候启明
和林希德,之后我再没有和两位长辈在OI 上交过手。时光飞逝,我表示bomber
队参预2005 年的青岛赛区,被候启明领军的Legendary
Team打得一败涂地。随后
2006 年底的谷歌 Code Jam China(GCJC)2006
上,我获取第三名,记得当天与获
得亚军的候启明同住在总统套房。其实在巴黎赛区此前自辛亥曾在正规竞技中打败过
他们。Shangri-La 的另一人zhuzeyuan 现在是自我的队友,记得她当时在TopCoder

然是Target(你然而早点在今年Final 之前把Target
拿回去呀,三遍涨停就可以
电子科技 5),实力也不在前二人以下。
直面知根知底的Shangri-La,大家都清楚一场战争在即,从实力上分析,我觉
得Mobile 罗布ot
略弱,可是赛前我们都不曾信心一定可以在比赛中占有优势。而
且大家内心深知,香港赛区的结果将很有可能平素控制哈工大大学当场的半决赛队伍容貌。
直面那种狠毒的切实,我们都没办法,有时一些有实力进军季后赛的军队在北大
都没有机会到场分区比赛。
民用的经历看来,我认为在伯仲之间的时候,最要紧一点是领会自己的优势和
逆风局所在,要用自己最强的地方来对抗敌手,避免暴光出自己的逆风局。我想在这一
点上Shangri-La 可能没有我们做得好。Shangri-La
的优势是五个人的完全实力很强,
她们完全可以动用三大王牌的组队格局;大家组队时间长,合营默契,而且当时自
己刚刚从TCCC2006 以100%正确率回国,保持了不错的场所。从单人竞赛上讲,
即时我的图景即便有Petr 和汤姆ek
在场,我都并不认为自己肯定会有鲜明的逆风局。
比赛场所是新加坡大学的一个大体育馆,现场气氛很霸气,想到大家用4 个机房
办的京城赛区的实地比试,不由地认为有点保守。
在场外遇到了lympanda,他向我打听刚为止的TCCC2006 的图景,我于是给
她讲述了一晃几道实地比试进度中1000 分的难点,结果一切都被panda
秒杀了,
无限向往呀!同时也率先次探望了周冬。
提一件飘逸事情,记得及时练习赛有3 题,封版时未尝武力经过B 题,不过其
实际上封版后大家经过了那题,我们应当是及时唯一在练习赛中AK
的大军。记得之
后接近还和热那亚学院的郭老师交换过这题。但是关于B 为何可以AC:B 题是一
道必要SPJ
的难题,但是磨炼赛的时候从不SPJ,而自己又坚信自己的先后是不错的,
于是我连连提交。可能是由于Judge 不耐烦了,才用Yes 的法子让我们为止。
比赛以前的晌午我们都休息得很好,第二天早晨以丰饶的精力迎接史诗般的上
海赛区决战。
比赛进程:400 米赛跑
自己中学是很喜爱出席400 米竞技,400
米比赛从起跑姿势角度应该认为是短跑,
唯独400 米已经远远超过了冲刺极限。所以400
米跑中,须要大家从发令枪响起的
时候就加速开动,直到拼尽全力截止。
大家回忆一下竞技的进度吧,新加坡赛区比赛之后,大家写下了详实的较量进度:
根据稳定的艺术,鬲融从A 开端读,胡伟栋从J 起首读,我准备编程的环境,
下一场从中间选拔难点读。鬲融读完A 后,发现A 是一道不难题。于是选拔先写A
题。
A:给定ACM网上预选赛的竞技晋级规则,求每所高校的进步队伍容貌数。
简言之模拟题,时间复杂度O(N)。本题题目有一个问号:一个该校出线的武装部队
数量也许比该高校加入预选赛的队伍容貌数量还多,不过难点叙述和样例声明不要求考
虑那种意况。
ACM 竞技的首先题的挑三拣四对竞技的进度影响很大,当没有事先挑选竞赛中最
概括 的标题时,更亟待有限协助冷静。
在本人写A 的历程中,鬲融看了B 和C,发现C 也相当简单,于是立即做C。
C:将一棵节点带权的树划分成两半,使两半的权值和的差最小。
枚举或者树的遍历,时间复杂度O(N)。二〇一八年有一个深远的训诫:当遍历树的
时候,很简单造成堆栈溢出(乔治敦赛区留下的肿块)。对于主旨的限定,保证起见没
有选取DFS,而是选拔BFS。使用BFS 略微增添了编程量,但是可以在早晚水准
上防止不必要的分神。
鬲融发现D 是一道经典的总结题,在不到3 分钟的切磋后,我们得出了卓有成效的
算法,于是上边写了D。在写D 的时候,鬲融和胡伟栋把题看完了,经过钻探,
控制胡伟栋开端想一起数学题I,而鬲融继续看题义不是很理解的G 和J 两题。
D:给出平面里的一多重点,要找一个矩形,使矩形边上的点最多。
离散化后,先判断一条直线的场所。枚举两条横边,然后枚举竖边,一旦一条
左侧的边比左侧的边好,右侧的边就不会再有效应。因而,枚举竖边的进度很不难
成就O(N),总的复杂度是O(N3)
那题其实存在O(N2logN)的算法,我想出题人也理应没有在第一时间想到吧。
做出D 后写了B,原因是B 的算法相对简便易行。可是殊不知的是:B 的样例不
官方,而且Clarification 的进程非凡慢,于是只可以先把B
放在一边。那几个进程浪费
了过多体贴时间。
紧接着看到team109(Shangri-La)过了一道藏粉红色气球,感觉是G,于是鬲融给本人讲
了G,不过发现G 实在不像算法简单或程序不难的题材。
此刻,胡伟栋推出了I 的一个很明确的公式。而且大家发现I 的气球也是紫色
的。刚才看G 很可能是被误导的。于是写了I。
写I 的历程中,由于鬲融看的题基本已经被做完了,胡伟栋给鬲融讲了H 的题
意,鬲融想出了一个使得的做法,不过由于还有更简明的题并从未立时做。
I:求杨晖三角形第N+1
行不能够被质数整除的数的个数。
可以找出规律,然后写出公式,时间复杂度O(logN)。我在并不知标题意思的
动静下写过了I,依靠胡伟栋的公式,我们走过了此次竞技第一段辛苦的时期。
从过D 题到过I 题,大概有40 分钟的岁月。那段日子大家根本的失误有:
(1) B 的样例不合法,那事实上不是大家的错误。
(2) 受气球颜色的误导,过早思考一道很难的难题。
(3) 后来听朱泽园的提议:由于一个人的难点造成短路,应该一个人解决,不
有道是让全队都陷入混乱中。
本人觉得我们一贯选择写别的一道难点首要有五个原因:一是B 卡住的来由相比
特种,不是大家花时间就能制伏的;二是I 的算法相比较清楚,格外平静。
等I 过了之后,B 的Clarification 出来了,Judge
换了一组样例。于是伊始调B。
B:给出16 个数,将她们排成十字架形,使力矩平衡。求真相区其余方案数。
十字架总共有4 个“臂”。首先找出一个“臂”的兼具意况。然后将等值的无
重新的集合成四个相对的“臂”。然后从16 个数中选出8 个,将他们当作一组,
其余8 个作为另一组,那种方案的总和为前8 个成对的方案数乘后8
个成对的方案
数。最终把方案数求和除4。
大旨属于搜索题,而且定期更加紧,由于搜索难点的优化空间往往很大,而且
又是多组数据,所以很简单造成TLE。在调对样例后TLE 了一次,革新了算法后
出于开小数组RE 了四遍,终于在第一遍提交通过了B 题。
记得高中时四遍在网上做题(只记得是xreborner
出的题材)的时候,比赛一始发
就写一道限期很紧的难点,推测开端先后的不利是尚未难题的,就是作用比较低;
不过,在不断优化的过程中改错了先后,导致1 个小时过后当程序不TLE
了今后,
程序变成了WA。这样使得信心完全崩溃。
听了累累校友钻探之后,发现众多军旅就完全卡在了B 题上。未来对那种题材
不得不倍加小心,现在大家还尚无什么样尤其好的方法。而且,B
题的样例只具有测试
性,不享有调试性,编程时务必更加细心才行。
那儿差不离才1 个多小时,我们好像顺遂地因此了5 题;不过现场的动静并没有
其他优势可言,Shangri-La 在几分钟后经过第5 题,七个武装的罚时只相差1
分钟。
随后我们到达了第二段艰苦的时日,主要缘由是鬲融把F 的题材看漏了一个条
件,与胡伟栋琢磨后误以为那几个题比较易于,很快那题出现Run-time Error
好在重
读题后发现错误并随即丢弃,没有再浪费时间去把Run-time Error
调成WA。假诺
马上死做此题则后果神乎其神。
在鬲融和胡伟栋分别读F 的先后以及难题的时候,由于后天结余的难点都相比较
复杂,大家选择了一道相对清楚的题材H 继续做。
H:对一个汇聚举办三种操作:插入一个数和通晓MOD Y 最小的数中最后一
个数。
出于数字的范围是[1..500000],先选拔一个适宜的M。当Y<=M时,通过插入
时一贯保存来拍卖,当Y>M
时直接枚举,用并查集求一个元素的存续。那样每一
次操作的岁月复杂度是O(Sqrt(500000)).
但是,伊始接纳M为1000,并从未充裕揣摸复杂度的平衡性。开首大家认为
并查集的常数较大,不过后来感到到并查集的常数相对小片段,于是把M选为
500 就过了。后来在同出题人交换的时候,被告之M取在400-800
的限制内都可以。
其次段辛勤的时期的原委想必非可是难点看漏,也鉴于标题难度已经增加。
好在及时专门是当H 的程序TLE 之后,我们都比较萧条,相信自己H 题的算法是
科学的算法,只是参数的挑选不够客观。那种考验在平日貌似是很少蒙受的,经受
这一次考验之后,再遭遇类似的难点,大家相应可以更鲜为人知一些。
过了H 之后,鬲融已经重新确认了J 的题意,随着气球的率领,我们决定砍下
本次竞赛最大的“纸老虎”:J,而做J 的经过中胡伟栋一直在想G,已经大概得
到了算法的框架。
J:给出一些数的尺寸限制的关联,求更确切的关系子孙后代判断为争论。
更换成图的模子,不断迭带调整,直到不可以调动甘休。当然这题由于大小限制
关系中既有’<=’还有’<’,所以要求看清XI<XI
是不合规的。时间复杂度O(N
3)。
J
题的数码输入输出比较复杂,可是难题自己很不难。那题对编程能力指出了很高
的要求。
通过J 题之后,看了一晃board,当时Shangri-La 唯有5 题,可是在我们还没
有反馈过来的时候Shangri-La 就也同样7 题了,罚时上大家超越4 次提交。
在比赛的前200 分钟,我继续了TCCC2006 的佳绩状态。大家合作默契,在面
对BHJ 那样琐碎的难点时,队友会提前把要求留意的底细总计在纸上,整个
进度
都保持得很平整。其余,鬲融和胡伟栋在自家做每一题时都准备了很合适的测试数据,
大大减小了自己测试的年月并很有效地增强了付出正确率。由于剩下的题材难
度明
显高出一个水平,在经过7 题时的罚时超过是终极收获竞技获胜的关键砝码。
近来结余的只有E,F,G 三道没有队通过的题材了,其实说到底也没有武力通
过。我们早已读错过F,由此本次独家品尝了E 和G,不过都战败了。那里大家曾
经研究过先做E 仍旧先做G,当时面临的精选是:E
的复杂度推测较高,不知优化
后能如故不能通过,而G 的算法性更强,胡伟栋照旧没能完全清楚怎么缓解,完成的复
杂度高于E。大家本次带有赌博性的选取了E,并不曾仔细考虑即使E 的光阴要求
过于严格会现出哪些难点(可能与B 的相持轻松通过有自然关联),在随后的比
赛中大家应当专注周密考虑,尽量挑选题意清楚并且复杂度简单猜想的标题。
E:带限制的有向图的第K 短路。
主旨其实有规范的A*算法,大家也拔取了这一个算法。但由于复杂度过高,我
们的先后平昔TLE。据Judge 说那题对时间的渴求尤其严酷。
G:在一个树林的若干点布置仪器,仪器有效果范围D,仪器之间的偏离必要
超过等于D,求最大的遮盖长度和微小的权。
主旨可以使用二次方状态的动态规划,类似CTSC2004 的一题。我和胡伟栋讨
论后成功想出了天经地义的法子,并且在结尾时刻写出了先后,而鬲融和胡伟栋则出了
一对测试数据,将数据调过后时光已经很忐忑了。首先是因为忘记优化floyd
超时了
一遍。在优化了floyd
算法之后,照旧没有设想到图不联网的情状,未能在较量结
束前调出。
F:给出一些公理,要是和定理之间的关系,依次尝试,推出尽可能多的定律。
在同样情形下需求使用的倘若最少。
主旨可以用小小成本最大流解决,但是正如便于完毕的网络流算法都很难在时
限内出解。
现在看来,EFG 三题中的E 没有竞技中想像得那么难,当时比赛中惨遭巨大压
力的熏陶没能攻破此题,不过FG 题即使出现在CTSC 难度的比赛上也相当合适。
竞赛截止:罚时险胜
竞赛停止时大家与Shangri-La 同为7 题,香港(Hong Kong)哈工大一队最后也因而了7 题,我
们依靠罚时的薄弱优势险胜。经过惊天地泣鬼神的300
分钟,大家总算赢得了梦乡
以求的2006 巴黎赛区亚军。Mobile 罗布ot
凭借着新加坡赛区的争冠,已经可以认为
得到了进军2007 日本首都世界半决赛的门票。
竞赛截止后来看了无数南开的老友和吴永辉先生,吴先生要么和原先一样,
玩笑开个不停。那一个武大的老友赛前由于是加入出题,我们直接从未见到,颁奖
仪式此前,大家总算有时机在后场一起聊天。但是聊天那些日子中,我和b142857
错过了郭老师在颁奖仪式前开展的“点名”(当时郭先生需要我们上去讲解标题),
实际上不好意思。
总结:
先是向Shangri-La 致敬,固然在结尾一刻,相信大家都还依旧有机遇,棋逢对
手也是自个儿ACM生涯中的一大好事。当两支部队都经过7 题的时候,排在第3 名的
枪杆子才刚刚5 题。也就是说,我们两支部队实际只用了2/3
的较量时间就锁定了上
海赛区的冠亚军。
日本东京北大一队最终也经过了7 题,竞赛先河时大家就专注到了南开开场时分外
不顺畅,可是顽强的南开一队多加商量,在最后一时辰也成功通过了第7
题。在那
里向清华致敬,开场的各样不利不亚于我在南京2005
时的起跑,你们能够沉着应
战,济河焚舟的神气一贯值得大家学习。当时哈工大一队中有一位出自西藏的健儿辛
韬,记得NOI2003 从前大家有很多次格斗都以自我败北告终,后来不时在重重网上比
赛中探讨,2005 年ACM
京城赛区也有你熟习的人影,在南开早有听说你在清华的
优秀战表,祝福你未来更进一步好。
这一次比赛的命题工作是由北大学院出任的,北大大学的命题特点与东欧的命题
风格很相近,题目标算法性偏强,标题对程序运行速度须要广大高。
根据panda 的布道,香港(Hong Kong)微软ATC 队鉴于局地合营的失误,最后只通过5 题,
不过也是前10 的武装之一。此外,临沂一中队也百发百中通过5
题排进前十。GotoFly
经过第3 题的时候还排在第3,但是后来卡死在J 上了,有些心痛。
后来,分配常规赛名额的时候,巴黎赛区获得了10 个季后赛名额,那个数字
相信也是那一个年来的之最吧。
那是一场值得回看的较量,出席2006 香港赛区的强队实力远不止几年内的各
大赛区,可以站立在香岛赛区的万丈领奖台是Mobile 罗布ot
拿到的万丈荣誉之一。
经验了新加坡赛区大战的洗礼,接下去的罗利赛区出场的则是更成熟的Mobile
罗布ot。
附日本东京赛区名次:
1 Tsinghua University => Mobile Robot 7 617
2 Tsinghua University => Shangri-La 7 709
2 Shanghai Jiao Tong University => Lacotix 7 1034
2 Fudan University => Symphonic Rain 6 924
2 Shanghai Jiao Tong University => Prodigies 6 957
2 Fudan University => ShuangYY 6 1098
2 Xiamen University => btALT 5 534
3 National Taiwan University => puyo 5 563
4 The First Middle School of Wuhu => WHYZ 5 652
4 Microsoft ATC Shanghai => Core-Stop-Dump 5 729
4 Zhejiang University => Golden Keyboard 5 817
5 Peking University => PKU_T2 5 819
6 Zhejiang University => Dasher 5 956
6 East China University of Science and Technology => Redfield 4 325
7 Tsinghua University => GotoFLY 4 367
7 Zhejiang University => sago 4 392
7 National University of Defense Technology => Robust 4 438
8 Zhongshan University => ZSU-Tanglha 4 512
9 Tongji University => Revenge 4 559
10 Shanghai Jiao Tong University => H-E-A-T 4 600
10 Xidian University => ACMore1 4 602
11 Wuhan University => Moonmist 4 723
12 Zhongshan University => ZSU_Olympus 4 765
12 Nanjing University of Science and Technology => Narcissus 4 774
13 Northwestern Polytechnical University => 1010 1100 4 845
14 Harbin Institute of Technology => Gaminerie 3 200
15 Fudan University => White * [ Bear + Dew + Cloud ] 3 337
15 Zhongshan University => ZSU-Everest 3 360
15 Hefei University of Technology => Happy For Unpain Teeth 3 406
16 Beijing University of Posts and Telecommunications => Neon 3 442
17 Shenzhen University => Aspire 3 453
18 Harbin Institute of Technology => Corsair 3 457
18 Nanjing University of Science and Technology => backbones 3 461
18 South China Agricultural University => scau_update 3 468
19 Huazhong University of Science and Technology => rodimus 3 480
20 Ningbo University => ACHC 3 505
21 Peking University => www_pku 3 513
21 Fuzhou University => OrOrz 3 520
22 National University of Defense Technology => Puzzle 3 520
22 Donghua University => Gespenst 3 535
22 Hunan University => Footmen 3 535
23 Tianjin University => TJU_Rocket 3 563
24 National Taiwan University => ABCDE 3 568
24 Nanjing University of Aeronautics and Astronautics => ZipFish 3
575
25 University of Electronic Science and Technology of China =>
transistor 3 599
26 Shanghai Jiao Tong University => Lucifer 3 608
26 Zhengzhou University => ZZU_cheapwine 3 650
27 Wuhan University => Silence 3 685
27 Hangzhou Dianzi University => MP3 3 687
28 Jinan University => JNU-FLY 3 830
29 Huazhong Normal University => Neptune 3 857
使用沐日空闲之时,将这几年GCJ,ACM,TopCoder 加入的有些根本竞赛作
个回想。GCJ2006,ACM2005 和TCCC2006 之后,2006 年对于自己来说是一个大丰
收,晚上发ACM 西安2006 吧。
2006 年ACM-ICPC(下)——古村落布里斯托
艰辛的ACM2006 巴黎赛区截止之后,大家原先以为北大会选拔此外3 支部队
在座纽伦堡赛区的较量。况且,大三的学科的试验任务很重,大家也就截止了安排的
期限磨炼。大概在25 天之后,12 月20
日左右雷暴式接到邬先生的公告,准备出发
列席ACM 埃德蒙顿赛区竞赛。大家的2006 Charlotte之旅也就是在那正如仓促的预备中开
始的。
布里斯托赛区此前,大家从不定下明确的靶子,竞赛进度中各处都采纳了追求稳健
的方法,当时也是为着幸免一年前的维尔纽斯喜剧重演。
奥兰多的较量没有太多快乐的AC,没有惊心动魄的排场,所有进程都在近似旅
游的空气中得了了。作为Mobile 罗布ot
的结尾世界一战,那里也作一个简便的回顾吧。
出于本次难题又是Srbga(刘汝佳)命题的,我最后也有意无意列举一下自我计算的他命
题的性状吗。
竞赛进度:
2006 年交大同样派出了3 支军队参与毕尔巴鄂赛区,除了Mobile 罗布ot(我,
geworm(鬲融)和wd.h(胡伟栋))之外,还有Panacea(OpenGL(唐文斌),zhy(周源)
和liuhe(海昏侯),要是您首先立时见这几个词就领悟是什么样意思,我相信您一定准备过
GRE 吧?)以及一块参与过2006
日本东京赛区比赛的GotoFLY(zcgzcgzcg(朱晨光),
wangjun(王俊),tedcn(龙凡))。
2006 年春日是自我先是次来到奥兰多,刚下轻轨就深刻感受到了马普托的古村气息。
到达饭馆之后,大家做得第一件事情就是玩,映像很深的是鼓楼,钟楼还有小雁塔。
咱俩做的最主要的作业可以用GotoFLY 的4 个大写字母GFLY 来代表,就是“公
费旅游”。
竞赛之前的夜晚,大家认真谈论了比赛中动用的国策,参预奥兰多赛区没有太多
价值观强队,大家一致认为应该先行使用比较稳健的方针。赛后有比较简略的总计:
依照定点的不二法门,鬲融从A 初步读,胡伟栋从J 先导读,我准备编程的条件,
下一场从中路选取题材读。与日本首都赛区相比较,比较顺遂的是自我一下就来看了一道比较
简单易行的标题B,于是我及时写了B 题。
B:使用火柴棒拼接数字,给定n,m,求使用不当先n 根火柴棒拼成的m 的倍
数中最大的数字。
主旨首要的合计是动态规划,方程很简单得出,时间复杂度O(nm*10)。但是
大旨有七个难点:
(1)怎样赢得最大的数字?标准的点子是应用BFS,搜索的长河中务必足够注意
探寻的各样,不过如此已毕很简单出错。我注意到了n<=100
的尺度,由此结果不
会超过50 位,于是自己动用3 个int64
来保存结果,那样既贯彻简单又不易于错。虽
然程序常数相比较大,不过不至于导致超时。
(2)无法不使用火柴棒,而数字0 也亟需火柴棒来拼成。例如n=5,m=97 的结
果是-1,而n=6,m=97 的结果是0。
ACM 竞技的率先题的拔取对竞技的历程影响很大,此次竞技很成功地运用了
很妥当的算法。
E:标准的课堂睡觉难题,求最早所有人不睡觉的时刻。
简单易行的模拟题,而且定期很宽松。
E 其实是最简便易行难点,不过由于我的低级错误,不仅收获了三遍罚时,而且浪
费了爱惜的时间。好在即时可比冷清,很快校勘了错误。
D:对于一个不超过100*100=10000 的表明式,能够在里面参与*来表示其余
字符,假设一个表明式只可以和唯一的等式对应,则称为A 类表达式。给定一个表
达式B,必要通过改变最少的字符使它变成A 类表明式。
宗旨使用了两回搜索再找找的章程,可以使得控制程序的速度。估摸时限难题
后接纳先交付节省了不少年华。
J:给定一个4*4 的网格的边框图形,问是否足以经过在4*4 的网格上放6 个
2*2 的方框形框获得。
H:给定一组旋转后的乐谱及开首音符及完工音符,求原始的音符体系。
发端胡伟栋没有观看旋转的角度是整数的基准,于是推出了可以缓解实数角度
的数学公式。不过出于公式须求考虑的状态相比较复杂,幸运的是我们采纳了枚举角
度再判断的方法。
写了读入部分之后,看到Panacea 过了H
题。鬲融重新读了难点,发现了角度是整
数的基准,于是稍微修改就得到了科学的次序。
要旨要求判定的条件很多,必要考虑得很密切:
(1) 先把坐标依照X排序。
(2) 通过初始音符及善终音符获得sd,判断sd 是或不是在1 到5 之间。
(3) 判断附近三个字符的离开是或不是在sd 到5sd 中间。
(4) 判断每个点的坐标是还是不是可以对应一个音符。
F:求3 维空间的Voronoi 图,输出每个Voronoi 块体积占的比例。
胡伟栋提议了焦点的不利算法:分割立方体。如若一个立方的8 个极点都到
一个点以来,那么那么些矩形内的所有点都到那一个点以来,否则就分开那些立方体,
直至立方体的体积少到自然水平甘休。
千帆竞发先后的精度不够,后来胡伟栋提议了一个启发式的剪切立方体的艺术,思
想就是驱动四个立方的分割面以尽力而为大的票房价值穿过Vorinoi 平面。程序的意义很
好,而且那时时限也早已放宽,于是顺手通过了F 题。其实本题蒙特卡罗法也可
以过,大家也想到了这么些主意,可是由于自由进度写的功效有难题,导致精度不够。
通过F 题的时日是270 分钟,封版时除了Panacea 通过4 题,其余军事最八只
有3 题。当时Panacea 正好坐在大家私下,很心痛他们卡在了D 和G 上,最后也
唯有4 题。最后半钟头大家也从没品味H 或者A,因为其余队伍容貌很难在终极一小
时通过4 题。大家就概括尝试了五回C 就默默地守候着巴尔的摩赛区比赛的完毕。
末尾大家由此6 题名次第一,由于已经获取了巴黎赛区的季军,不列席ICPC
的名次,可是依旧获得了Solaris 杯。
总结:
奥兰多的ICPC 季军是香港(Hong Kong)高校的T2(rainer,dzx 和cici),后来她俩凭借马尔默
的争夺第一名战表进入了2007 年的五洲季前赛。T2
在最后一钟头表现最为强悍,顺遂通
过2 题一举超过了GotoFly 和Panacea,而且最终几分钟还很有期望由此H,赛后
和rainer 研讨之后发现算法相差无几,可能就是一些小细节缺陷吧。2006-2007

度的ACM 竞赛,从上海到博洛尼亚,还有日本首都的常规赛,Mobile 罗布ot
每一次竞技都能
来看了T2
熟稔的身形。大家在封版之后平时由于压力较大很难攻破标题,他们在
封版之后的冷冷清清心态十分值得大家的就学。
GotoFly 与T2 一样通过5 题,由于5 分钟的罚时逆风局位居第三,Panacea 通过4
题依靠罚时优势排在第四。两队都不足一些命局,很心痛。其余映像很深的是,坐
在对面的朝鲜队通过了4 题在ICPC 中名次第2,假设奥兰多可以多一个名额的话,
她俩就可知产出在季后赛比赛场所了。
纽伦堡赛区是Srbga(刘汝佳)出的题目,从高中时代就从头做了Srbga 出的题
目,西安赛区的难点又一遍展现出了刘汝佳命题的众多主要特征:
(1) 要是Srbga 堂弟出是一套标题,那么你会肯定觉得题材拿在手上鲜明重一
些。Srbga 堂哥出题很强调标题叙述如故故事的完整性,他很少使用一些僵
硬的难题模型和讲述。有时读着她出的题材更像是在读小说,欣赏故事。
理所当然,由于Srbga 小叔子出的标题叙述完整,刚得到难点的时候会倍感很难
左手。我们很不难觉察没有一道难题简单上手。用数码表达,比赛起首时
的空机时间偏长。
(2) Srbga 二弟出的难点和世界季前赛的题材风格相近,标题多半对编程能力
提议很高的须要,相比较之下对算法的渴求不是相当高,考察的都是相比基
本的算法。假如用一个字形容就是:野。
(3) Srbga 小弟出的标题对算法的体察范围分外广,纵然对于某非常的算法要
求不高。有时还必要很强的整合算法能力。
(4) Srbga 三哥出的题材中很上心数据的宏图,例如C 题中尤其生成了最为的
景况,J 则利用了近乎20000 组数据。一般景观下,不通过精心设计的人身自由
算法会吃尽苦头。
2006 年的Mobile 罗布ot 的ACM 分区赛比赛职务现已整整扫尾了,2006 对于
Mobile 罗布ot
来说是丰收的一年,大家圆梦了香港和罗利的双亚军。在紧接着的冬日,
俺们加速训练准备日本首都的季前赛。
行使假日空闲之时,将这几年GCJ,ACM,TopCoder 参预的一对至关主要竞赛作个
回溯。回想了GCJ2006 和2005 年的ACM 之后,转向TopCoder 的比赛呢。我在场
的最早的TopCoder 赛事是TCCC2006。
TCCC2006——与世长辞之组
TopCoder Collegiate Challenge(简称TCCC)是TopCoder
一般在冬日举行的面向全
世界在校学员的程序设计大赛,2006 年的TCCC
在利雅得举办。从京城到台北
的航空只必要11
个钟头左右,所以不至于那么疲劳。路上所有都很顺遂,很感谢
OpenGL 的唤起,对于当先8
个小时飞行自带拖鞋和枕头对自家的话仍然很重点的。
TCCC2006 使用的科班的TopCoder 现场比试格局,竞技有48 名健儿加入,首
先48 名健儿被分成16 个人一组,每组分别举办季前赛,前2
名间接升级决赛,3-
6 名晋级wildcard 竞赛,wildcard 比赛12 人中的前两名填补决赛的最后2
个名额,
决赛由8 个选手参加。TopCoder
现场比试中很首要的一个翻新是:每名比赛选手
在观众席前都有一个一起的显示屏,这样观众得以看到选手任曾几何时刻做的事务,极
大增加了互动性。
TCCC2006 的Room 1 和前面的Final Round 都可谓是与世长辞之组。现在就想起一
下那两场激烈的较量吧。
Room 1:
关于3 个房间的分红,TopCoder 依照注册停止时选手的Rating 分布蛇形分配。
可是TCCC2006 的房间实力分布极不平衡,我与上届冠军tomek,知名选手reid,
Egor,halyavin 还有Rating 不高只是实力极强的Ying 和ardiankp
同被分到了Room
1,赛前Room 1 成为公认的逝世之组。
在台北,我和师兄Macsy(张一飞)同一个屋子,很谢谢师兄的关注,我
那几天休息的都很好。要知道假若性交的人有10
小时左右的时差的话,一人必要
很小心才能有限辅助不影响另一人的苏醒。
Room 1 在自己抵达美国的第二天中午展开,选手允许提前30 分钟准备一些少不了
代码。不过现在我们都比较喜欢学习Petr
那样一行代码都不打。上面就是竞技的
过程:
250 分难点是:给定n(n<=50)个整数AI 和一个阈值d,计算n
个整数所有排列
PI 中满足|API-API+1|<=d 的排列中,所有差异或许AP1
的个数。那题最专业的点子是
动态规划,基本考虑是把n 个整数排序之后,计算两条相邻元素不超过d
的队列。
自家使用了一种更精致的算法,把n 个整数排序之后,对于AI,如果AI
可能作为排
列的第三个元素,那么AI
必定在某一个趋势(大小)一而再而在另一个倾向每间隔
多个要素相连。那么些算法比较简单落成,可是正确性注明相比较难,甚至让人第一感
觉是错的。我写完程序测试了拥有样例都毋庸置疑就交由了,243
分。提交未来我又测
试了诸多数目,并在纸上尝试申明正确性。
赛后,我看了互连网上的座谈记录。在我付出250 分题之后,立时受到了misof
的可疑,他认为自己的算法有标题。据Macsy 学长的想起,OpenGL
在我显示屏前看我
写完程序,也觉得我的算法是错的,可是新兴她俩谈谈之后发现没有反例。
关闭250 分难题之后,我正要发现到Room 1 的3 题分数不是250-500-1000,
而是250-600-900。现在看来,对于250 相比顺利的情景,应该先做500,若250
不顺利或者想大胜的话,可以先开1000 分。当时不曾什么经验,我认为900
比600 应该不难一些,于是就打开了900。
900 分难点是:给定一张n(n<=10)个点的带权有向完全图(也就是n2
个实数)
和一个衰减周密p,求一条经过d(d<=10)条边路径(不须要有限协助不难路径),须要
那条路子的指数衰减长度(指数衰减是指第i 段的长短乘以pi-1
然后求和)最相近
1000。那题假设运用穷举法,就须求1010 左右的统计量,在TopCoder
的测试机上
也不可能透过,由于路线长度很不难超越1000,所以很难找到多项式时间的动态规
划。我立时有了一个设法——双向搜索。对于长度为d 的途径,其实可以当作从
某一个点p
出发的一条反向的尺寸[d/2]的路线和一条正向的d-[d/2]的路径,对于
定位的节点v
来说,那种五个趋势的途径都不当先n[d/2],那样只要枚举一个大方向
的路径然后二分查找另一个倾向即可。复杂度是O(dn2+[d/2]) 。
当场比试调试环境不是很好,我花了许多年华调试以发现先后中的错误。提
交之后690 多分,还不到700。可是对此900
分的标题在那种压力下仍可以接受。
交由之后我花了15 分钟左右测试,没有发现错误。于是就准备做600 了。
600 分难点是:一道经典的数学题,给定一些行情叠放的平整,总括顶层盘子
的最大可能大小。其实算法不是很难,只要二分顶层盘子的轻重,然后依次贪心计
算来判断底层是不是可以知足即可。只是贪心的时候要考虑二种意况,一时想不亮堂。
自身当下已经感觉到很疲惫,思路不是很通晓,最后40
分钟时间也没能调试通过。那
题过于琐碎,Room 1 中最终没有选手通过600 分题,并且成功了一个鼓舞的
Challenge 阶段。
Coding 阶段自己和tomek 采取了一心分化的政策,我跳过600 直攻900,而
tomek 在600 中挣扎了很长日子才废弃。Coding 阶段停止时,有4
名健儿提交了3
题。我依靠速度优势超越同样提交250 和900 的tomek 35 分左右。
Challenge 阶段开头时,我盲cha(blind
challenge)了一个结尾每日提交的900
分先后,然则由于自己选拔的数目实在太弱,失去了25 分。那样自己和前边的tomek
只相差10 分左右了,所以我主宰只要tomek 不动,我也不动了。其实,当时
tomek 已经清楚自己的900 是错的,Challenge 阶段他估算已经屏弃了。我的
Challenge 阶段最后就以-25 分结束。
未来的Challenge 就是Ying(王颖)显示勇气和智慧的戏台了。他Challenge 掉
了独具提交的600,凭借225
分的加分超过了自我,排在第一名。那样比赛的花样也一
目驾驭了,7 位选手提交了900,我依靠速度优势超越第四名reid 当先100
分。只
要本人两道标题可以Passed System Test 就足以进入Final Round 了。
System Test 从前,我和Ying 钻探她“超神”的Challenge 阶段。那是自我首先次
参与TopCoder 的现场比试,发现System Test 结果突显是根据System Test
从前的
排行倒序进行的。测试到本人时,除了tomek 的4 名健儿的900 都过了。展现自己的
结果时,八个绿框闪烁了很久终于突显出了三个大大的钩,我到底可以欢呼庆祝胜
利了。我眼前的Ying 也两题全过了。那样大家两位中国运动员得以在归西之组携手
并发,这场较量真可谓是华夏运动员的获胜。Reid 只好在魏尔德card 赛再作努力,
tomek 则被一直淘汰出局了。
Final Round:
接下去的二日里,我见到了Room2,Room3 和魏尔德card 的比赛。第2 天早上
咱俩加入了TopCoder 赞助的Laser Tag
游戏,大家具备中国人组合了一队,我的发
挥很差,原因是以此娱乐与CS
不一致,选手头上没有感光器,而自己爱好碰着人就攻
击尾部,所以狭路相逢多半是本身战败。活动中,我有幸结识了很多Dev 的神明,
当时出于vividmxx 没有临场,magicpig 和PE 的竞争很激烈,最后PE
得到了“广东
高等高校建校100 年来第三个TCCC 季军”。记得赛后本人uncle 来到现场,我uncle 是
湖南学院本科毕业的,magicpig 见我uncle 第一句话就是“四川高校建校有100

正史了吗?”汗死了。此外zjq 也获取了Design 的亚军。
其三日清晨Championship Round 开首了。决赛时,场合里设置了好多视频头,
可以说大家的其余举措都在严密监视下了。那回自家提前确认了难点分数是正经的
250-500-1000
的遍布。插足决赛的健儿除我之外有:andrewzta,ardiankp,bmerry,
Eryx,mathijs,Petr
和Ying。面对决赛选手的实力,我已经没有意义定一个近乎于
“保几争几”的目的了,努力发挥自己的水平是最应该做的。上边就是比赛的进度
了:
250 分难点是:给定n 个正三角形,每个终端都有数字,选出6 个三角拼成
一个正六边形,必要附近的数字必须一律。三角形允许旋转,统计可以取得几个
本质不一样的正六边形。标题很长,我仔细读了一回才发轫写,算法很清楚,就是枚
举六边形要旨和四周的7 个数字,然后判断是不是有丰裕的三角。在认清本质不
同的时候犯了一个错误,调试了几分钟,提交之后唯有215
分了,看了弹指间排行榜,
Petr 有232
分之高,其余选手都还并未交给。测试了几分钟发先生现先后的运作时刻不
是很稳重,很简单抵达0.8 秒左右,测试了15
分钟之多才逐步放心下来,因为基
本上所有数据都0.8 秒左右。赛后Macsy 告诉自己,我的顺序速度瓶颈是在set
的判
断,所以时间比较稳定,不会晚点。我立即的动摇和尚未经验浪费了足足20
分钟
的时间。
安分守纪赛前的安排,我此刻应该打开1000 的难点的,然则出于投机对250 没有
信心,而且求稳思想比较重,我先打开了500 分的标题。现在总的来说,开500 分的
标题并不算错误,其实在开拓500 分难点的时候,与Petr 的歧异不是很大。
500 分难点是:给定一个机器人的位移命令种类,须求测算截至时机器人的位
置。由于活动体系中允许()那样的重新操作,直接模拟是晚点的。那类标题标科班
算法是应用矩阵乘法,由于事先对于此类难点从没经验,没有未雨绸缪好就起来写了,
导致矩阵处理失败。我坚决废弃了调节,换用一种记录中间结果的物色方法,写完
的时候曾经唯有280 分了。更要紧的是本人曾经没有时间出击1000
分了。提交之后
排在第3,前面是Petr 和Eryx。
1000 分难点是:给出一个排队取菜的模子,总括一个等待时间的排队序列。
再者对于各种答案的景色,必要测算字典序最小的行列。标题实在不是很复杂,集
合动态规划就足以化解,可是模拟取菜进度时索要分外注意细节。Petr
提交了一个
660 分左右的主次,Ying 则在结尾一分钟提交了400+分,排在第2。
Challenge 阶段显得很枯燥无味,前二日大发神威的Ying(+225)和Petr
(+300)都没有品味Challenge,整个Challenge 阶段没有其余一个Successful
Challenge。
System Test 结果出来了,在bmerry,ardiankp 和andrewzta
都只经过一题的结
果出来之后,排在我前面的mathijs 两题都Pass,随后我的250 和500 也都Pass
了。
不过,名次在自己事先的Eryx 和Ying 的500 分和1000 分都Failed System Test
了,
自家弹指间升格到了第二名的岗位。但是尽管如此Petr 的1000 分挂了,不过她依然依赖
250 和500 的进程获得了亚军。
在此间说一下1000 分的真实情况吧,因为这几个时间来对于TCCC2006 Final
Round 的1000 分难题有广大例外的布道。竞技结果中显得没有选手通过1000
分题,
一旦条分缕析分析测试结果,Petr 的次第由于超时出错,而Ying
的程序由于一个地点
不曾清0 而招致错误,确实很可惜。因为一旦Ying 的1000 能够Pass
的话,他将
是TCCC 的亚军。但是Ying 的算法犯了与造成Petr
超时一样的荒谬,他们的动态
规划程序比正规方法多出一个n 倍的时间,我已经成功生成了一个用例,可以让
Ying 和Petr 的次序都超时,这些事例已经获得了Ying 的认同。要求提议的是
TCCC2006 是TopCoder
的测试机的快慢仍旧很慢的,三个程序一旦在前几日的电话机上
运行可能只必要1 秒左右了。
竞技之后和uncle 到downtown 游玩了瞬间,参加完颁奖晚会,第二天就回国
了。
总结:
TCCC2006 是本身先是次参加TopCoder 的现场比试,很幸运可以在这么多的率先
次中就进来决赛并且得到第2 名的大成。很感谢同参加比赛的同校Macsy,
OpenGL,Ying 还有PMH
的关注和拉扯,你们在自己比赛时全程在场边,让我深感很
温暖。
其它,我还有幸认识了visualage,现在她现已是arena 的决策者了啊。记得她
和OpenGL 在Room 1 的Challenge
阶段通过大声叫粤语(在国外,这是最好的密码)
告诉自己tomek 的900 是错的,可惜我从未听到。
TCCC2006 对于中国的话是不小的收获,中国运动员占领了Dev 比赛,PE 得到
“新疆高校建校100 年来第三个TCCC 季军”,magicpig 和zjq 分获Dev 和Design
的季军,也就是说中国承包了具有季军。在竞赛之余,我很欣喜认识了比比皆是
TopCoder 的朋友。
Petr 在决赛中显现了非常完美的情状,TCCC 的争夺第一标志着Petr 收获了2006
年的大满贯。Ying
也应用了很有理的国策,只可惜他的赌博由于运气差不多败诉。
本身使用了比较保守的国策,在装有决赛选手中名次第2,那也是本身在TopCoder 的
当场赛事中的最高排行了。
TCCC2006 我很谢谢亲人的关心,父母凌晨很早起床查看自己的比赛结果,而
uncle 还专门赶到现场为我加油。这几年的TopCoder
现场比试的赞助商列表里都能
找到American Online(AOL)的身影,TCCC2006 是AOL 唯一三次开展了3
个小时左
右的全程直播,父母和uncle 都在互连网上看出了实地的形象直播。
TCCC2006 我神奇地保持了100%的正确率,我个人觉得TopCoder 现场比试对
正确率提出了更高的须要,大家不必太在意Coding
星等的那么些高分,只要自己的
次第是正确的,就是成功的。
利用沐日空闲之时,将这几年GCJ,ACM,TopCoder 插足的片段主要比赛作个
回顾。首先是GCJ2006 的回忆。
Google Code Jam 2006
反复:
谷歌(Google) Code Jam 2006 是自己先是次到米利坚到场现场的顺序设计比赛。谷歌
Code Jam 2006
的比赛地方设在了London,本次London之行从前的签证出了不小的难题,
此处极度感谢我们对大家的关心,更加感谢吴总(wyy)和鲁小石的支援,使自己最
终踏上London之旅。
从上海到London的宇航时刻是13 个半钟头,由于是首先次做超越8 时辰的飞机,
没有怎么要求的经历和准备,路途至极疲劳。一到商旅就睡了,结果由于手机铃声
的时光使用的是东方时间,差了12
个钟头,一觉把具备事务连晚饭一起都睡过了,
无论吃点东西就一连睡了。之后的所有现场比试自己都养成了提前睡觉的习惯,以保
证丰裕的体力。
竞赛进度:
竞赛时精神状态还算可以,可是分配了竞赛房间之后发现自己和tomek 分在一
个房间,真是很悲哀;在和边际的zhuzeyuan 抱怨的时候,发现她和Petr
一个房
间,互相相互吧。
上边就是竞赛进程了,总体来说竞赛进度比想象的困顿,不过实在在System
Test 从前的结果要么很乐意的,先容易描述一下3 道标题吧。
250 分的题材是一道平面极值问题,给定n 个点,求一条直线,使得n 个点到
那条直线的y 方向截距总和最小。我想起起金凯在2003 年集训队杂文中报告中讲
到的很类似的一道标题,记得一个主要结论是那条直线一定经过三个点,尽管标题
有点差距,不过高速得到了同等的根本性质:那条直线一定经过七个点。那样很容
易得到一个O(n3)的算法。
500 分的难点是一道反Hash 函数难题,给定一个Hash 函数和x,求一个细微
的非负数y
使得H(y)=x。揣摸了一下,单向搜索须求26^8,于是自己改用双向搜索,
这么就改为了26^4。但是贯彻进度比想象的纷纭很多,提交了后只有280
左右了。
事实上,那题有更简单的数学方法,tomek 的次序有450+。
1000 分的题材是关乎卷积函数和计算反函数的题材,通过转载变成线性方程
求解难题。当时碰着现场氛围的熏陶多少打鼓,浪费了诸多时光,提交未来550
分左右。其实,当时有的原理难点都未曾想知道,但是新兴和Ying(王颖)经过讨
论验证都是不利的。
Coding 停止从前Petr,tomek,Ying 和andrewzta 都付出了3 题,其中Petr 领
先得比较多,我和其余3 人差别50 分以内。
Challenge 阶段开首未来,我是因为500 分题自己行使的是双向搜索的算法,没
有在意到有些单向的检索加模线性方程的形式其实是正确,在10 分钟以内cha

了2 次。落后于上述的4 个人,排在第五。
但是上面的5 分钟发先生生了戏剧性的一幕,首先是Petr 的250 被cha 了,接着
Ying 的250 也被cha 了,那样自己面临那样一个景况:tomek 超过我100+分,
andrewzta 超过我30+分,由于自己和tomek
处在一个屋子,所以我做出了一个无畏
的主宰,就是challenge tomek 的1000
分题,我随便生成了一个随意大数额,在最
后随时提交了那几个challenge,系统重回了一个让人窒息的结果:successfully
challenge。凭借那50 分我一口气超过了tomek 和andrewzta,在System Test
往日占
据了头名的地点。
戏剧性的结果:
自家很幸运可以在第三遍到位现场比试时,就可知和季军这么接近,即使System
Test 可以百分之百Pass 的话,那可以认为是一场完美的比赛。
但是,整个故事就恍如是被刻意设计的均等,System Test 之后的结果使我目瞪
口呆:首先是250 分的难题,我是因为有一个地点没有即时运用double,而导致整
数越界;然后,1000
分的标题几乎是喜剧的参天境界,我在高斯消元的时候没有
当时把一个非同儿戏变量暂存,导致影响了结果,没有想到居然躲过了那么多大数目,
而是无法通过System Test。最后排在50 名左右。那多少个谬误至今一遍遍地怀恋。
最后Petr 获得亚军,Ying 亚军,andrewzta 由于500 挂了排在第3。
11 月的伦敦不怎么冷,我随大队人马协同去了一趟帝国大厦,景象很可爱。第
二天休息一下后与多少个中国运动员打了一会“找朋友”,第五次花旗国之行就为止了。
总结:
竞赛结果固然不是很美丽,可是对于第一次加入世界比赛的本身还算可以接受。
也终于为将来的比赛留下一些教训呢。
在帝国大厦上见识了豪门的拍摄功底,我是因为技术差没有拍到任何方便的肖像。
在较量进度中,首次见识了liympanda 的大将风姿,和panda 在共同延续笑口
常开,他随便碰着怎样动静都敢于,那点自己平昔在努力学习,可是一直做的
不好。不过panda 打牌的时候就不雷同了,总是喜欢偷看人家的牌,还炫耀自己
会说广西话,被Ying 和rocking 两位西藏选手狠狠鄙视了一番。
Petr 加上此前的TCO 和之后的TCCC,获得了2006 年的大满贯,可以算是历史
性的突破吧。汤姆ek 有些可惜,比完了还问我怎么cha 他1000 分的,呵呵。
其实本次比赛Ying 挺可惜的,其实Petr 的说明并不很好,如若Ying 运气再好
部分的话,历史从那时候就要重写了。然而Ying
如故显示了她超强的数学功底,让
人佩服。其它,来自清华的同省队友LemonTree 也收获了好成绩。
那就好像是自己最终五遍和xreborner 同场竞赛了(由于之后xreborner 退役了
很长日子,忘记GCJ2008 大家又见面了,谢谢Savior
的唤起),感谢您在自家高中
一时教师了本人无数编程技巧,我一向沿用至今。
附比赛排行:
Handle Score
Petr 927.02
Ying 811.21
andrewzta 761.56
halyavin 732.46
tomek 677.55
tomekkulczynski 634.69
pashka 590.05
asaveljevs 579.60
ainu7 552.23
misof 537.19
Egor 534.19
xOberon 517.65
reid 516.23
bmerry 498.01
LemonTree 497.27
MikeMirzayanov 490.32
PaulJefferys 481.89
monsoon 478.60
Andrew_Lazarev 475.39
tsjoker 454.86
kalinov 440.75
pparys 440.41
dyatlov 420.64
Michael_Levin 419.19
daveagp 403.39
malcin 399.55
kalmakka 397.15
kedaizd 391.91
cyfra 389.02
Macsy 387.38
Psyho 377.22
mhchan 374.90
jakubr 353.71
overwise 330.73
kia 283.48
ACRush 282.62
JongMan 261.44
IvanRomanov 251.33
DmitryKorolev 235.14
Revenger 234.54
elizarov 233.79
evgeni 232.44
antimatter 226.70
CatalinT 226.15
Jan_Kuipers 225.73
krijgertje 225.11
wd.h 221.28
w_ 218.82
zhuzeyuan 217.09
falagar 212.75
MegaS 210.88
gawry 209.13
liympanda 207.74
hyyylr 206.37
skatou 205.00
Vintik 204.09
jasonw 199.82
darnley 199.59
NPermyakov 199.54
aengus 196.67
embe 191.62
Yarin 186.89
NSI 185.22
AdrianKuegel 182.40
nicka81 181.01
HeaDacHe 178.77
VitalyGoldstein 178.37
kappa 175.40
HilbertRaum 168.29
DmitryKlenov 168.26
Abednego 165.51
Rocking 164.38
Per 163.41
Emilian_Miron 158.22
Aidin.Kashigar 156.94
lukasP 156.00
grotmol 152.34
gevak 142.55
nhzp339 130.61
NauCoder 107.71
lazyboy 98.73
WSX 56.89
Snail 25.00
Masao 0.00
blackmath 0.00
.Invader 0.00
Mg9H 0.00
smsorin 0.00
Rostislav 0.00
nya 0.00
lyc1977 0.00
xreborner 0.00
goo 0.00
soul-net -25.00
wintokk -25.00
Ulan -25.00
Bankevich -25.00
madking -25.00
fpmc -25.00
Soultaker -25.00
使用假期空闲之时,将这几年GCJ,ACM,TopCoder 插手的有的关键比赛作个
追思。明日到了2007 年底的东京(Tokyo),回想一下2007 世界季前赛暴发的趣事吧。
ACM-ICPC World Final 2007——Mobile Robot 日本首都决战
2007 年的日本东京ACM-ICPC 整个世界半决赛在樱花盛开的3 月底拉开序幕。成立了一
年的Mobile 罗布ot 凭借2006 年ACM 东京(Tokyo)赛区的冠军,代表南开参加了这一次ACM
盛会。
记得黄金雄教授在拉脱维亚里加2008 时说,ACM 准决赛的实力分布由原本的美洲称霸
逐步转向了当今的亚欧争霸。2007
年,同样来自南美洲的新加坡复旦拥有很强的争夺第一
实力,南美洲2007 年固然没有一级高手Petr 和tomek 的参加,可是ACM 传统名校
St. Petersburg,St. Petersburg IMFO,Warsaw,Saratov,Petrozavodsk
等都派出了极
其豪华的阵容。就算在2000
年前后美洲部队战表倒霉,可是近期出于众多北美洲
运动员的加入,美洲MIT 等超级名校也在季前赛中显示得极度强势。
记得,每趟世界季后赛往日,TopCoder 的论坛上都会罗列出装有在座季前赛
的TopCoder 选
手名单。可是自己不是很重视那么些多少,因为在很频仍与北美洲运动员切
磋之后,我意识了上下一心与亚洲选手相比较的一个主要缺陷:我插手种种赛事以来,起
初比赛过程中平常受压力的熏陶很大,很难正常发挥自己的水平。后来情况拥有
革新,在大多数交锋中都能健康发挥团结的水平。可是,令自己倍感奇怪的是,许多
来源西方的健儿在
巨大的下压力下,反而表现得极其欢悦而能超常发挥出自己的水
平。来自西方的各项,我深信她们假使达到了兴奋的情景,都持有获得季军的实力。
二〇一八年日本东京复旦季前赛总括中,他们也提到了团结并未公布出应有的水准,而IMFO
不畏在竞技压力下还可以够做出8 题,可知他们平时陶冶实力之强。不过本人觉着
当场比试发挥受影响恐怕是个别中国运动员的坏习惯,可能不符合用相同的思绪分析
澳大利亚(Australia)的顶级高手。
到达日本东京:
启程的前天晚间,我依旧熬夜插足了TopCoder 上的SRM 竞技,竟然是Petr
出的难点。当时我与Petr 的Rating 差异很小,当时自己3
道标题都交出了很高的分
数,在System Tests 之前一马领先,可是500 和1000
分的标题都是因为局地很小的
疏忽而破产了。我也失去了在半决赛从前超越Petr
的大好机会。结果到达日本之
后的第二天,吃早餐的时候,我就际遇了作为磨炼来到日本东京的Petr,他一看到自身就
扯前日竞赛的事情,汗。现在回顾起来,这一场SRM 对本人的准决赛之旅确实有不小
的负面影响。
到达东京(Tokyo)随后才意识,所有军事中,唯有我们挑选了与拥有志愿者衣裳颜色
如出一辙的南开校色黑色,开幕式进程中,许多三军都把我们真是志愿者了。
演习赛前一天的晚会很富厚,大多食品都是神州作风的,水果也非常美味。
晚会时期,我看看了重重陆地校园的人马,当年大陆至少有15
支部队参加季前赛,
大街小巷可以感觉到说着国语的健儿。同时还察看了成百上千TCCC
上出现过的面庞,随后
发觉ardiankp 也来参预了,大家还聊起了ACM 在新加坡共和国(ardiankp
是意味着南洋理
管理大学加入的)的情形。类似常规赛那样的较量,我觉得选手之间的调换则更器重
了,因为每一趟常规赛都会汇集众多熟稔的ID
但陌生的脸面。晚一些过后,大家与
香岛大学的T2 一起打牌,队友geworm 和wd.h
都抽签到了另一方,他们的牌太猛
了,在加上我和李文新老师的牌都不佳,结果大家惜败。
从正规比赛的前几天的清晨始于,主办方组织我们娱乐当地的Disney 乐园。
东瀛3 月的景观很美,当地人也很热心,唯一的缺陷就是无论用塞尔维亚语照旧日式英
语都很难沟通。大家在Disney
乐园中第一以观望表演为主,没有参预过多的位移。
东京(Tokyo)到了中午有点冷,我嘴唇都有些结霜了,但是发现路上许多东瀛女高中生还穿
着裙子,仰慕。
专业竞赛:
半决赛的枪杆子是根据校园的音序排座位的,陶冶赛时大家发现自己坐在来自
荷兰王国的上届季军Twente 大学旁边,刚打招呼就发现他们3
人的最低身高也有190,
传言荷兰王国女孩子的平分身高也有180 以上,就像觉得温馨是从小人国来的。
陶冶赛进程中,我早已丝毫感想不到游戏的气息了,现场的忐忑不安氛围已经笼
罩了俺们全队。所有军事都在抓紧一分一秒熟练比赛环境,比赛场合中敲击键盘的动静
早就完全覆盖了观众鼓掌的音响。竞赛中采取的PC2
提交系统比想象得安宁,我们
全力尝试各样功效以熟练电话上的编程环境。日本东京的半决赛使用了一个形象奇特的
键盘,由于当下一度养成了自带键盘的习惯,本次季前赛中奇形怪状的键盘对我编
程的快慢影响越发大。
季前赛正式竞赛在其次天9 点左右上马,Bill 想尽种种措施活跃气氛,不过比
赛初步前几分钟现场或者静得可怕,竞赛初阶5 分钟过后,现场就被键盘声笼罩
直至为止。大家回看一下比赛的经过吧,底纹的文字是我竞技后写下的总括:
这一次World Final 的难点又着力由编程题组成,可能是由于竞赛时不够欢愉,
比赛全程都不行不顺遂。
粗粗从2003 年开端,世界季后赛的题材风格早已完全倒向以编程题为主的特
点,对此我们早有准备。可是是因为时差难点,还有几天前SRM 比赛是因为错两题导
致Rating
跌停对本人信心的影响,使自身竞技中直接不是很提神。不过比赛进度中,
大家依旧雷打不动的使用后边提到过的常用组队形式:
(1) geworm 全程负责读题,思考算法和出多少;
(2) wd.h 和本身在较量前2 个钟头一起攻不难的标题;
(3) 2 钟头后wd.h 就起来死磕难点,我主写程序一直到3 个半小时左右,结
合wd.h 对难点的握住,大家先导合攻难题。
25 分钟:Problem A,简单地枚举。不过我生物并未学好,没有设想老人基因
的各种难点,错了一遍。
比赛起初时,正常情况我会从B-I 中间寻找不难上手的标题。然而由于有些紧
张,直到geworm 给自身翻译A
标题内容时,我还平素不读懂任何难题,那种意况很少
发生。
标题A 的讲述,须要一些必需的古生物知识支持精通,可是那几个事物本身一度忘
记。geworm
花了过多日子协理自己领悟这题,我仍然出于尚未考虑老人基因的顺序
WA 了一遍。可是改过来之后,大家甚至是颇具部队中首先个通过A
题的,可见当
时多多武装也尚未完全松手。
43 分钟:Problem B,最长上升子体系。开首算法没有想好,不可捉摸地错了
一次。
借使说题A 的WA 是生物难点,那B 的WA 简直就是莫名其妙。B 就是最长上
升子种类难题,好像刚开头写时自我和wd.h
都并未想了然,写了一个神鬼莫测的程
序,WA
一回将来才改成正确算法。不过立时我们都并未想到的,准决赛中我们队
伍莫明其妙的WA 恐怖的梦才刚刚初始。
97 分钟:Problem G,枚举+模拟。那是很扯淡的一题,标题很不难看错,我
们出于看错题目错了两回,等看齐Twente
大学过了后来才重读难点,找到了合情合理
的了然,浪费了大批量的日子。
G 的题材叙述确实不是很明白,许多军事都暴发了接头错误,大家也不例外。
可是第2
次提交错误就不可能了解了,当时也不知底是因为怎么着来头又提交了第二次,
难道说是想先抢一个提交亚军呢?当时我们真正受到了开场救经引足的影响,那样做在
罚时自己就落后的景色进一步下雪上加霜。
146 分钟:Problem F,BFS。其实那题是自己揭橥编程能力的机遇,不过我起来
用了一个很想获得的寻找方法,错了四遍才改用BFS 过了。
在G 题迷茫而放弃以后,我又尝试完成了F。F 的第一回WA 是大家Final 之行
的第二回“莫名其妙”了,我也不亮堂自己用了何等一种出乎意外的摸索方法如故过了
样例,还及时提交了,面对那种状态我不怎么心急,表现得很不冷落。好在geworm
当下提示,我立刻改成BFS 过了。在那时期,wd.h 已经落到实处出了I
题,并交由了一
次,结果是WA。
178 秒钟:Problem C,排序+枚举。那题有一个险恶的地方,就是theta=0 的
事态,还好大家着想到了,那也是咱们唯一四遍AC 的题材了。
C 题的算法其实万分清楚,阴险的景观大家也考虑到了,我终于没有再搞笑一
次,那也是大家唯一五遍AC 的题材了。从通过C
的时刻讲,我们的格局依旧很有
利的,因为难度很大的I 大家已经完成得大概了。
224 分钟:Problem D,数学题。那题本是一道很粗略的数学难点,但是不知
出题人怎么想的,搞了有的并未别的意义的东西,真是这一次难点的一折桂笔。大家
开班由于没有留意三点共线的情景错了3-4 次,然后由于int64 越界又错了3-4
次,
说到底错了7 次才AC。这题一共浪费了1 个多钟头。
在BGF 各三次意外的WA 之后,大家又完全陷在了D 题的圈套之中,假使顺
利的话D 题只需要15 分钟就足以写完,不过大家忘记考虑了D
题中众多的阴险情
况,拖延了1 个多钟头,进献了7 个莫明其妙的WA。不过,当时本身并从未想到,
那曾经是自我AC 的最终一道标题了。
227 分钟:Problem I,数学+模拟。那题是Jelly 写的,有很多破例意况。
平心而论,我在准决赛上的气象不是很好,编程速度受到震慑,而且有10 次
上述的失实付出。最终我们7 题的罚时高达1200 多,而新加坡赛区同样7
题的罚时
唯有700 多,从这点上也足以见到当时实在不在状态。可是,wd.h
很好地实施
了俺们约定的组队形式,顺遂落成了拖后石嘴山的角色。在本人透过D 题之后,他改
正了I 程序中的最终一个bug。I
题最后也唯有大家和法兰克福两支队伍容貌经过,但是说
是我们最终可以获取亚军的一艺之长。记得在颁奖仪式往日,基本上所有选手见到我
都问I 如何做,我都合并答复:是胡伟栋做的。
咱俩依靠I 题的AC 首次排在了登峰造极。比赛进行了227 分钟,可以在200 分钟
事后收获领跑的机会,我首次探望了争夺头名的想望,香港(Hong Kong)和马普托赛区的欢呼场所一遍
又三次从自身面前闪过。当时唯有洛杉矶高校通过6 题,其余阵容都还不当先5 题。
而是幸福只持续了短暂的3 分钟,大家是因为罚时太多而被圣Paul反超,洛杉矶大
学通过第7 题时仁川队员的反应大约疯狂,ICPC
的工作人员也用照片记录了这一
时刻。
Problem E,大家的算法应该是不错的:二分答案+最短路。不过不知程序犯了
怎么着错误,没有AC。
Problem H,很复杂的几何难题,大家的算法是:扫描。可是不知程序又何在
写错了,结果是WA,不是TLE。
纵然如此在接下去的73 分钟时间内大家从未再过题,然而我们仍旧拚杀到了最后
时隔不久,拼尽全力而无怨无悔。无论是E
仍旧H,大家都想出了不利的算法,并且成
功写完了先后,不过Judge 给出的结果平昔是WA。大家不断测试数据,并修正了
局地bug,但仍然无法通过第8
题。在那种景况下的安居乐业过题能力大家实在更加没
有磨练过,蔚山能够通过8 题的超强实力真正很令人敬佩。竞技刚截止时,Petr

专程赶到问大家有没有通过第8 题,ICPC 的工作人士碰巧留下了照片。
当下自家很盼望可以借她的造化获得一个Yes,不过PC2 依然不停重回WA 直到
最后。
新兴,E 题就成了自家写总计几何难点的一个光辉的心情障碍,直到2 个月前在
Proxima 的一回训练中,在队友的援助下,我到底不负众望通过了一个更强版本的E

(题目在UVA 上,题号是11425,那题至今2009.1 也还唯有自己和日本首都季军队的
marek 通过)。
Problem J,那是一道很复杂的算法标题,现在本人还不能印证算法的正确性。
更重视的是那题很不难落成部分接近天经地义的算法,可能没有做那题是大家这一次比赛
的绝无仅有中标之处。
I 的算法大约如下:
(1) X_i = the mininum cut between V_i and V_0.
(2) while (the graph is not empty)
{
(3) m = min(X_i).
(4) remove all nodes V_i whose X_i=m.
(5) let X_i = min( X_i , m+ the mininum cut between V_i and V_0 ).
}
(6) return X_1.
此间提一个当着的秘闻,最终突显洛杉矶大学的结果时,他们成功通过了E 题,
不过竞赛进程中,大家并不曾看出她们挂起粉红色的气球,不明了来自河北大学仍然
嘉兴大学的健儿能无法细致回看一下,当时你们应当坐在他们边上。
颁奖:
最终,华沙大学以通过8 题的大成得到季军,Mobile 罗布ot 通过7 题总用时
1200
分钟赢得季军。半场比赛,我们克制了起初的种种不利因素,成为半场第一
支通过7
题的军事,亚军也是一个更加讨人喜欢的实绩了。由于芝加哥大学不出自澳国,
俺们同时也得到了亚洲季军。
颁奖仪式之后的表演很精美,映像最深的要数那位“神偷”了,他在观众面
前不断施展“室如悬磬”,观众掌声不断。记得表演截至后大家等电梯时,这位演
员从大家身边度过,我们都超过确认自己的钱包和手机。ACM-ICPC
日本首都半决赛在
一片片掌声中落下帷幕。
总结:
ACM-ICPC 季前赛为止后,Mobile 罗布ot 又復苏了安静。Mobile 罗布ot
创造的话
共获取了多个分区赛亚军和一个常规赛亚军,从那以后Mobile 罗布ot
就揭示解散
了,也许唯一的不满就是没能获得一个确实的世界季军。赛后,黄金雄助教也来向
俺们祝贺,从她的谈话中,大家也感受到了一丝挥之不去的缺憾。
东京(Tokyo)季后赛的几天里,我有空子结识了许多国内外朋友,也是本次扶桑之行
的一大收获。同时也谢谢众多ACM
选手一年来对我们的关怀和支撑,当时bbs.pku
上预留了一个很长的帖子,让自己永生难忘。
在现场比试中,我多次与亚洲运动员直接交手,对他们的特色有自然的精晓:
(1) 亚洲运动员的编程能力很强,很适应季后赛现有的题材风格。有些亚洲选
手在notepad 里写程序,然后直接提交的史事绝非神话。
(2) 亚洲运动员对于算法的灵活运用能力强,可是对于一些比较深的算法驾驭
不多。例如此次常规赛的J 题。
(3) 许多南美洲运动员的实地抗压能力很强,即便在终极天天仍可以表明出自
己的程度。
在总括过武大和Srbga 出题的风骨之后,总括一下自己通晓的常规赛标题风格吗:
(1) Srbga 二哥出的题材和社会风气季前赛的难题风格看似,标题对编程能力提议
了极高的渴求。比较之下一大半标题对算法的必要不高。
(2) 准决赛标题对算法的体察范围格外广,不过对于某非凡的算法必要不高。
(3) 准决赛标题标大运限定很宽,出题人很提倡一题多解。而且数量尚未想
象得苛刻,随机算法有用武之地。
日本首都的半决赛已经甘休快2 年,二零一九年寒假甘休未来,我又要准备踏上季前赛
道路了,希望这一次大家Proxima 能做的更好,将季前赛排名进步一位。
附Final2007 排名
Rank Name Solved Time
1 Warsaw University 8 1405
2 Tsinghua University 7 1200
3 St. Petersburg University of IT, Mechanics and Optics 6 866
4 Massachusetts Institute of Technology 6 866
5 Novosibirsk State University 6 868
6 Saratov State University 6 957
7 Twente University 6 1011
8 Shanghai Jiao Tong University 6 1026
9 University of Waterloo 6 1103
10 Moscow State University 6 1192
11 University of Auckland 6 1210
12 California Institute of Technology 6 1241
选拔假期空闲之时,将这几年GCJ,ACM,TopCoder 加入的一部分非同儿戏竞技作个回
顾。最后是2008 年的阿德莱德再次出现。
2008 年ACM-ICPC——瓜亚基尔再次出现
2006 年ACM-ICPC 季后赛甘休后,Mobile 罗布ot 就公布解散了,也许唯一的遗
憾就是没能得到一个真的的世界亚军。发布退役ACM 之后,我并不曾完全与ACM
绝缘,每便TopCoder 大赛此前 还每每做一些ACM 比赛调整意况。记得08
年终,
我也全程观察了季后赛,然而没有想过复出。
波尔图再次出现:
一 切事务要从一个zhuzeyuan 的电话说起,时间是11 月8 日夜晚10 点左右,
立刻自家正在参与UVA 在线竞赛而为GCJ2008 作准备。 zhuzeyuan
在电话机里第一告
知我Loner 车祸的事情,好在后天Loner 已经痊愈了,当时实在很担心。随后,
zhuzeyuan 向本人介绍了 2008 年ACM
交锋的拓展意况,当时首都和孟菲斯赛区已经
甘休。然后,特邀自己参与Proxima
参预底特律赛区的较量。我想立马承诺的由来根本
有3 个:
(1) 我 个人很喜欢Coding,纵然退出ACM 已经快两年了,但是还时常加入个
人较量。刚刚完成的GCJ2008 中国区季前赛,出人意料的争夺第一增强了我的信心。
除此以外,ACM 那样长达5 个钟头的公司比赛作育了很特其余环境,比赛场所上的空气和
豪情是做评判教练要么在场个人竞赛中不可能体会到的。
(2) 3 年前的2005 ACM 南京赛区,我留给了自己大学生活中的一大缺憾。对于杭
州2005
的全军覆没,我直接想寻找机会从分外跌倒的地点爬起来,彻底摆脱紫金港校
区留下的阴影。
(3) 其实还有一个缘故就是我家在科伦坡,而且在本科时期我也曾经到阿德莱德电子
科学和技术高校做过关于ACM 的报告,lcy 先生的热情给自己留下了长远的纪念。
对于Loner 的车祸,我也认为很是奇怪。那也是对此大家常年在校园骑自行车里
横冲直撞的警告。Loner 现在亦可还原得这么好,我们都很乐意,祝你过年ACM
好运。
加入Proxima 的步调很顺畅,教练邬老师对我复出想法的作答简单扼要:研一
学生可以加入ACM 竞技。
Proxima 的其它两名队友分别是zhuzeyuan 和zhouyuan(周源),我加入
Proxima 之后,新Proxima 先后举办了3
次陶冶比赛,随后就出发到马那瓜电子科学技术
高等高校出席2008 年ACM 青岛赛区的比赛了。
当 时,我经过众多网上资料和zhuzeyuan 的叙说通晓了当时北大的成绩。到
乔治敦赛区从前,北大的What’s Up 和IronGods
已经分头赢得了萨拉热窝和首都赛区的
亚军。其中IronGods 还赢得了哈利法克斯赛区的亚军,What’s Up
则一起过来马那瓜加入
比赛。Proxima
在瓜亚基尔赛区以前早已参与了香港赛区的竞赛,成绩是第二名。就当
时的地形讲,大家一向不身份考虑太多事情,若是想
保留悬念就非得得到圣何塞赛区
的冠军。
格拉斯哥赛区现场赛:
在青岛赛区操练赛这天的早晨,大家赶紧一切时间开展了模拟磨练,选用的
标题是NEERC 的题目。标题难度有点大,大家做满整个5 小时,直到12 点50 才
不久去吃午餐。结果很晚才到达比赛场地,到时候磨炼赛已经初始很久了。希望自己
们的姗姗来迟没有影响旁边队深谙竞技坏境。
杭电比赛场所的条件很好,在比赛场地里本身找回了2006 年新加坡赛区的觉得。队伍容貌里面
的空中很宽敞,电脑桌也很大,足以让3 私有在下面一起演绎公式。立即就看到
了lcy 先生,不过他带来了一个不太好的消息——差异意自带键盘。好在杭电提供
的键盘很标准,对我们影响不大。
正式比赛在其次天深夜9 点开班,回看一下较量的长河吧:
在Proxima 队中,比赛先导时,依旧由自己准备编程环境,然后从中间开头读题。
自己当下发现了D 是一路接近简单的难点,并且也只顾到了那句话:
WARNING: a naive algorithm might not be sufficient to solve this
problem.
唯独没有想到的是BFS 算法也毕竟naive
algorithm,我交出了半场第二个提交,
结果是理所当然的TLE。然而那句WARNING 稍微有点大方。
zhuzeyuan 发现A 是粗略难点,于是我及时写A。
19 分钟,A:判断两张图的修改距离。枚举全排列,计算即可。
A 是最简便的题材,由于开端D 的推延,大家大约是半场第4 个出题的人马。
进而,zhouyuan 发现J 也很简短,于是自己转向J。
28 分钟,J:允许删点的并查集难点。通过添加新点的章程完毕删点。
过了J 之后,排行暂时上升到首位。随后,zhuzeyuan 发现并未新题可写,
于是乎就从头写C,进度中,我和zhouyuan 发现G 比较简单,于是插空写G。
50 分钟,G:简单图论难点。早先删点判断错误导致WA 了一遍。
59 分钟,C:高精度总括和素数判定问题。那题是zhuzeyuan 写的。
不到一个小时就因而了4 题,Proxima 获得了一个很好的开头。对于瓜亚基尔赛区
难度的难题,可以在首先个钟头通过4 题已经很顺遂了。对于广大分区赛中会出
现愈多的概括难点的情事,有时可以一呵而就一小时5 题。不过一钟头6 题其实太难
了,记得大家在三遍锻炼竞技中完结了一钟头6 题,已经是大家的能力极限了。
接下去自己完成了一下B,不过由于发生了了然错误,总括结果与题材需求测算
的结果平素存在重新排列难点,只能把程序放在一边。
继而,zhuzeyuan 伊始已毕H,提交未来我起来写F。
95 分钟,H:总结几何,就算使用O(n2)的算法必要注意常数不易太大。
105 分钟,F:自动机判断相等难点,通过测算差乘的办法可以在
O(n2*|Sigma|)内解决
H 的交由等了很久,H 的Yes 出来后不久本身就写完了F,提交将来也Yes 了。
大概在2 个钟头左右大家做出了6 题,其实如若不在B
上浪费时间可以更早一些。
在2008 波尔图赛区,我们又三次拿走了6-4 的超过优势。
上面大家面临一个比较不方便的光景,E 和I 看似都相比复杂,但了然题意的B
和D 都未曾想出算法。2008
年格拉斯哥赛区的标题中,基本没有中间难度的难点,所
以大家因此6
题之后就向来进入了较量前期。当时大家分了弹指间工,我主宰死磕D
题,zhouyuan 负责推B 题的公式。zhuzeyuan 尝试新题目E 或者I。
自身的办事展开很不如愿,先完毕了一个层见迭出的A*算法,由于优化得不得了或者
TLE。现在回看起来,D
题标准A*算法中行使的要命优化依旧挺巧妙的,至少很有
艺术感。我放弃A*算法之后,zhouyuan 如同早已推好了B
题的公式,开首协助我
实现D 题。
163 分钟,D:状态最短路径难点,通过A*算法加局地优化可以轻松通过。
zhouyuan 提议了一个很要紧的优化措施,先经过解方程的措施判断是否有解,
在认可有解的动静下利用双向广度优先搜索,程序写好将来又TLE
了。但是自己觉得
运行时刻已经差不离了。于是,我使用了卡节点的法门,终于在第5 次提交通过
了D。D 题大家用了大概一个钟头左右。那时What’s Up 早已经过5
题,但是是因为
她们卡在H 题上,大家依旧以7-5 超越。
zhuzeyuan 确认E 和I 比较复杂之后,大家开头合攻B 题。zhouyuan 其实受到
了自己原本错误算法的误导,他得到一些公式来测算繁衍函数,通过繁衍以及原来程
序的结果得到不错结果。可是,从即刻的款式看,那样也是很正确的选择。
次第高效就写好了,提交将来又是出其不意的TLE。B 题的TLE 和D 的TLE 本质完
全差距,B 题大家算法的复杂度是O(n4)的,对于n<=20
的数目范围,时间上理应
未曾难题。于是,我生成了100 组测试数据,发现一起只须求1 秒左右。
在B 题的这一点上,我认为命题人做的很不创制,纵然此题存在O(n3)的算法,
可是既然把范围出到20,就应有允许O(n4)的算法通过。然则命题人一共叠出了
6000 组测试数据,使得咱们的次序超时了。而且在Clarify 中的回答是1000
多组,
大家优化程序未来仍然间接TLE,当时我们怎么会想到是6000 多。至少那里的范
围20 极具误导性。幸好,zhuzeyuan 及时想出了一个解决办法——打表。由于对
次第没有信心,打表的15 分钟时间内我们3
人都只好通过手工计算不难多少来确
认程序的不易。
236 分钟,B:相比复杂的动态规划,须要考虑4 种情况。
打完表之后提交终于到手了第8 个Yes,时间是236 分钟,距离封版唯有4 分
钟。由于6000 组的阴险数据,大家从第五回提交B 题到通过B 整整用了50
分钟,
而且是3 个体直接在一道做。
封版时,大家仍维持了8-6 的超越优势。可是接下去,我们犯下了坎帕拉2008
最大的谬误,要是类似的谬误在季后赛中出现,大家将很可能错过超过地点。当时
大家从不看出港大挂起E 的气球,于是在E 和I 中挑选了I,结果深深地陷在了I

无底洞中,直到为止都不可能自拔。
I:模拟题,需求考虑的情景比较多。
E:总结几何。总括半平面的交。
现行回顾起来,E 题的难度远没有I 题大,我们错误猜想了I 的难度。相当敬
佩赛管上通过E 题的港大和I 题的海南大学,你们不愧为射雕英雄。
清华2008 战况:
2008 年,复旦连续自己在ACM 大陆赛区中的霸主地位, 4 支不相同的武装获得
了创纪录的4 个不等赛区的季军。分别是:

  1. What’s Up——圣克鲁斯赛区季军
  2. IronGods——香江赛区亚军
  3. Proxima——瓦伦西亚赛区季军
  4. ZCS——天津赛区季军
    从ACM 的平整上讲4 支队伍容貌都获得了出征准决赛的身份,哈工大常规赛阵容的
    遴选进程在拉合尔赛区截至的第二天就起始了。
    从自身的角度描述另3 支军队的图景吗:
    What’s Up 是武大首个获得季军的军队,乔治敦赛区的进程中,他们以amber
    主写程序的格局举行,在比赛起始阶段体现出了很强的冲击力,然则卡住H 后的
    慌乱略显出组队格局的弱点。纵然他们在克利夫兰赛区之后就挑选摒弃了常规赛资格的
    角逐,可是大家都获悉她们的实力。后来What’s Up 的分子担任了PK
    竞赛的裁定
    工作。
    ZCS 由刚进来清华学习的三名大一学生结合,成员是yuhch123,Cheryl 和
    ScaleRhyme。我出席Proxima 之后没有和ZCS 交过手,不过在Ural 和SGU
    上较量
    时看到过ZCS 的身影。在阿塞拜疆巴库赛区之后,ZCS 在圣胡安赛区创立了7/7(7 提交7
    通过)
    奇迹,可是和上海赛区相似的是中期略显经验不足。随后,ZCS 没有临场校内PK
    赛。
    IronGods 的重组是OpenGL,ahyangyi 和ghy。在IronGods 创造之初,我平昔
    很看好那支阵容。萨拉热窝赛区甘休后,记得ahyangyi
    还来和我抱怨竞赛中的失误,
    那道高精度题目确实有些过于复杂(呵呵,不过至少数据尚未不当)。巴黎赛区的
    场馆,我是将来听dzx 介绍的,IronGods 依靠最终一钟头的稳定发挥,通过3
    题,
    一举当先Proxima,Carriage 和ZCS
    获得亚军。可是几天后,我惊奇的发现自己需
    要面对强大的IronGods 了。
    IronGods 的重组与新Proxima 惊人得一般,IronGods 的OpenGL 与ahyangyi 还
    有自家和zhuzeyuan 都是TopCoder 上的Target(中国共计有7 个Target,其它3

    是前辈haha,lympanda 和ZCS 队中的yuhch123,看好zhoujie 成为第8
    个,加油
    哟!),他们的编程能力与自己和zhuzeyuan 齐驱并驾。从TopCoder
    的成绩上看,
    咱们多人的速度略快。
    另一名队员ghy 和zhouyuan 都很擅长思考算法,ghy 为止OI 时间相比较短,状
    态保持得很好,zhouyuan 对于长远的算法明白比较踏实(巴黎的A
    很赞呀!)。
    从协作上说,IronGods 组队时间长,同盟地点比大家默契许多。大家结合后
    即使如此也展开了一部分教练,但是在较量中广泛调换偏少,越发是本身和zhouyuan
    的交
    流,在后几场交锋中才有些成功的匹配。
    不过从平安角度看,我们稍占上风,TopCoder 上的Volatility 值至少可以说
    雅培些。而且ACM 比赛时间长达5 钟头,稳定性的渴求相应比TopCoder
    还高一些。
    南开校内PK:
    新生,zhuzeyuan 代表Proxima 与IronGods 协商之后,大家决定选择三局两胜
    的赛制,并定下了3 场交锋的时日和题材布置。
    有关半决赛队伍容貌的挑选,我个人分外不接济间接指定,可能与自己的片段经历
    关于呢。已经跻身博士学习的自身,对加入半决赛已经没有两三年前的心绪了。不
    过自家个人的见地是,假若高校指定,我对此4 种结果都能够承受;如若进展PK

    拔,比赛场合上自己必然拼尽全力。
    两场PK 进度中,大家都在bbs.pku 上公布了现场的即时排行情状。由于清华
    ACM 团队有严厉规定须求对五遍PK
    中应用的题材保密,我那边就只留下了比赛的
    差不离进度。
    率先场PK,时间和孟买赛区完全相同,进度大概如下:
    Proxima 启动相比较快,到2 钟头左右就取得了5:2 的超过优势。
    题F 是这一场较量中我们最大的失误,F 浪费了过多时日,而且最后都并未过。
    IronGods 利用Proxima 卡住F 的机遇连追4 题,以6:5 反超。
    发觉IronGods 反超之后,我又尝试了五遍F 题,但依旧无法因而。竞技还有
    70 分钟甘休,而且大家手上并不曾任何标题。zhuzeyuan
    在事关重大时候毅然决定初始
    写J,记得她说的一句话是“没有时间了,我不可能不从头写了”,当时地势不容乐观。
    好在J 成功1Y,士气大振。
    Proxima 随后连过两题重新占据7:6 优势。
    末尾,IronGods 追成7:7 平,竞技又打得难解难分。
    IronGods 最终每日也还有机会,大家又几次目睹了IronGods 的绝境反击实力,
    可能他们最终做H 的取舍值得商榷。
    首先场PK 进度中两支队都有为之侧目失误的一时,大家是因为失误在先前时期,所以罚
    时较少。最终仰仗罚时险胜,在PK 中占得先机。
    其次场PK,时间设在12 月25 日的早晨拓展,标题编号从A 到L,共有12 题
    之多。第二场PK
    比前一场展开得更激烈,进程中两支军队都长日子保持了很好的
    场合,比赛进度中反复调换超越地点:
    早先Proxima 起步略快,65 分钟就因而了5 题BDEFK。
    胚胎看似顺利,但是大家都了解:真真的比拼还平昔不起来。
    Proxima 卡在了H 和C 上,IronGods 通过了BCDFK 追成5:5 平,罚时Proxima
    领先。
    IronGods 通过了G,首次反超6:5。
    Proxima 经过rejudge 通过了H,出现了6:6 平,罚时Proxima 领先。
    Proxima 第10 次提交才通过了C,再一次获得题数超过7 :6。
    比方输掉了这次PK,题C 则是最大的后天不足。
    IronGods 通过了J,追成7:7 平,IronGods 在罚时上打头。
    此刻的罚时后退就是Proxima 在C 题上出错9 次的恶果。
    Proxima 第4 次提交才通过G,以8:7 反超,但罚时依然很大。
    IronGods 通过了H,又追成8:8 平,利用罚时IronGods 再度取得超越。
    那早就是第6 次现身平分了。那时还不到3 个小时,校内PK 赛的难点难度并
    不在2008 波尔图赛区的难度之下,3 时辰的8:8
    的高比分平局是现场比试中很掉价
    到的。而在高比分平局中罚时也是很重大的,此时IronGods 占据明显的优势。
    Proxima 经过rejudge 通过了I,再度超出9:8。
    Proxima 通过了J,优势壮大到10:8。
    回忆题J 的率先次提交起头的回到结果是“Other-Contact Staff”,看到那么些回
    复之后zhuzeyuan 马上跑到Judge 室,在被工作人士挡住之后,zhuzeyuan
    很意外
    地问道“难道不是你们让自家来Contact 的呢?”,囧死了。不过很快就rejudge 成
    Yes 了,题J 的经过也从一定意义上逆袭了罚时的不利,IronGods
    如果想逆转就必
    须在最后一钟头重新演艺上海赛区封版透过3 题一幕。
    Proxima 通过了A,优势增加到11:8。
    纪念最终提交A 题的时候,我紧张得手都不怎么发抖了。当时只剩下25 秒钟,
    IronGods 还从未起来写A 和L
    两题,所以在结尾的时日里他们一度不可以因此余下
    的4 题了。A 题的Yes 也就变成了本场PK 的大胜宣言。
    IronGods 最终每一日通过了I,最后题数为11:9。
    本次校内PK 的凶猛程度决不亚于2006 年日本东京赛区,可以最终取得这一场PK 使
    得我们更有自信地站在准决赛的当场。
    率先感谢关切大家的同窗,记得首先场PK 当天正在举行多伦多赛区比赛,
    bbs.pku 上或者出现了如此多的帖子为大家双方加油。第二场PK
    截止时已经是早上
    11 点,大家手机还持续接受祝贺短信。
    向IronGods 三位国王致敬,在PK 进度中只需略微的转移,出现在布宜诺斯艾利斯
    的就很可能是你们。棋逢对手是本人ACM 生涯的一大好事,相信你们今年早晚可以
    做得更好。
    自家想那是武大第三遍选取公开的实地PK 方式来拔取准决赛队伍容貌,个人觉得PK
    的方法除了公平之外还有许多优点。首先,PK
    格局得以使得各武力可以更从容地
    慎选和准备不相同的分区赛赛区,有效抓实高校的总体战表。其次,通过PK
    的历程,
    可以增强各项之间的沟通,阵容各州点水平能够获得周详升高。真是一石二鸟。
    行使假日空闲之时,将这几年GCJ,ACM,TopCoder
    参与的一对重点竞技作个回看,包蕴
    后天统计10
    篇。接下来的重中之重竞技就是世界常规赛了,纵观世界常规赛各队,尽管时势不容
    明朗,但大家必然会拼尽全力。
    使用沐日空闲之时,将这几年GCJ,ACM,TopCoder
    参与的有些要害比赛作个回想。
    抚今追昔GCJ2006,ACM2005,TCCC2006 和ACM2006 之后,今天几乎回看一下国内个
    人比赛场合吧。
    境内私家比赛场面——百度之星
    国内个人赛管中最重点的较量要数每年一度的百度先后设计大赛,到二零一九年为
    止已经开设了4 届,每一届我都全心全意地加入了比赛的全经过,百度先后设计大
    赛是炎黄开办的局面最大的了然程序设计比赛,其加入人数比许多社会风气范围的次序
    统筹大赛的人口还要多得多。别的在2006 年底,谷歌 Beijing 进行了谷歌(Google)
    Code Jam China 的竞技,刚刚先导参预TopCoder 的自我也参加了这一次GCJC
    之旅。
    率先届baidu 程序设计大赛:
    最早的境内私家程序设计竞技要回溯到2005 年9 月尾步的率先届百度先后设
    计大赛了,源于宿舍走廊中的海报,我以尝试的心理申请参与了第二届百度先后设
    计大赛。每一届百度先后设计大赛都由初赛,复赛和实地决赛组成。
    首先届百度先后设计大赛中,影像最深的复赛题目就是那道范围巨大的小不点儿
    树形图难题了,100000
    的数据规模吓退了诸多选手,我鼓足勇气提交了一个冲突
    上可以运转的顺序,顺遂经过了复赛进入决赛。最小树形图算法在大约图论书上就
    接在最小生成树算法前边,但是其程序量远比最小生成树大,而且用途尚未最小生
    成树大面积,在多数竞技中很少出现。我最早接触最小树形图算法是在2003 年4
    月,当时正值复旦大学教练,记得关于这几个题材和xreborner
    琢磨了很长日子才得
    以注解算法的不易并贯彻出高速的次第。
    现场决赛于2005 年10 月中在京城进行,由于当下比赛的盛名度不高,时间
    上还和GCJ
    争执,没有太多的超级高手参与。武大高校除我之外唯有superzn(张
    宁,大家留shell 一个人与会ACM 东京赛区预赛􀀯),当时OpenGL
    仍旧以高中生
    身价加入的,还有南开高校的xreborner
    和young(李阳);阿雷格里港大学的magicpig,
    Savior 和张子臻(不佳意思,我不记得你的ID 了,好像马斯喀特2008
    的时候大家还说
    起此事)。我直接认为,现场比试进程的一个主要的意思在于提供了一个老朋友重
    逢和结果新情人的机会,选手之间的调换是比赛中最根本的组成部分之一,我很有
    幸可以在那个比赛中认识了诸多牛人。
    些微回看一下决赛的题材吧:决赛的题材是经典的8 数码难点,给定起先状
    态和竣事状态,计算最短须求的更换步数。对于分数相同的情事,按照顺序的运行
    进程名次。比较不难想到的不二法门有:
    (1) 单向BFS:最坏情形须要1s 左右。
    (2) 双向BFS:如果先判断无解意况,那是xreborner 使用的主意,平均景况
    大概0.002 秒左右。
    (3) A*或者IDA*:先判断无解情形,然后经过距离启发函数搜索。平均意况
    大致0.002 秒左右。我当即采纳了A*的法子,但不少位置的贯彻不是很合
    理。
    (4) 常量表,那是最有挑衅的主意,因为决赛的提交量限制在64K 以内。
    当场比试中,(2)和(3)的应用人口相比较多,速度差不离,选手之间比拼的是
    各样细节和常数的处理。后来,我想出了一种速度格外快的点子:
    首先使用A*加上“卡节点”技术,就是限制A*算法搜索进程中每层的节点个
    数上限,那种算法扩大节点个数在100 左右。然后,由于上述算法的正确不可以
    管教,把具有反例打成常量,程序大致50K 左右。很简单发现,那几个程序的速度
    远比比赛进程中具备程序的速度都快得多。
    最后我的主次以总时间0.022 秒获得亚军,xreborner 和Savior 以0.026
    分并列
    其次名。xreborner
    的顺序很可惜,假如进入了无解判断,速度应该比自己程序块,
    superzn 就更心疼了,superzn 的大方程序其实唯有0.020
    秒,不过有一个数码错了。
    回想颁奖之后,主持人约请获奖选手发言,选手能够透过向前走一步选拔优
    头阵言。那时,我恍然觉得我们把眼光都聚焦到了我身上,向右一看,由于自己站在
    最右边没有留神到左侧的情事,可哪个人知其他运动员都后退了一步,把自己留在了看似向
    前一步的岗位。
    第一届Astar-baidu 程序设计大赛:
    其次届百度先后设计大赛没有等到10 月,而是在2006 年6 月就拉开序幕。
    没有想到的是,第四届百度先后设计大赛竟然以本人在一年前比赛中行使的A*算法
    的名字命名,感到格外雅观。
    记念复赛的标题卓殊标准,印象最深的要数xreborner 招牌式的Zuma,我推
    了多个钟头公式才拿到了合情合理的动态规划方程,完成之后还由于TLE 唯有30 分
    (100 满分)。还有Ying
    出的无向图最小割难点,我用网络流算法又超时了。可是最
    后一题,我的主次如故比xreborner
    优化过的标程还快,真是不易于啊。清华的舍
    友RealPlayer 在复赛中呈现很欢跃,可惜由于一个很小的荒谬没能进入决赛。
    在座第二次百度决赛的健儿中有成百上千耳熟能详的面孔,北大的校友包蕴shell,
    OpenGL,lympanda 还有Macsy。哈工大大学也来了广小运动员,其中除了LemonTree
    和Topkiller(沈毅)之外,还有自己刚到北大时见过的admin 和funny
    的身形。其它
    magicpig 和flymouse 也列席了,而且magicpig
    和我住一个房间,吃饭时记得她把
    桌上所有人的Dev 功底全都鄙视了两遍,可惜PE 不在场呀。竞赛前还观察了
    Srbga
    的身影,据他算得被特邀一起来玩的,其实有点用小脑判断一下就掌握迟早
    是加入出题的,有了Srbga 的加盟,相信决赛题目相对不会是一年前的风骨了。
    其次年决赛的题材是:盛名的俄联邦四方。写程序玩一个10 列的正统2 维俄
    罗斯方块游戏。
    Srbga 设计了很有风味的记分措施和评分标准。对于记分措施,特其他地点是
    消去1 行后并未得分,而同时消去2,3,4 行的得分分别是3,6,10,记分措施
    越发鼓励三回消去多行。评分标准则更意想不到了,有50
    种不一样范畴的数额,对于每
    组数据对拥有选手的得分举行排行,前8
    名的健儿依次得到10,7,6,5,4,3,
    2,1 分,也就是说,是存在可能在测试截至以后分数依旧为0 的。
    竞赛进度中,我花了好多岁月来分析那几个意外的评分标准。
    对此那种评分标准,常见的策略有两大类:(1)所有数据的成绩相比较平均 (2)在
    一种多少风格中特地杰出吧。
    根据数量描述,50 个数据足以分为10 种不一致的风骨。加入竞技的共计有50
    名健儿,要是所有分数是一点一滴平均分配的话,分数是31
    分,那么些数字意义不大。
    但倘若考虑分数的80%会分配在前10 名中(根据当下运动员的品位,这几个只要如故
    正如客观的),那样前10 名的平分分数是124
    分左右,也就是说若是想挤进前4,
    最少也要100 分以上,如若想争取季军揣度须求200
    分左右。倘使接纳一种政策,
    使得它只在一种多少风格中专门非凡,分数唯有非常的50
    分,而且很可能有不少
    有平等想法的运动员,所以(2)不太可取。
    在支配接纳比较平衡的方针(1)的之后,须要再考虑一个难题,如果最后目的
    是150 分,那么平均分数只需求3 分,也就是说每个数据足以允许有5 名运动员超
    过自己。那些不可或缺的解析协助我明确了不遗余力的取向,面对那种开放性的问题,多分
    析标题的特征往往可以已毕一矢双穿的效劳。
    还有一个紧要环节是调动估价函数,机器学习其实是一个很好的方针,可惜
    自己当时不会。其实当时本身做的作业,本质上就是人工模拟机器学习,手工调整了1
    个半时辰,眼都花了。而且我犯下了一个致命的一无可取,记得记分措施相当鼓励两回
    消去多行,也就是说对于平坦的数额,一次消去1-3
    行的权值应该可能设置为负数,
    而自我只把他们设成了0,使得程序对于平坦的数目分数不高。Macsy
    就考虑到了这
    一些,只可惜一个很意外的技能难点(在Linux 和Windows 下的CLOCKS_PER_SEC
    参数是不等同大的,想利用卡时策略时相对不可能事先把这几个数字取出来设置成
    CONST)使得Macsy 没能成功。
    出于Macsy 和LemonTree(同样的技艺难题)的出局,我在不少数码中得到了
    很高的分数,最终的总分达到了是255,当先了第2 名有99 分之多。其达成场的
    诸多选手的顺序风格相差并不大,可能本身唯一多做的事务就是身无寸铁了一个博弈树,
    多搜索两层,那样比直接贪心的顺序看得更远一些。后来事实也验证了,名次靠前
    的选手基本上都是相比较平衡的国策。记得lympanda 洋洋洒洒写了1800 多行程序,
    在其间一种多少中得到了满分50 分。但是可惜panda
    的次序平衡性稍差,总名次
    进入了前10,但最终唯有三等奖。
    其次届astar-baidu 程序设计大赛,南开大学取得了丰收。记得许多北大的选
    手由于试验提前回到校园,颁奖仪式的时候二等奖颁奖一片空场。
    竞赛的夜宿条件得以用无与伦比来描写,很感谢baidu 的大方与细致。记得第
    一天夜里还有机会和Ikki 一起打沙壶球,面对球风完全争论的Ikki
    玩得很热情洋溢。
    Google Code Jam China 2006
    大致是2005 岁暮,突然见到了名为GCJC 的比赛,而且选取的是TopCoder 的
    比赛情势,于是就报名参加了。当时臆度只列席过几场TopCoder
    的比赛,帐号还
    是黑色的,GCJC
    第二轮预选赛由于经验不足差点就被淘汰了。好在安全地
    跻身到了新加坡的现场赛。
    GCJC 现场的健儿中,我以为至少认识80%呢,厦大同学就有7 人:b142857,
    fuwenjie,lympanda,Macsy,zig 还有hyyylr(李老师),复旦的LemonTree

    TopKiller 也都来了,清华也来了过多TopCoder 上的元老xuchuan(徐串),
    sghao126。
    回想,就在GCJC 决赛的今天早上,我出席了TopCoder 的SRM 比赛,第一
    次踩住了Petr,不过也消耗了太多的RP。中午的SRM 比赛中从不人过3 题,第二
    天晚上lympanda 还把大家全都鄙视了三回。随后,b142857 还描述她Challenge

    程中的囧事,由于500 分难点的归来结果需求利用long long
    类型,所以b142857
    见到一个人付出的先后总计进度中只利用了long 就坚决Challenge
    了,结果破产了
    几次之后才意识,那个家伙用的语言是Java。
    比赛中250 分难题,简单的票房价值难点。我写完就交了224 分,竟然是富有选
    手中最快的。后边的500 分,我即便提交是最快的,不过尚未设想一种境况。打
    开1000 分难点之后互连网就起来很不平静了,时断时连,1000
    分难点实在算法很清
    楚,由于互连网原因提交唯有600 分左右了。
    Challenge 阶段起初时,我打开了房间中lympanda 的500 分程序,发现我们两
    人的次序基本进度完全平等。又开辟了一个,也同等。不过在还一直不影响过来的时
    候,lympanda 的500 分程序被Challenge 了,接着我的500 分也被Challenge
    了。
    接下来就不曾什么样斗志了,在迫不得已中伺机竞技甘休。
    比赛结束之后的午宴进度中,我刚刚坐在谷歌(Google) 中国帮主人李开复(英文名:lǐ kāi fù)旁边。午
    餐快为止时,李开复先生问起2 个月前的百度先后设计大赛,突然,一差二错地直接
    问我百度大赛的亚军是何人?那然则在谷歌的巢穴呀,抖死了。我当下真害怕他
    听完回答今后一贯把自家赶下桌:-P。
    好在自身的250 分和1000 分都Pass 了,由于TopKiller 的1000 分超时了,我获
    得了第3 名。季军xuchuan 和亚军b142857 都顺遂通过了3 题。
    POJ Monthly Contest
    约莫是从2004 年8 月底始,POJ 上伊始进行每月五次的有奖月赛。2005 年的
    月赛中,每一次都有空子同xreborner,Ying 等一把手研讨技艺。从2006
    年终起来,我
    曾经相比熟谙了较量的题风,延续收获了重重次竞技的季军,并且保持了大好的个
    人较量场所。
    记得2006 年4 月首,在POJ 的邮箱里忽然意识了hawk 的信,他问我五一长
    假回家的处境。我报告hawk
    自己定在周六晚间起程。于是,第二天深夜就看看比
    赛安排中:2006 年5 月份月赛布置在了周二晚间,太囧了。
    新兴,POJ 上直接出现了一连串奇怪的概念,但实在结论就是自个儿不可以以专业身
    份出席月赛了。现在那么些概念早已成为笑谈了,可是本人不在场月赛之后,照旧有
    ahyangyi 这样的选手夺走了半数以上的亚军。
    后两届baidu 程序设计大赛:
    从第四届开端,大家习惯了在每年6 月拭目以待astar-baidu 的开赛。2007 年最出
    乎意料的就要数CS
    这几个决赛标题了,我在根本的买枪环节犯了第一错误,太迷恋
    AK47 了。祝贺师兄lympanda,Macsy 还有shell,不愧是真金不怕火炼。
    第三届百度大赛我插手了预赛和复赛的命题工作,不过尚未参与决赛的命题。
    决赛标题是一道关于直升机的题材,影像最深的是ahyangyi
    使用了一个很有攻击
    性的政策,若是应用淘汰赛,可能就是亚军了。对自我的话,通过现场比试,有空子
    和老友重逢,并结识了不胜枚举新选手是本人最大的好人好事。
    使用假期空闲之时,将这几年GCJ,ACM,TopCoder
    参预的有些至关首要比赛作个回想。
    前日总括一下万国个人比赛场所吧。
    国际个人比赛场面——三大赛事
    ACM-ICPC 准决赛停止后,Mobile 罗布ot 就昭示解散了,也许唯一的不满就是
    没能得到一个确实的世界季军。发表退役ACM 之后,我如故延续加入了那以后的
    每一场世界范围的当场编程竞技,按照时间顺序分别是:TopCoder Open(简称
    TCO)2007,TopCoder Collegiate Challenge (简称TCCC)2007,TCO2008
    以及Google
    Code Jam(简称GCJ)2008。每趟竞技,我都度过了一段美好欢娱的时光。
    TopCoder 公司与三大赛事:
    TopCoder 集团大致在9 年前建立,创设的缘故有些让人匪夷所思,据说公司
    创小编原来是另一家IT
    公司的大股东,在把本来集团的股票转手之后换了一笔钱,
    设置了TopCoder 公司。然则Topcoder 和原先的IT 公司有一个要害协议,就是
    Topcoder 在开创之初的两年内不足从事软件开发的干活。于是TopCoder
    在前两年
    日子内以看似竞技的章程从事软件开发的移动。经过9 年的向上,现在TopCoder
    商家一度主导由算法竞技转向软件开发了。
    TopCoder 公司除去在网上开设SRM 之外,每年还开办TCO 和TCCC 等现场赛
    事(当然还有TCHS,可是规模比较小,参与面也不是很大),TCO 和TCCC
    分别在
    每年的6 月和11 月举办,每趟大赛都能聚拢广大国际编程高手。其它,谷歌公
    司从2000 年开头,先在各大洲进行名为谷歌(Google) Code Jam 的较量,从2002
    年开始
    也设立中外限量的谷歌 Code Jam。于是那些年来,大家一贯把TCO,TCCC 和
    GCJ 称为三大赛事。
    2007 年事先的GCJ 都是选取TopCoder 的较量情势,Topcoder 的算法比赛有点
    看似于IOI,ACM-ICPC
    之类的较量,标题是同一个项目的。每一次比赛三道难点,一
    般分数分配为250-500-1000,竞技分为Coding,Rest,Challenge 和System Test

    个阶段,时间各是75 秒钟(现场比试85 分钟),5 分钟,15
    分钟(现场比试10
    分钟)和不定。
    TopCoder 的当场比试都由3 个级次组成:所有选手被分成3 个组(称为
    Room1,2,3),每组分别举办季前赛,每组前2(或3)名直接提高决赛,3-6
    名晋
    级 wildcard 比赛,wildcard 竞赛12
    人中的前两名填补决赛的尾声2(或1)个名额,
    决赛由8(或10)名健儿参与。由于三大赛事的竞技方式相 差不大,每便实地决赛
    的运动员中总是有巨大熟知的人脸。
    三大赛事的波荡起伏:
    可能细心的同班可以察觉难点,在作品最开头的一段中,我申明自己在2007
    年之后没有失去任何现场赛事,那干什么一向不GCJ2007 呢?其实原因很粗略,
    谷歌(Google) 公司在2007
    年全年中只举行了面向美洲的较量,没有进行面向满世界的公
    开业。GCJ2007 的间歇也使得整个2007 年只有TopCoder
    公司独立举办世界大赛。
    不过,当大家认为GCJ 将在回想中消灭的时候,GCJ2008 重新登陆,而且新的
    竞技环境与格局给选手以万物更新的觉得。那里先谈谈自己对那种新比赛环境的看
    法吧:
    GCJ2006 仍旧使用的是TopCoder 标准方式,也就是说和TCO 以及TCCC 完全
    一致,用一句话概括就是Coding-250-500-1000-Challenge-SystemTests。
    GCJ2008 比赛环境结合了ACM,TopCoder 还有IPSC(ipsc.ksp.sk)等三种较量的
    特色。
    (1)每道标题分为Easy-Hard 两组数据,并且数据足以下载到地点,那一点好像与
    IPSC 很相像,另一个与IPSC 的共同点就是,不限定选手接纳的编程工具,包
    括肉眼寓目或者人工搜索。
    (2)Easy 数据则和ACM 格外类似,即时交由评测,并且也设定了每一回失利提交
    加4 分钟的罚时。
    (3)Hard 数据则更像TopCoder 的格局了,Hard 数据由于是联合评测,System
    Tests 能够有效
    地把悬念保留到最后一刻。
    GCJ2008 的较量格局是一种大胆的品尝,并且也一度有了很卓绝的结果。
    其余,值得称扬的是,GCJ2008 中首次使用了分各大洲进行地面现场半决赛的
    赛制。使得排在前500 名的健儿可以加入各大洲的半决赛,也拉近了谷歌(Google)集团
    与运动员之间的相距。从另一个角度来说,各大洲季后赛的法门很实用担保了决赛选
    手的水平。平心而论,TopCoder
    现场比试前的最终一轮互连网淘汰赛对运动员的下压力
    很大,就连Petr 在2007 年都平昔来了一个“滑铁卢”,连现场赛都未曾进。而现
    场竞技的公允程度远当先互联网赛,所以经过现场赛决定决赛选手能够毫无疑问程度上提
    高决赛选手的档次,至少我个人很同情那种做法。
    停顿的竞技见惯司空,可能是备受了2008 年全球经济危害的影响,TCCC2008
    也停办了。而且大家都认为,TCCC2007 很可能是TopCoder 举办的末梢五回TCCC
    了,当然TopCoder 那样做没有不客观的地点。
    TCO 则相对平静一些,就连每年举行的地址都不变,TCO 三番五次3 年在知名的赌
    城Las Vegas 进行。今年理应也不会转移地点。
    三大赛事的开办,我觉得选手最大的受益就是,比赛提供了一个到美利坚合营国免费
    打闹的空子。我先后去过7 次美利坚联邦合众国,其中6 次都是参预编程比赛。通过比赛的机
    会,大家可以开阔眼界,结交朋友。我个人真心愿意三大赛事可以持续进行,可是
    2009 年秋日的TCCC 和GCJ
    很可能还要停办,那也是一个不足逃避的题材,让大家
    等待吧。
    弥利坚之旅:
    从2007 年来说的4 次现场比试,尽管每趟竞技进程中都有一对缺憾,可是现
    在回看起来都有不尽的野趣。
    TCO2007 是本人先是次到达赌城,一下飞机就看出许多赌场(CASINO),可什么人知
    TCO2007 整个比赛进度就是一场伟大的赌钱。我随即是因为不熟识Texas Hold’em

    平整,在季后赛中搞错了Flush 和Straight
    的轻重缓急关系,结果初上赌场就倾家荡产
    而被淘汰出局。TopCoder 竞技中竟然出赌博有关的标题,果然有Las Vegas
    的特点
    哟。可是在赌场里,我仔细商量了成百上千赌博娱乐的条条框框,然后写了多少个程序统计赌
    博的期望,但是发现标准几率模型下具有游戏的企盼值全是负数(其实挺明显的),
    于是,也就以娱乐为目的和lympanda 探究了一晃。
    若是说TCCC2006 的Room1 是中华的出奇制胜,TCO2007 的Room1 则是神州的破产
    了,固然Ying 和lympanda
    都跻身了wildcard,不过都是因为有的小失误输掉了这一次
    赌钱。赛后lympanda 请自己去牛排馆用餐,后来卓殊牛排馆也变成每回TCO
    竞赛我
    们中国运动员的首要聚会地方。
    TCCC2007 的小组赛还相比较顺遂,我轻松制服了gawry,Per,marek.cygan 得到
    小组第一挺进决赛。但是决赛中,我为着增强速度以领先Petr,再添加有些紧张,
    最后500 分和1000 分两题又都挂了,落到了第5 名。TCCC2007
    地方设在了奥兰多,
    比赛甘休后大家到邻县的Disney Land
    去玩,那里的危殆游戏比境内激发得多,有
    些远远超过本人的极端,大家一行人平素玩到早上才回到。许多运动员还共同到奥兰多
    魔术队(Orlando Magic)客场观察了NBA 现场比试,可惜最后一节成为了废品时间。
    TCO2008 我也借助飘逸的1000 分题中800+分的交付闯入决赛。决赛前我还和
    visualage
    聊天,夸耀自己平昔没有具备标题全挂,更未曾拿过负分。不过在跟着
    的决赛中,那七个“梦想”就都落到实处了,PE 对自我的评介是太紧张了。基本每一回
    TopCoder
    现场比试都能看出PE,哪个人知他老是猜忌自己一点难点的正确性的时候,我
    的次序就势必是错的,如若下次本身在场决赛,您就无须再看本身先后了啊(呵呵,开
    个玩笑)。
    唯独在决赛Challenge 阶段的最后天天,我从第一理念目睹了Petr 和汤姆ek 的
    顶点对决。在还有15 分钟为止时Petr 还落后汤姆ek 大致30 分左右,Petr 成功
    Challenge 了一个当先了汤姆ek,可是汤姆ek 利用短短的10 分钟也交由了一个成
    功Challenge 又超了归来,什么人知Petr
    获得那些新闻之后又提交了一个Challenge,可
    是天意稍差,假若那一个数据用来Challenge 我的主次的话,Petr 就可见在结尾1

    重复夺回亚军的职责。可以到终极一秒仍能有时机成功逆转的必然是神一般的人选,
    可以把神一般的人选逼到最终一秒的也必将是神一般的人员,七个神一般的人士你
    来我往,为大家表演了一场赏心悦目的交锋。
    亚洲称霸:
    再次引用黄金雄助教在卢布尔雅那2008 时说的话,ACM 准决赛的实力分布由原本
    的美洲称霸逐步转化了今日的亚欧争霸。可是,我根据那一个年的竞技结果发现,从
    2006
    年开端,团体竞赛和村办竞技,越发是个人竞技,南美洲选手一贯保持着相对
    的霸主地位,亚欧争霸的传教实在有些牵强。
    从2005 年开端,大约所有三大赛事的亚军都是亚洲运动员。成绩最好的要数俄
    罗斯,俄国运动员以Petr,andrewzta
    等为表示。俄罗斯运动员训练刻苦,编程能力
    极强。亚洲的另一霸主就是波兰(Poland),波兰共和国选手具有很强的智慧,以tomek,marek

    及Eryx 为表示,程序设计在她们手中展示出了办法味道。
    前几日自己也来看关于废除NOIP 保送资格的小说,我从没登出评论,因为自身没
    有看懂,为啥小说里把保送和保荐资格混为一谈,令人觉着难堪。这里自己对
    保送资格或者想方设法不多,但是想相比较一下大家中华运动员与澳大利亚选手思维能力上的差
    别。
    在高中时,吴文虎先生就常说中国选手的IOI 成绩很精美,的确这几年从IOI
    培育上看,中国是相对的霸主。不过ACM-ICPC
    的成绩,俄联邦和波兰共和国等强队的成
    绩却远在中华以上。于是大家总括的原由是:澳大利亚联邦(Commonwealth of Australia)运动员的编程能力强。我分外同意
    以此说法。
    而是“南美洲选手的编程能力强”的传道并不表达她们的算法能力弱,相反她
    们的怀想素质尤其高,他们持有万分专业和严苛的思索方法,显示出通过短时间磨炼
    的思维能力和素质。
    本身 觉得中国的“高手”和广大经过高考进入名校的“神人”,在大学从前接
    受的指点都是以采用为目的的,并从未太多针对思维格局和力量的教练。记得小学
    要考重点
    初中,初中则拼搏重点高中,高先前期间间则期望名牌高校,而在读书期间,
    咱俩并从未太多机会磨炼自己的思维能力,至少在自己的中学阶段是这么的。固然很
    多高中已
    经竭尽全力通过类似探究性学习的不二法门磨炼大家的创新能力,可是仍旧
    不可能更改选用性考试“高考”这一事实。而在与天堂选手调换的进度中,我以为许
    多思维能力
    良好的学生很已经有时机接受系统的思维能力磨炼,寻找最契合自己
    的考虑方式。我五回有机会看Eryx
    留下的文稿,发现她设想难题有那一个严密的过
    程,从领悟标题到想出算法每步都有根有据,并不是任意碰撞的结果。
    当今南美洲运动员与我们相比较,思维能力上也并不曾逆风局。我有幸在投身OI 竞技
    从此未来,获得众多机遇与其它选手交换,学习他们的商讨格局,努力练习自己那上边
    的力量,试图与层出不穷澳大利亚(Australia)运动员对抗。
    Mountain View 登顶:
    GCJ2008 在谷歌(Google) 总部Mountain View 举办,赛前自己想用Ying 的一句话来表
    达本身对比赛争夺第一的热望,“我尽管获过许多奖,可是缺失一个世界季军”。早在
    GCJ2006,我就具有机会赢得季军,不过在错过本次机会之后一等就是整齐两年。
    比赛开首不久,bmerry 的强势起跑使自身逐步失去了争冠的思想,只得一心做
    好眼前的难点。bmerry 在不到2 个钟头的岁月里就做出了除了C- Hard
    以外的拥有
    题材,他只要在终极一钟头做出C- Hard,就基本上能够锁定季军了。
    不过我克制开场的不顺手之后,磕磕碰碰地在2 小时过5 分顺遂经过了E-Easy
    和E-Hard。摆在我前边的唯有B-Hard 和C-Hard。B 题和C 题比较之下,B
    题我已
    经有了迟早的想法,然则C 则是完全没有想法。于是自己控制先做B,GCJ2008 的B
    题大致是自家的克星,我先后用了100 分钟时间做那题都未曾结果,可以说当时状
    态很差。大约到了2:40 的时候,我翻看board
    时忽然意识了一件令人窒息的业务,
    bmerry 已经尝试了C-Hard 并且超时了。由于C-Hard
    的分数略高于B-Hard,我最后
    想要当先bmerry 就非得做出C-Hard。果断屏弃B-Hard 之后,并从未想出C-Hard
    的点子,写了一个追寻程序可是内心很没底,Hard 数据的交给时限是8
    分钟,于
    是到了2 小时52
    分的时候,我坚决打开C-Hard,用搜索的程序运行C-Hard,在焦
    急的等候之后,程序在运作了1 分多钟将来神奇地运作甘休了。我依靠搜索方法
    透过了C-Hard,一举当先了bmerry。1 分钟后zhuzeyuan
    也做出了相同的标题,超
    过了bmerry,由于罚时排在第2 名。我和zhuzeyuan 还有bmerry
    竞赛过程中都有
    不小的失误,我很幸运把失误的损失降到了最低点,终于赢得了首个世界竞技的
    冠军。
    这一次GCJ 的题材有至极详细的解答,可以在竞赛的链接里找到。GCJ2008 的比
    赛结果从自然意义上,打破了澳大利亚联邦(Commonwealth of Australia)运动员多年的独霸场面。加上原籍南非共和国(The Republic of South Africa)的bmerry,
    前五名中都并未出现南美洲选手的名字,这也是在多年实地比试中没有出现过的。
    这一年,我很乐意看到OI 选手中出现了ahyangyi,yuhch123,Loner 等各地点
    都颇为精粹的新娘,真心希望你们可以早日适应高校的上学生活,再创佳绩。
    多多新娘的参预,大大提升了南开ACM 团队的实力。在2008 年,哈工大大学
    ACM 队创纪录地赢得了4 个分区赛的季军。前天最终一篇记念元帅分享ACM-2008
    中生出的佳话。

相关文章