记 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 中能够赛出更好的成绩吧。

comments powered by Disqus
使用 Hugo 构建
主题 StackJimmy 设计