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

顺路纪念一下yukkuri解散2个月~

Rank Team Name Solved Penally Time AC School
1 Intrepid 8 1386 ABCDEFIJ THU
2 AlphaCentaury 7 1068 ABCDEFJ THU
*3 Rhodea 7 1145 ABCEFIJ SJTU
4 TriPal 6 1036 ABEFIJ SJTU
5 yukkury 5 939 ABEIJ ZJU
6 FreerRadiant 5 961 ABFIJ WHU
7 Falcon 5 1041 ABFIJ PKU
*8 TeaM 4 520 ABIJ SJTU
9 ACOrz 4 925 ABIJ FZU
*10 CZHS 4 954 ABIJ CZ HighSChool
11 SYSU_Imitator 4 1057 ABIJ SYSU
12 Whu_Hibix 3 300 ABI WHU
13 FreeOpen 3 392 AIJ WHU
14 firstblood 3 433 ABJ THU
15 HustCFOP 3 512 ABI HUST
16 SJTUclover 3 512 ABI SJTU
17 Catalyst 3 524 ABJ PKU
18 BUAA_Regulus 3 529 ABI BUAA
*19 SJTUteam5 3 543 ABJ SJTU
20 seuer 3 600 ABJ SEU

10月23日(金)

出发:杭州->上海松江

做校车去DHU,刚开出浙江就到了下沙(大误)松江。先去维也纳报道,然后去大众国际会议中心,路上建筑越来越少,绿色越来越多,最后我们落脚在了一个前不见村,后不着店的地方。于是宅在酒店成了我们的不二选择。

10月24日(Fire)

开幕式,恩恩

开幕式领导迟到习以为常了,过分的是9点的开幕式8点就把我们给晾在会场里了。开幕式开始主持人让大家关闭手机或调到震动,不过我们发现会场里手机就完全收不到信号么!开幕式里的东西就没怎么听了……GB让大家拍了很多手。

接着是教练会,先扯了半天无关紧要的东西,总之我理解不能。后面的提问,由于之前官方已经发布了很多的信息,加之对其基本立场坚定不移,也对我们不少建议也坚决说NO了,我们得到的新的有用信息只有旅游队情况。

一个吐槽点都没有的试机赛

三道水题五个小时的实际赛还是第一次,不过这给了我们灰长灰长多的寂寞时间用于折腾那个◯◯的系统。对于DHU相当自慢的这个裁判系统,我们一直一致觉得很废,除了可以CV Sample外没发现任何优点,毛病倒是一堆。

OS是Ubuntu9.04,但是没有gvim……比赛那个破键盘实在是适应不来,吐血……

试机赛B是寒仔看的,就是实现一个cat;A是jay哥搞的,他先后用三种方法写过这道题;C我很圡的推了很久,最后过的。

然后就是折腾了。最方便折腾的自然是B题了,于是寒仔写了个直接调用cat的程序,结果CE了,发现unistd被识别为“屏蔽关键字”。于是我提示他改用C语言,不include头文件。于是编译通过,并且AC。

int main() {
	execlp("/bin/cat", 0);
	return 0;
}

然后我们打算再试试权限,结果发现在裁判的机器上写个perl脚本,并调用perl执行也是没有问题的。下面的代码也AC了。

int main() {
	void *fp = fopen("cat.pl", "w");
	fputs("#!/usr/bin/perl -p\n", fp);
	fclose(fp);
	execlp("/usr/bin/perl", "", "cat.pl", 0);
	return 0;
}

调用setrlimit更改堆栈大小更是不在话下。更出格的我们就不敢试了,结论就是这功能完全就是花瓶。怎样都能绕过去么,最万能的方法就是通过宏里的字符串连接##。

#define FI_LE FI##LE

后来LAF过来打酱油,说到代码大小有限制。当然主办方后来就说了,源代码大小限制64k,这也就罢了,提交失败后还算一次罚时!估计这也不是他们本来的规定,没办法,系统里就这么写死了,于是就赖着不改了。后来又悲剧地发现30s内不能连续提交的sb限制,极其无语。我们提意见后,强势的主办方直接54之。另外系统没有broadcast功能,关掉再打开,之前所有记录都到/dev/null里去了。而且后来我们的系统还莫名其妙挂过一次……

总之对这个系统无可奈何,所幸这些问题在正式赛中没有发生在我们身上,也没有发生在别的队伍身上。

10月25日(◯)

正……式……比……赛……了……!

比赛前的等待时间真是相当的不爽,先是被晾在室外站了一个小时(当然和参加◯◯方阵排练的同学们比算不了什么)。然后也不知道是谁在挑战谁的底线,虽说像合肥那样入场后没有规矩不太好,但像上海这样把所有参赛者都当成犯人一样才真是恶心,广播里的泼妇骂街式的叫喊听着相当烦人(比较一下,WF里的Do Not Touch Anything实在是可爱啊)。后来貌似要发布点有用信息的时候话筒坏了,变得一顿一顿的,也许是主办方高估大家了,反正不管说的是中文还是英文,我都听不懂……(反正我说了,听不懂是你们自己的责任^ ^)不过这倒是很好地活跃了一下现场的气氛^ ^

これから本番

比赛开始,寒mm负责搞机器,我拆题,然后我看ABCD,寒mm EFG,jay哥HIJ。上来我就直接把A跳过看B去了,看来我真的很能pass水题,这种情况也已经不是第一次发生了。B看完后就推出了结论,一开始没注意规模,我居然去写了,刚写就发现不对劲,下来把其他题看了。开场实在是相当脑残。而有队伍10分钟就过A了,在一看A是水题啊,可是我想去准备B,于是让寒mm写A。

A没发现什么好的生成邻接表的办法,于是人肉,程序也花了不少时间,调过sample后WA了。打印,寒mm和jay哥检查,而我去写B。中间寒mm发现了错误,我改了这个错误以后终于在一个小时的时候过了A。

B写了挺长时间,而且没有过sample,只好打印检查(这回送打印的速度真的不敢恭维)。后来发现几个小错误,调好以后过sample也WA了。发现输出的地方可能运算溢出了,改了一下,没敢马上交,用python写暴力算法拍了几个数据,再三确认后提交AC。

看到有队伍过F,寒mm想写dfs试一下,虽然我觉得应该要加剪枝,但是也没什么好的想法,机器又空着,于是让他去写了。而我和jay哥讨论其他题,当时J过的队伍比较多了,不过我们还没很好的写法。后来F TLE了,于是被丢在一边。

不知不觉比赛就要过半了,而我们只有两题,而且机器还悲剧的闲了下来。这时候寒mm对我说I是不是可以利用选择一个点在同一直线的两个邻居和在另一直线上垂足的两个邻居中贪心。虽然贪心不怎么有前途,但寒mm提醒了我只要用这四种边构图求最小生成树就可以了。于是寒mm敲生成树和点到直线最近点模块,我写构图,完成了I,但不过sample。debug发现是我对点排序反了,改正后测了几个数据没发现问题,提交后1y。这是本场比赛我们第一次1y。

过完I以后,寒仔给我讲E题,我觉得这道题比较有前途,决定这场比赛最后就攻这道题。而J的重任则交到了jay哥一个人身上。以下过程基本是我们有时间就上去写代码,调试代码,然后打印检查。J题发现题意理解错一个地方过不了sample,最后jay哥决定用复杂度稍微高点的算法试试,过了sample,保险起见测了几个数据没有问题后也1y了。赞。

最后全力的功E,E的写法就是用set保存每列哪些位置有方块,再维护一个链表记录那些没有消去的行表,与及这一行的方块数。E写的时间不算太多,但是写完却没有过sample,RE了。printf,gdb都用上,发现是人肉的数组下标有问题,改过以后离正确解进了一步,还是WA。再看人肉的数组也有问题,于是再改,这次只有最后一个方块位置错了。猛然发现计算下落后位置的程序判断的地方有bug,于是改写insert函数,改完以后又RE了,发现完全没改对,接着改,再改,终于过了sample,比赛已经接近尾声了。立马去掉调试信息,测sample,提交,等结果,再测sample,然后返回了yes!在298分钟的时候我们过了第五道题,赞!

比赛结束后看到了前来围观的vls, xls和vbvan,FM则过来聊了几句后先赶回杭州了。

颁奖&版聚

晚上颁奖会,由于按奖分配了位置,也就没什么悬念了。会上GB又让大家拍了很多手……颁奖会后合影,于指导屡试屡败,浪费大家感情……

晚上版聚,大众那边实在无处可去,于是我们先乘车到维也纳,然后步行到一家KFC。路上某几只一直在唱曾哥的歌……在KFC吃饱喝足后打的回郊外的酒店……感谢xls和vbvan的bg。

小结

最后比赛的结果,我们是队伍排名第四,学校排名第三,排在我们前面的是清华和上交的队伍,他们分别过了8, 7, 6道题,于是感觉到差距啊……这次比赛前期的表现真的很糟糕,尤其我整个状态都不太好,我们队不但过题慢,还WA了几次,debug了不少时间,晃晃乎乎赛程就过半了。好在后半程会过神来了,不然就得杯具了,这还多亏了队友,J基本后面就是jay哥独自搞出来的,I多亏了寒mm的提示,E也是我和寒mm共同努力拿下的。这也是yukkuri的告别赛了吧,从集训到组队,一步一步,一场比赛一场比赛过来,我觉得不论是我还是我的队友收获真的很大。yukkuri的进步也很明显,也取得了不错的成绩。

结束了今年的比赛,希望能找点地方好好大酱油。祝去合肥和泰国的zjuer能取得好的成绩,能够如愿。也祝愿今年zju能在Final上取得好的成绩。

PS: 现在大家都是多一事不如少一事,所以面对甲流风险办比赛挺不容易的。DHU也为这次比赛投入了大量的人力物力财力,主办方辛苦了。不过不得不说的是在某些方面,尤其是作为比赛选手来看,这次组织确有不足之处。

PSS: 复旦的出题质量是非常不错的,自愧不如啊,令人羡慕啊。尤其看了解题报告觉得自己好弱啊。不过这次的题少了点简单题呢,最后太多2题1题的Rank不是很好看呢。

	无限仰慕8题夺冠的Intrepid
	恭喜WHU取得三金,令人羡慕啊
	算起来FZU应该是出线了呢,恭喜恭喜
	友情摸摸bitset,你们缺了点经验和运气
	强烈鄙视LAF,搞什么啊,到武汉将功赎罪吧
	祝浙江大学ACM队在武汉赛区旗开得胜!
	祝浙江大学ACM队在泰国赛区旗开得胜!
	
Leave a Reply