再见了,ACM-ICPC

终于还是来到了这一天,当双手在键盘上敲下这些文字的时候,竟有些颤抖。尽管曾经不止一次的思考过退役后的场景,也做足了充分的思想准备,但当这一刻真的到来,却有些不知所措。看着ACM交流群里热烈的讨论,关上窗口,退出该群;将ACM资料小心翼翼的放置在移动硬盘的角落,不小心瞥见NOIP退役时存放的资料,记忆一下子席卷而来。在算法竞赛的道路上跌跌撞撞的行走了将近五年,从NOIP到ICPC,是时候说再见了。

此时的我,依然记得多年前第一次提交A+B时的激动,记得思索半天推导出Segment Tree时的满足,记得苦思冥想理解Dancing Links时的欣喜,记得写完几本草稿本后证明Binary Indexed Tree时的顿悟,记得那无数个奉献给《数据结构》和《算法导论》的日日夜夜,记得一遍遍的WA和随之而来的AC。记得那一个个打训练赛的下午,匆匆忙忙地胡乱吃完从后庄带来了晚饭,便投入下一场比赛。记得水平日渐提高时的欣喜以及发挥失常后的焦急。

那无数在实验室刷题的时光,除了让我体会到了较之高三更为枯燥的生活,却也给我带来了些许快乐。一群人讨论时事热点时的激烈,徐老师突击检查时的尴尬,准备题目汇报时的担心,为新生赛出题的忙碌,准备新生授课的紧张以及北疆饭店里的谈笑风生都将成为珍贵的记忆,小小的实验室,承载着一群人的梦想,不断的奋斗,只为接近更广阔的天空。

四场比赛,从上海开始,再到长春,辗转北京,最后回到上海,两铜两银,在最后的EC-Final中夺得银牌,虽然无缘World Final,但也算是个不错的成绩。

第一场比赛是华东理工大学承办的上海邀请赛,铜牌,身为常年铁牌的弱校选手,第一次参赛拿到一块铜牌也是意料之外。回来以后便和队友商量,区域赛一定要拿到苏州大学的首枚银牌。第二场比赛是东北师范大学承办的亚洲区域赛(长春站),在我们奋力拼搏五个小时以后成功收获一枚铜牌,为此队友们都低落了许久,徐老师却安慰我们好好准备,还有机会。第三场比赛是北京大学承办的亚洲区域赛(北京站),银牌,不负所望,成功晋级EC-Final。最后一场便是上海大学承办的EC-Final,以银牌收尾。

我的算法竞赛道路也就到此结束了,退役的原因很多,一方面作为一名电院的学生,本身课业压力较大,无暇分心;另一方面也是想多接触一些工程,将所学的算法竞赛知识运用于实践。

故事很长,就像一场长长的宴会,大家说说笑笑,戛然而止,来不及一一道别。

感谢一路帮助过我的父母、老师和朋友,陪伴我度过快乐的ACM生涯。

感谢曾经的队友,我会记得你们CARRY过我的每一场比赛。

感谢ACM交流群,和大家谈笑风生是我的荣幸。

最后,愿我们都前程似锦。

2016

当我习惯性的在博客写下这个标题的时候,才发现2016又是一个闰年。且将这篇文章的内容定位在总结与展望吧。

回顾整整一年,学到了很多知识、参加了很多比赛、去过了很多地方、也认识了很多朋友。

前段时间,有一个问题一直在困扰着我:在复习完《模拟电路》后,发现全书讲了很多的方面,但是好像很多东西都是浅尝辄止,并没有触及问题的本质;在如同《信号与系统》,虽然向读者呈现了傅里叶变换以及拉普拉斯变换这两个优美的积分变换,但是却闭口不提它们当时是如何发现的,也不会如同《数学分析》那般严谨的证明其正确性。

由此引申出来,我们寒假需要为ACM集训队的新队员授课,当我将我的授课内容拿出来和队友商量时,他们都认为讲算法时候不要涉及太多的原理以及证明,然而我却认为在没有清楚原理和证明之前,即使能够熟练运用,但却还是不能内化为自己的知识。正如前几天保研南大、腾讯实习的学长尝试性的与某公司视频面试,当时我在他边上,当对方提及一些算法的时候,我们都可以应对自如,但是当对方问及,请证明这一算法的正确性时,我们却都有些为难。

下面是不得不提的ACM实验室,这一年所有的假期基本都在实验室度过,从寒假的留校培训,到暑假的赛前集训,整天的日程便是学习和刷题。可以说,我们队伍算是较为幸运的,一共参加了4场比赛,分别在华东理工大学、东北师范大学、北京大学、上海大学,也取得了较为不错的成绩,具体可以参加这两篇文章:《记2015 ACM/ICPC上海大都会赛》《记2015 ACM/ICPC亚洲区域赛(长春站、北京站)》,其中上海大学的比赛总结暂时还没有动笔。

此外,还参加了全国大学生电子设计大赛,与两位大三学长组队,准备阶段制作了四轴飞行器,最后比赛时由于各种各样的原因临时换题,虽然三天只睡了8小时,比赛结果也不是非常满意,但是在这个过程中却学到了很多东西。

关于项目方面,今年大大小小一共完成了5个项目,前阵子把今年的项目全部结项的时候,本想指望着可以稍微休整几天,但是目前已经有3个明年的项目开始立项。

最后,不得不提的是在剑桥的半个月时光,它使我领略到了一种完全不一样的生活习惯以及思维方式,以前只是在文章中读到“开拓了眼界,拓宽了思维”,当这些事情真真切切的发生在自己身上的时候,才能体会到这种文化的冲击所带来的感受。当我第一次踏上这片土地,就被那蔚蓝的天空所震撼,呼吸着新鲜的空气,拥抱着久违的刺眼的阳光,再加上田园式的环境,使我产生了一种「久居樊笼里,复得返自然。」的感觉。从剑桥回来以后,一直想写一篇文章来记录记录这如梦般的半个月,但是无论怎么写,都无法表达我的想法,所以也就只能作罢。或许这些经历将会如同那些我读过的书一般,最终成为我的血与肉。

以上大概是2015的缩影,一言以蔽之——有些辛苦,却也非常值得。

至于即将到来的2016,一切都会更加美好。

记2015 ACM/ICPC亚洲区域赛(长春站、北京站)

细细想来,已经有近四个月没有更新过博客,上一次还是在7月份。既然这样,那就从那时候讲起吧。

整个暑假,绝大部分时间在参加ACM训练,除此之外,还参加了全国大学生电子设计竞赛,拿了个一般的奖项;去英国走了一遭,体会了不同的风土人情。一直想好好记录这两件事情,但总是由于各种各样的原因搁置了。

这学期自从开学以来就一直非常的忙,刚开始备战ACM,上个月在长春拿了一块铜牌,上星期在北京拿了一块银牌,周三刚刚把FPGA设计邀请赛的作品完成,明天一大早赶往上海交通大学参加微软Hackthon大赛,下周需要提交全国移动互联网开发大赛的作品,再加上最近期中考试周,几乎忙的没日没夜。

这几天难得有个喘息的机会来,却发现自己已难以适应如此清闲的生活了。思来想去,不如把这两次比赛过程中的所见所闻写下来,权当回忆罢。虽然前往北方这两个城市的目的是比赛,但是我却希望在这篇文章中淡化比赛的内容,一来比赛的内容对于大多数读者来说较为陌生,如果不是参加过类似的比赛,很难感同身受;二来比赛的情况已经反思总结过,也没有必要再拿出来写一遍。因此,我想尽可能的把整篇文章的重点放在整个旅途的过程,我所见到的、遇到的人和事。

当暑假里进行的网络预选赛结束时,我便想去北方的赛区经历一番,主要原因是没有出过什么远门,想出去见识一番,顺便可以拿个奖回来。最终分配给我们队伍前往长春(东北师范大学)、北京(北京大学)这两个赛区。

先来说说长春赛区,这也是我第二次坐高铁,第一次是去年的上海邀请赛,可以参阅《记2015 ACM/ICPC上海大都会赛》。从苏州到长春,11个小时、1000多公里的路途,体验了从短袖到毛衣的气候与风景。在去的途中,坐在我边上的是一位在苏州从事医疗工作的长春人,听说我是苏州大学的学生,便和我聊了起来,不停地向我推荐长春的旅游地点,使我深切的感受到了东北人民的热情。

当然,到达长春的时候,我才发现曾经的东三省,如今是如此的破旧。可能由于气候的原因吧,晚上七八点钟在路上已经看不到什么营业的门店,大多都已打烊。所幸当时并没有暖气,所以空气质量虽然不是很好,但还能接受。

报道的时候,专门负责接待我们学校的志愿者早已等候多时,这也不由得使我感到一阵惊喜。简单的手续后,志愿者在我们带队老师的请求下,带领我们参观了东北师范大学。学校不大,但是富有现代气息,宿舍楼更是高达二十层,此外,我们还去了隔壁吉林大学串门。第一天走下来的感觉便是破旧,即便是白天,想要在大街上找一家像模像样的超市也非常的困难。

第二天,我们便开始了正式的比赛,从上午9点到下午2点结束,然后颁奖,闭幕式。吃完晚饭,一直到晚上6点才结束。接下来却无奈的强行被拉到KTV唱歌以庆祝比赛顺利结束。晚上9点多钟出来,同学叫来了吉林大学的同学,想让他带我们逛街,然而正如前文所说,所有的商店都已关门,我们就这样在黑夜中顶着零下一度的温度在东北的马路边行走,最终回到宾馆附近的一家烧烤店吃了夜宵才回去睡了。

在归途中,由于接下来要考试,所以便一直在复习。当我准备休息一会的时候,坐在我边上的旅客突然跟我说,你解微分方程的速度真快。于是便聊了起来,对方表示已经工作,希望我能够在大学里好好学习。临走时戏谑地说,我要是再跟你聊下去,就要和你去苏州了。

经历的第一次的失败,我们非常希望能够在北京赛区拿到一块银牌,也算是对自己过往训练的一种肯定。但是我们都知道,北京是所有赛区中难度最大的,因为所有的强队基本都会去,而奖牌是根据百分比来评定的。也就是说,同等的成绩,可能在长春可以拿到一块铜牌,到北京,可能连一个牌都拿不到。因此,这一个月大家都或多或少的有些许压力。最后两次训练赛的时候进入了银牌区或许给了我们些许宽慰。

前往北京的旅途虽然不及长春的一半,但却更加艰难。由于比赛与一门考试冲突,在院教务主任、院长、校教务之间辗转多次,终于办完了缓考申请,院长签字的时候,语重心长的说:好好比,拿一块银牌回来。

当我走下动车,踏上北京的土地,感受到的是帝都强烈的雾霾,直教人难以呼吸,以至于后来拍照时竟然以为自己的摄像头坏了。当我们来到宾馆,看到破烂不堪的房间和高昂的住宿费,不禁感叹帝都人民的生活。与长春类似,我们报到当天参观了北京大学,这座历史悠久的名校,在未名湖畔,眺望密檐宝塔。感受到了强烈的文化冲击,或许这就是一个学校应该积淀下来、传承下去的东西吧。

正式比赛时,进入场馆,不禁怔住。这是2008年承办北京奥运会乒乓球比赛的场馆,头顶“Beijing 2008”的字样依旧一尘不染,展现着它的光辉。开幕式时,各位国际嘉宾纷纷致辞,中英对照,使人仿佛置身于国际决赛的现场。5个小时的比赛很快便过去了,而颁奖阶段,却着实进行了两个多小时。这使得一位与我相识多年特地从北京师范大学赶来希望和我见一面的网友在寒风中等待了一个多小时,颁奖典礼结束后,我才得以从场馆出来迎接他。

我们多年的交流虽然只是通过电磁波作为媒介传递着消息,但当我们真正见面时,却如同多年老友一样亲切。在北大艺苑餐厅吃完晚餐,稍作闲逛,便和他前往北京师范大学游玩。当我晚上8点多钟坐地铁返回北京大学时,在夜色中,来到一个邮筒旁,投递了近十张明信片,也算作是和朋友分享自己的所见所闻。

今年的比赛也就随着北京赛区的结束而落幕了。

The Freshman Grind

想来放假已经好几天了,总算抽出了一些时间来总结一下这学期的经历,虽然在期末考试期间应导师要求写过一篇《学期总结》,然而由于复习紧迫,只是草草收笔,并没有点中要处。

Grind of Courses

这学期刚开始,或许是由于上学期不错的成绩造成的盲目自信,导致了上课时间并没有特别认真的听讲,大多数时间在自己看课外书,比如《暗时间》、《浪潮之巅》等(不得不承认,这些都是不可多得的好书,前者介绍了如何高效的利用时间;后者介绍了近几十年信息技术产业作为信息产业的发展史,其中涉及了各大知名公司,例如Apple、Microsoft、AT&T等的衰亡)。当然,造成这种结果除了主观因素外,不可否认还有一部分客观因素:由于教师们不急不慢的授课速度,使得我不需要太快的思路就可以跟上甚至超前他所讲的内容,几番下来也就不想再听讲了,然而事实证明这并不是一个非常好的选择。

期中考试的时候,就吃了不怎么听课的亏,导致节节败退;到了期末考试,通过一阵子的学习,将所有的内容全部赶上,并且在期末考试中取得了较为不错的成绩,但是由于期中考试并不是非常理想,导致最后的总评不是很好看,虽然两个学期的总评还过得去。

还记得上学期的时候,每节课都不缺,每次都认真听课, 但是发觉很多时间听课都是听老师讲过的东西,或者自己已经会的东西,真正不会的东西其实所占的比例并不是很大,再结合这一学期不怎没听课,但是通过自学,也感觉学的和上学期的扎实程度差不了太多,因此对于学习方法有了一个较为大胆的想法——全部自学。这样可以省下很大一部分的时间,可以做我感兴趣的事情,学我感兴趣的课程。

在一次外出参观Rigol公司的时候,和班主任聊天的时候和他提出这样的一个想法,带有咨询的态度去和他交流,本以为班主任会有些反对,没想到班主任对于我的想法表示出了较大的赞成,并且说出了一个令我信服的理由——教师上课的时候只会挑课本中的一部分讲,而自学则会从头到尾的学习一遍,真正的做到融会贯通,同时获得的能力上的提升,也不是听课可以学来的。同时,他也希望我可以通过这样的自学,取得较好的成绩,总的来说,他非常支持我做这样的一个尝试。

通过这一系列的思考和交流,我开始制定了自己的自学计划,希望可以在暑假期间可以自己看完《Complex Variables》。我并不认为学习一门课程非要使用我们学校规定的教材,我希望找一本深入浅出,涵盖面广的书进行学习,通过对图书馆书库进行一系列的搜寻和比对,结合之前借阅《Circuits》参考书籍的经验,感觉国外的教科书总是可以从最为基本的入手,到最后讲的也非常的深入,较国内的大部分生硬的教材来说更有吸引力,可以同时提升英语能力也是一个非常重要的因素。

Grind of Projects

说到项目,为了体验本科生科研的感觉,这学期揽下了两个项目,其中一个是项目负责人,一个是项目参与者,然而事实证明,这个选择也是不太明智的。

首先说说我作为负责人的项目——掌上敬文移动客户端开发。当时招募人手的时候有很多人踊跃报名,通过筛选,选出了一些有一定开发经验的人员,最后定下了一个6个人的开发团队,负责Android以及iOS两个移动端的开发,还从计科院找了一位指导老师。然而最后的结果就是——指导老师撒手不管;分配任务时,团队人员不是没有时间,就是以不会推诿。最终整个项目就落在了我一个人的头上。还记得当初揽下这个项目时,舍友跟我说的一句话:「当你做项目负责人的时候,就要做好一个人做完项目的准备。」现在想想这句话还是很在理的。通过这次经历,至少让我觉得项目团队中的人员实力差距不能太大,同时自学能力是科研最为基础的能力。当然,我觉得最为重要的一点是——目前的本科生科研现状大多只是为了一个名号,走一个过场,把别人发明过的东西再发明一遍,或者把国外的东西搬过来翻译一遍,而不是真正的投入科研,或许在某种程度上大部分本科生并不是非常适合做科研。

其次是作为参与者的项目——四轴飞行器的制作。这个团队只有3个人,两个大三的学长再加上我。加入这个团队主要是学完了51系列的单片机,想继续深入学习STM32系列的单片机时,正好有这样一个契机,因此就和他们合作,同时还可以顺便参与一下今年的全国电子设计大赛。然而当我真正开始着手做这个项目的时候,我才发现自己知道的实在太少了,四轴飞行器的理论要求还是很高的,为此看了很多篇四轴飞行器物理模型、控制算法的论文,但是依然感到略有吃力。

除此之外,我还需要每天坚持ACM训练,基本上早上出去上课,晚上在实验室呆到11点才回到宿舍。

这三件事情就像三座大山一样压着我,使我喘不过气来。有时候我想放下这些事情,让自己去做一些别的事情,然而没过多久,就会发现还有一大堆事情没有处理完,但是却力不从心。以至于放暑假前学长推荐我去带薪实习,我都抽不出空来。有时候我觉得它们似乎在告诉我:你累了。

Grind of Interests

这学期的《艺术审美》课程,虽然对于讲座内容有时候兴趣不是那么浓厚,但是却使得我作为一个毫无艺术细胞的人对音律和绘画产生了兴趣,我觉得这大抵是最大的收获吧。喜欢在书画室内临摹名家的画作,虽然一幅山水需要很长的时间,但是我却从中得到了难言的乐趣,当看到墨水在纸上化开,感到自己的心胸得到了开阔,心境得到了提升;喜欢到钢琴房去练习钢琴,当音符从指间泻出的,感到自己的心灵得到了洗涤,身心变得无比的宁静。或许这就是艺术的魅力所在吧,我也渐渐的理解了为什么那些历史上的画家、音乐家虽然生活贫瘠,但是他们好像比任何人都富有,因为他们拥有自己的本心。

Grind of Future

在学期快结束的时候,我突然意识到,我的大学生活已经过去了四分之一,而我在这一年中,我并没有取得自己所想要得到的成绩。在这一学期的忙碌中,我似乎并没有太多的时间去思考,感觉自己就像是被推着前行。或许我需要更多的时间去思考,而不是用来平庸的忙碌。我认为Definiter的这句话说的非常有道理:

每当我看到那些 20 岁的健壮的形体时,我都会想起自己孱弱的身躯;每当我看到同龄人做的那些令人惊叹的事之时,我都会想起自己的碌碌无为;每当我看到本科毕业生拥有的坚实能力时,我就会想到大学只有四年,已经没多少时间了。我明白成长不是一件急于求成的事情,焦虑之后,只能亲力亲为。

在过去,很多事在变好;在未来,一切当然会变得更好。

记2015 ACM/ICPC上海大都会赛

到今天为止,距离2015 ACM国际大学生程序设计竞赛上海大都会赛结束已经快有一个星期了,趁着记忆中暂存的些许余温,将其记录下来。

我们从上周四开始,放下手中正在做的题目,转而准备比赛所需要的材料。由于比赛是可以携带纸质材料进场,因此我们准备了一些较为常用的算法模板,并且幻想着可能会遇到类似的题目。然而事实证明,携带的这些模板并没有什么作用,当然,这是后话。

周五晚上,我们开始整理行装。由于第二天早上需要六点半之前集合,所以便早早的入睡了。早上起来稍微打点一下,已是六点。草草地吃了一块面包,关上宿舍门便出发了。走到外面才发现宿舍大门紧闭着,原来此时舍管阿姨依然沉睡在梦乡。走近时才发现,宿舍大门是虚掩的。来到实验室已有两三个人在等候,陆陆续续地都到齐了。

就这样,我们六名队员踏上了前往上海的征途。一路上地铁-动车-地铁-步行,费尽周折终于找到了指导老师早在一个月前为我们预定的酒店。放下行李,躺在床上休息了一会儿,便前往华东理工大学(徐汇校区)报道。无奈一开始不认识道路,以至于耽搁了很久。

报道结束后,领了材料赶去吃中饭,饭菜只能说一般般而已。接下来的开幕式只用了短短的十分钟便结束了,然后便是热身赛(主要用来熟悉比赛场地以及比赛的系统环境)。比赛场地在体育馆内,一共将近两百台电脑,一个队伍(3名队员)一台电脑(Linux系统)。裁判拿着话筒选读比赛须知,志愿者则站在门口迎接我们。

在热身赛中,一共有三道题。第一题是高精度乘法(C/C++语言内置的变量类型保存的数据是有一定范围限制的,如果要操作成百上千位的一个整数,就需要使用数组来模拟整数的每一位,并且结合竖式的方法,模拟加减乘除运算,称之为高精度算法),我们在短短几分钟内就AC(Accepted,即作答正确)了。然后在接下来的一个半小时内看着其它队伍的牌子上插满了气球(做出一道题目就会有一个对应的气球),而我们却一直做不出来。第二题直觉是二分图匹配,却不会建立图论模型。第三题已经忘记了。和学长他们一样,我们两个队伍都只做出了第一题。

热身赛结束后便去吃晚饭,一开始有一个World Final的选手邀请大家去吃晚饭,当我们走到校门口的时候突然感觉无颜参加这样的集会,就直接回到了宾馆。到这时候才意识到忘记在学校里顺便吃一顿晚饭,于是乎就近找了一家饭店。等到饭上来的时候才发现饭碗小的可怜,而我一连叫了三碗饭,被服务员惊诧的看了几眼。回到宾馆后,做了一场“百度之星”,准备休息的时候,我的队友过来串门,拿了一包薯片,然后发现我的门口被塞了两张卡片,写满了广告。

第二天一大早便起床集合,指导老师徐教授也早早的到了,来到楼下的自助早餐厅,吃了一顿不错的早餐,回到房间再稍做休息便启程出发。来到比赛场馆,坐到昨天的位置上。桌面上放着一个信封,装着三份试题。等到10点整的时候,裁判宣布比赛开始,我们打开信封,抽出一张写有登录密码的纸条以及三份试题,开始了紧张的比赛。

第一道做的题目是运用贪心算法的区间覆盖问题,就如热身赛中一样,短短几分钟内就AC了。接下来,我又发现了一道表达式求值的题目,发现和前几天做的Basic解释器差不多,因此没有多想就开始写代码,提交代码后返回的结果是TLE(Time Limited Excceded,运行时间超时,题目要求在规定的时间内给出正确的答案)。在队友的提示下,发现这道题目并没有那么简单,因此就将它放到一边。(事实证明,这次的决策是正确的,使得我们在这道题目上浪费过多的事件,一直到比赛结束,只有一个队伍作出了这道题目。)我们AC的第二道题目是队友思索了半个小时想来的,一个简洁的公式,再配上一个高精度乘法即可。第三道AC的题目是由我和另外一个队友合作完成了,实现一个Base64的加密方法(我们使用的是C++语言,而Java语言这一加密直接可以调用内部函数,奈何我们都不会)。第四道AC的题目我们整整思索了一个半小时,是一道有趣的数学期望问题,可以将它描述出来:

给定一个\(N\times M\)的方格,每次可以选择这\(N\times M\)个方格中的任意两个(可以重合),将以这两个方格为左上、右下的矩形方格全部填充上颜色。一共进行\(K\)次操作,求最后被填充上颜色的方格个数的数学期望。

在此不给出具体解法,读者可以自行思考。至此,我们一共做出了4道题目,排名第34名,一度以为有银牌了,最后事实证明与银牌擦肩而过。在剩下了的两个半小时内,我们一直在思考另外一道概率题,以及一道数据结构的题目。期间志愿者过来发午餐——85°C的面包和奶茶,然而却根本没有心思去吃,嚼了几块巧克力便继续思考。

比赛结束以后,举行了一个讲座,主要是给赞助商做一些公司的宣传,希望应届选手前往应聘。颁奖典礼上,得知是铜牌第一的时候,只是感觉自己太弱了。在这期间,终于意识到了自己还没吃午饭,于是吃完了所有的面包。恰巧这是颁奖典礼结束,徐老师说带着我们去吃晚饭,而我刚刚才吃完一袋面包,徐老师说,你怎么吃这么一点点。接下来,地铁-动车-地铁,又踏上了铜牌滚出的路程。

总的来说,第一次参赛给了我很多的经验,这与高中是参与的NOIP竞赛不同,更讲究团队合作,以及思维的巧妙,而非看完题目按照常规方法就能够按部就班的解答的。要说这次比赛还能有什么别的意义的话,我想就是圆了我一个从高中就有的参加ACM的梦,希望在接下来的Reginal中能够赛出更好的成绩吧。