原文发布在珞珈山水 BBS 的 ACM/ICPC 版, 这里也是原文, 不想修改了, 估计很可能这也是自己这个分类的最后一篇文章了.
剧终, 青春散场
–告别赛记 by snoopy
晚上的时候在 2006WHUACM 群公告里写下 “Moonmist解散退役” 的时候, 才真的意识到 “剧终” 这两个早就想好的告别词的伤人. 又是一个组建一年即解散退役的队伍, 只是, 去年的 KMXS 到后来我更多的是一个看客, 今年的 Moonmist, 自始至终, 都是我们三个主演.
11月19号中午出发去上海, 20号到达, 搞定住宿. 21号大巴把我们拉到上大新校区, 开幕式. 完了是教练会议, 第一次参加, 应该也是最后一次参加吧, 看了看是怎么抽签的, 自己也参与了提问, 问了一些在北京让我们失误的影响因素. 上海奖项设置是 10 金 20 银 30 铜, 比北京多, 但是因为队伍都很强, 其实局势更恶劣, 至少是金牌几乎是没希望的, 而北京冲金是有很大空间的, 最后定位是银牌保本, 最好能靠前, 能拿金牌就赚翻了.
中午吃完饭后去看了看比赛场地, 在一个大体育馆里, 一共 116 个队, 赛场安排的非常有气氛, 我们在靠中间的位置, 能对场上局势有比较好的把握.
下午练习赛, 3题有2个是简单题, 结果都被我抢了, 剩下的那个太郁闷, 到最后也没出来, Tank还说键盘都没摸到, 要敲敲玩玩找一下手感. 练习赛后是 SUN 的活动, 算大学技术日了吧, 介绍了一下 Solaris 和 SUN Studio, 也算是为后来人做一点基础培训, 毕竟从今年的西安开始所有大陆赛区都要改用这两个东西了. 当时 Moonmist 的人都是笑笑, 对我们一点影响没有, 我们不会参加以后的比赛了, 除非是进 Final, 不过 Final 不是那么好进的, 进了 Final 也未必是 Solaris, 即使参赛, vim + gEdit 的使用跟系统一点关系都没, 特别是现在 Solaris 也是用的 GNOME.
21号晚上招待晚宴, 上大很奇怪的把招待晚宴放在练习赛后而不是正式比赛后. 没有比赛, 没有成绩, 吃饭的心情依然是沉重的, 没喝酒, 也不敢. 晚上早早睡下, 为第二天准备, 不知道是不是因为还是害怕是自己最后一场比赛的原因, 半夜无光无声的宾馆房间内醒了好几次看时间, 确认没到起床的时间又草草睡下.
22号正赛, 原定 9:30 的进场推迟到了几乎 9:50, 入场后以为要推迟比赛开始的也并没发生, 宣布比赛开始的也只是现场的一个 Volunteer. Moon 拆密码信封登陆系统开 PC^2, 我拆赛题信封并分发. 10题, 按老规矩我从前面开始, Moon 后面, Tank 中间.
我看完 A 后就立即判断是个简单题, 就是上海赛区的决赛选拔规则, 过 k 题可以进一个队, 参见过 Final 并且前 20 名加一个队, 举办了 Local Contest 的加一个队, 抉择一下决定后面题目不看了, 直接上去敲, 看题的任务交给 Moon 和 Tank. 很快敲完, 这个时候场上已经有队过这题了, 交了后 WA, 立马想起估计是我对题目一个细节理解有问题了, Sample 给的极具欺骗性, 同一个学校过 k 题的如果有多个队伍也只能是有一个队能以这种形式参加决赛, 完全遵循上海的规则, 加了个判断后提交 Yes, 第一个红色的气球送来, 我暗暗骂了自己一下干吗要怀疑规则, 既然都说是上海规则了那就是跟实际情况完全一致而不是有修改.
Moon 和 Tank 分别交流了一下题目意思, 看懂了 I 的题意但是不好写. Tank 看的 D 题意也简单, 平面上 n 个点, 画一个矩形使落在矩形边线上的点最多, 离散化后其实就是在一个 n*n 的棋盘上操作, 但是 n<=100 的数据量我只能想到 n^4 的算法, 怕超时也先放下, 看其他的题. 我看完 B, C 后 Tank 看完 E, Moon 看完 H, 但是交流后都没好想法, 而赛场上这个时候过 C, D, I 都有, 并且 C, D 居多. 我跟 Moon 说清楚 C 的题意后对题目数据理解产生分歧, 因为从题意来理解输入的应该是一个无根树, 只要 dfs 一次即可, 而数据输入说是 10 万的点 100 万的边. E 交流后 Moon 判断是一个第 k 短路径, 但是写起来很烦, 其他题都太长而暂时没看懂. 把 C 的题意重新读一遍并讨论后认定题目数据在唬人, 输入只可能是一个无根树, 最多是有自环, Moon 上去写的时候害怕堆栈溢出, 准备手工实现递归堆栈, 但是太烦还是放弃直接写的递归, 交上去没有 RE 而是 WA, 修改一个小细节后返回 Yes, 第二个白色的气球也来了. Moon 做 C 的同时 Tank 和我在推 I 的杨辉三角, Tank 给了一个 O(n) 的累加式, 考虑 n 是 10^9 的数量级的所以我们将其化简到了 p + n%p 级, 但是 Tank 上去写后调了几个自己的数据发现就有问题, 于是下来. Moon 开始上去写 E 的第 k 短路, 因为是写的很熟的算法, 所以 Tank 对 Moon 也很有信心, 我不熟悉图论但是觉得写起来可能会非常的占机器, 不过既然没题敲, 也只能这样了. 比赛的时候发现真的还是会紧张, 我在不停的上厕所, 回来看剩下的题, 都很长, 并且心里有些烦, 都没能看下去, 不过题目本身也很难, 所以还没造成太坏的影响. Tank 推 I 没想法, 我说具体数学上应该有, 于是翻了一整章最后在一个习题上发现一个公式, 感觉会有用, 给 Tank 后他再看了一些定义再开始化简, 把时间复杂度减低. 我实在没题做问了 D 类似一个问题 (矩阵里求小矩阵使矩阵内数值和最大) 的 n^3 的加速算法, 知道 n^3 做法后觉得无法套用, 并且看场上那么多人过决定写 n^4 的去水, 因为也只能想到这个算法了, 并且我是优化后的, 是系数远小于 1 的 n^4 记忆化搜索. Judge 在 PC^2 上有提示说 B 的 Sample 有问题, 不过看了后认定就算有问题我们也没法拿出好的算法, 只能是16! 级别的, 最多也只是 16!/8!. 我很快敲完 D 后提交, 居然直接返回的 WA, 没有 TLE, 这时 Moon 提醒我直接的扫描有没有多算点或者少算点, 略加思索有发现我考虑的只是枚举矩形左上角和右下角, 右下我有判重, 而坐上没有判重, 加了一个修正后就 Yes 了, 第三个土黄色的气球. 刷了一下 Rank, 大概在银牌和铜牌交界的地方, 很玄. Tank 推出 I 的公式, 上去写但是错了, 这时时间不是很多了, 我跟 Moon 说如果 E 不好写就准备放弃吧, 毕竟赛场上还没一个队过这题, 我没看 Rank, 但是猜应该也没太多队做, 不过这种图论题都是想到做法就很简单的, 何况 Moon 也是写的多了, 但是写太久了似乎也有问题了. Tank 跟我说了 I 的思路, 并给了我最新的打印出来的程序, 不过我看了看觉得很麻烦, 同时 Tank 说的做法似乎很简单, 于是准备自己写, 才写完一半 Tank 那边已经返回了 Yes. 第四个淡黄气球送来的时候已经是只剩下 40 分钟了, 看了看封 Board 时的 Rank, 当时过 4 题的有 18 个队, 最后估计加上后来也过 4 题的我们在大概 20 的样子, 银牌是一定的了. 这时分析了一下场上局势, 我们的 B 依然没想法, Moon 写的 E 最后说是数据有写反一列, 不过太迟了也调不出来, 我站起来看过的最多的也只是 J 了. 很快看完那个一直没人看完的 J 题的输入输出后觉得像是一个差分约束系统, 跟 Moon 和 Tank 说了后觉得也有理, 一起看完题我就在听讨论了, 因为知识面的问题, 图论我几乎为 0. 不过 J 还是有很多细节问题, 即使时间不多也还是要仔细讨论, 等 Moon 上去敲代码的时候 Tank 和我都在两边看着, 给 Moon 信心, 同时也注意看程序中的书写问题, 到最后的时候已经是无法在比赛终止之前写完了, 并且 Moon 和 Tank 发现做法中存在的问题而停了下来. 我坐在一边不停的在纸上随便乱写, 脑中想的只是还有不到 10 分钟我们就要退役了, 我们的第二场比赛也是告别赛就要这么完了. 最后还是没能发生奇迹, J 有太多的细节问题需要处理的, 最后还剩下不到一分钟的时候站起来看了看四周, 后面的 H-E-A-T 也过了 4 题, 并且罚时应该要比我们少, 和平时的练习差不多. 比赛完了马上就是颁奖, 等了很久, 等的非常急. Silence 是 3 题, 不过他们的罚时太多了, 估计也只能是铜牌了. 我们 4 题, 从我们最后看到的封 Board 的情况来看大概是 20 左右吧, 银牌是跑不掉的, 并且从最后场上气球情况来看, 金牌应该还是要 5 题或者还要求速度快的. 最后 wmzhou 宣布结果的时候从后面往前面念, 每念过去一个我们就要兴奋一把, 说明我们的名次会更靠前, 不过最后还是没能有不现实的事情发生, 我们 16, 这还是前面有带 * 参赛不参与排名队伍情况下的. 我们还是没能突破我心里一直期盼的那个槛, 没能在这个赛季拿到一块金牌或者是进 Final. 不过从学校的角度来看, 我们已经在书写历史了, 虽然 Silence 在我们前面过的三题, 但是我们是第一个在正赛中过 4 题的队伍, 并且是 03 北京 Nova 后的第二块银牌, 这块银牌拿的更加吃力. Moonmist 也将会是武大 ACM/ICPC 历史上的重要一页, 我们也是历史上最好的队伍之一. 只是, 我们没能像四年前的 Nova 一样能延续下来, 不能不说是一个遗憾. 同时, 我们也衷心的希望能尽快有后来的人继续超越我们, 往更高的目标冲刺, 而不是让我们成为一个和四年前那个两题/银牌的魔咒一样. 祝福 Moonmist 的三个人, We are the Moonmist, We are the future~. 祝福 Moon, 希望读研的日子里能变得更强, 有空的时候也过来带带 WHUACM 后面的小朋友们吧, 祝福 Tank, 希望明年你能如愿到达北方, 到你想到的地方, 和你想在一起的人在一起, 祝福自己, 希望明年此时我已经能拿到一个比较好的 Offer 去实习工作了吧, 并且最好不要丢集训队的脸, 能有一个比底线更好的 Offer. 对我而言, 保研已经是几乎不可能的事情了, 为了前途, 我需要更多的实践来让自己在找工作的时候有更好的竞争力. 所以, Snoopy 这个 id 在 ACM/ICPC 中应该也是要归隐了吧, 或者是永别. 从高一开始玩 NOIp, 到现在, 也快 6 年了吧, 可惜自己几乎是一事无成, 在大牛遍地的 OI 界和 ACM/ICPC 界, 不过是一个匆匆过客. 对 WHUACM 的一腔热血, 那么多的规划, 应该也是永远无法实现了吧, 不过希望能快点把自己一些希望能实现的东西留给后面的人吧, 毕竟我们走了太多弯路, 希望后面的人能更顺利的在更需要耗费精力的地方努力. 对 Snoopy, ACM/ICPC 已经剧终, 青春散场, 留下一地狼藉. 刚刚 MasT 还说我其实也创造了一个记录, 除了是目前武大 ACM/ICPC 队内呆的最久(虽然不是参赛最多)的一个外, 也是Honorable Mention 拿的最多的, sigh~, 希望这个记录不要有人去试图打破.