原文发在 BBS 上了, 其实这不是总结, 因为没有解决任何问题, 只能说是比赛记录吧
北京 2006, Moonmist.Snoopy 总结
这一篇, 只谈比赛.
清华的比赛环境赛前有说, 练习赛前一天晚上还问了 Gardon 复活赛的情况来决定
比赛的时候怎么做, 在国内看来是很奇怪的分配. 比赛分 4 个机房, 每个机房 15 支
队伍左右, Ranklist 是可以直接在本机刷出来的, 没有投影.
练习赛的时候发现的确是这样的, 我们在 2 机房, DeathDecay 在 3 机房, 清华
在练习赛的时候依然没发笔和草稿纸, 还好我们自己有带, 不过问了 volunteer 确认
第二天正式比赛的时候有有放心了. 不过系统不是赛前说的 Fedora Core 4, 而是 1,
不过没影响, 我们要用的都够了.
Nov.11th 练习赛.
题目:
A. KMP 或者直接硬搞, 看是否一个字符串 s 里有分离包含单词组 w[1..n].
B. 一个经典题的变形, 问把一串 n 个数字(有正有负)分成 m 份, 使得和最大的
那份的和最小, 二分加奇妙的方法, 现在依然还没做出来似乎.
C. 公式题, n 个野人 m 个传教士, 最少要多少步能过河, 所有人都能划船, 船
最多能装 2 人.
练习赛看题顺序跟正式比赛一样, 看完 A 后我就去敲了, 数据很小, 但是想稳妥
一点, 就去找标程敲 KMP, 过了 Sample, 交后 WA 了. 然后是 tank 上去写 B, 他理解
的就是全部是正数的经典问题了, 想二分贪心, 写到一半觉得有问题就放了. Moon 把 C
的公式推出来, 写了还是 WA.
这个时候 Moon 帮我看 A, 我和 tank 一起在推 C, Moon 发现 KMP 有问题, 改了
后交还是 WA. 我和 tank 找到 Moon 公式的特例有不符合的地方, 讨论过后把 Moon 的
程序修正了一下就过了. Moon 发现我程序一个小 bug, 改了后也过了. 其实那个问题是
一开始就有想到的, 后来因为 KMP 有问题又改错了.
刷了一下 Rank, 我们在 1x 的样子吧, 这个时候 Moon 和 tank 写 B, 我在按计划
测 Judge, 像 gets() 什么的还有特殊情况导致 PE/WA 的情况, 有些直接就在 PC^2 上
问 Judge 了, 裁判都很好, 非常友善的回答了问题, 基本上我们担心可能会有问题的
地方都测过或者问过了.
最后还是没能过 B, 并且全场也只是最后几分钟的时候 PKU_RPWT 过了这个, 还剩
5 分钟左右的时候我跑去 RPWT 那边问怎么做, styc 把我推给 ACRush, 一群人围着听
完, 知道了大致思路, 前面部分说的很清楚, 不过似乎最关键的部分大家都没问清楚,
也没说如果在二分后判断上下界.
练习赛发挥还算正常, KMP 的标程有问题不是很应该, 并且我错的那一次也是可以
避免的, 还是心态和细心程度不够. 同时发现一个有点郁闷的情况, 那就是清华机房里
暖气开的特别足, 让人很晕, 甚至 DeathDecay 那个机房还开空调降温了, 当时就在开
玩笑说是不是明天带一条毛巾过来随时准备洗脸清醒.
Nov.12th 正赛
题目:
A. 贪心. 机器人响应命令, 合理安排命令顺序使得能有最多的响应.
B. 求平面图的最小割, 赛后点评说可以转换为求最短路径.
C. Manhattan 距离最小生成树, 题目中有给出一个很关键的 Hint, 赛后点评说要
用高级数据结构.
D. 计算几何. 问是否能在一定范围内找到一条折线连接两个方块的中心.
E. 简单题, 贪心.
F. 安排合适的指令操作特定计算机使结果是某个特殊排列, 有规律然后贪心.
G. 图论, 我没看题, 比赛中最难的那个题.
H. 搜索, 要求在一根直尺上使用最小数目的刻度来量出要求的 n 个长度, 刻度数
不超过 7(包括0), n<=50(可以证明去重后n<=21), 赛后问过了的队都说是暴力
通过的.
I. 博弈, 赛后点评说用 Nim 算法, 我推了一个递推关系, 不过不知道到底是我推
的关系错了还是只是输出的地方有问题.
比赛当天正点起床, 然后叫醒其他所有人, 按计划准时往比赛地出发, 在东主楼前
拍了很多集体的照片. 进去门口等入场, 清华说因为机器配置的问题推迟了 10 分钟
开始比赛.
进去后跟前一天 Volunteer 说的一样有发笔, 不过没草稿纸, 还好我们带练习赛
打印的一些了. 大家没 BT 到真的拿毛巾过来, Moonmist 的计划是 “保银争金”, 当时
预计是过 3 题就能稳拿银牌的.
宣布比赛开始后我开的试卷袋, 然后开始看题, 跟平时一样, 我 ABC, tank DEF,
Moon GHI. 题目都不长, 我看完 A 后觉得是个不难的贪心, 立马跟 moon 和 tank 说
了意思, 但是大家都想更稳妥一些, 并且觉得应该有更简单的题, 然后继续. 我看完
BC 后说题目意思, 然后 moon 说了 I 博弈的意思, 不过我没完全听明白, 至少是有
细节没说明白, moon 说了一下 H 的意思, 觉得是个经典题, 我想了一下搜, 不过觉得
数据规模太大, tank 说 E 是个简单题, 不过我没完全听明白他意思, 于是 tank 跟
moon 讨论了一下决定 tank 上去敲, 我继续看 tank 没看的 DF 的题意. moon 看完了
G 我也看完了 DF, 交流了一下题目意思后我觉得 I 那个博弈是可以写的, 就开始推.
tank 写完 E 后提交 WA, 打印出来看, 我上去写 I, 用一个很简单的结论, 交上去也
WA 了. 这时全场有不少队过了 E, 并且有人在试 HI, 不过都没过. 一起帮忙 tank 看
了一下 E, 觉得可能会是精度问题, 乱七八糟修正了一下提交就过了, 这个时候是大概
15 名左右吧. 觉得我们能可以出至少 3 题的, 这个时候我继续想了一下 I 无果, 转
去写 A 了, tank 去看我的 I.
moon 想了很久的 G 跟 H, 然后重新去看 D, 因为我们队只有 moon 一个人经常做
计算几何, 我的 A 敲完后提交 WA 了. 这个时候看 Ranklist, 有队过 I 了, 并且有
很多队过 H, 我的 A 打印出来后看了看没问题, moon 觉得 A 能出, 看我代码太长就
索性重新写了一遍. 我想了很久的 H, 推了个时间和空间都很复杂的算法, 不敢写, 跟
moon 说但是他说出不来, tank 说不会搜索也没参与讨论, tank 看我的 I 然后给了个
想法, 我觉得有道理, 就去重写 I. moon 的 A 交上去也还是 WA 了, 回头看 H 似乎
依然觉得没法做, 又埋头改 A. tank 闲着, 我们说赌一下 B, 用最大流的算法去求要
的最小割, 我的 I 改了后非常慢, 不过自信是对的, 于是想修正一下 BFS 来降时间.
tank 慢慢敲完 B 后提交超时了, 索性完全放弃了 B. 这个时候午餐过来, 我和
tank 都在吃东西想问题, moon 在改 A, 看的出来似乎是有些急躁了, moon 让我们快
点, 自己也在到处看 A.
吃饭的时候看了看时间, 还剩下一个半小时的样子, 而我们开的题似乎是太多了,
我跟 moon 提议说我们要不要重新考虑一下策略, 因为看 Ranklist 上 A 依然没一个
人过, 而 H 过了很多, B 和 I 都只有很少的队伍过. 我个人的倾向是全队合力暴力
搜 H, 但是 tank 以不会搜索为理由不参与讨论, 而 moon 觉得我的算法是绝对会超
并且不能实现的, 就在写 A, 我对 H 的信心也不是很足于是在继续看 I 的特殊情况.
最后的时间我把 I 的搜索顺序改了一下使得答案能瞬出, 交上去后是 WA, tank
手里没题跟我一起看 I, moon 依然在写 A. 封 Board 的时候我们是铜牌第一第二的
样子吧, 并且刚封 Board 我们旁边的国防科大就过了第二题, 当时觉得只要能出一
题我们就是铁定银牌了, 因为第一题过的还不是很慢. 当时我的想法是全队合力做出
H 来就好了, 因为 A 我和 moon 的思路都很简单, 没任何特殊情况, 没道理所有人
都做不出来的, 而 I 那种博弈是很靠运气的.
最后 20 分钟左右我改了一下 I 的一个判断条件, 交上去返回了 Output Fomart
Error. 大家都很兴奋, 让我在机器前改一切能改的, 同时在 PC^2 上问裁判有没有
题目描叙不清楚的问题. 改了很多都是 OFE, 裁判回答也是完全按题意, 我们的输出
跟标准输出不一样. 最后几次在 WA 和 OFE 之间徘徊, 到最后一次提交依然没过, 而
比赛终止的命令却已经到达.
忘记了我们是怎么出去的, 只记得出去后 KO 很面无表情的说还好啦, 收拾一下
按组委会安排去照相吧. 最后那张几百人的照片上, 估计我们是笑得最难看的.
赛后想了想我们的很多问题, 其实很多问题都是在练习赛的时候就留下的隐患.
比如我们不适合做我们不领先的比赛, 因为在学校里做比赛一直都是我们领跑, 什么
题能做什么题不能做几乎都是我们决定的, 而在北京的时候我们对 Ranklist 上那么
多人过 H, 并且没人过 A 没能及时调整策略. 比如平时很多时候都是两个人在讨论,
因为我们有足够的题都可以同时写, 剩下的人都是在准备过题的. 但是很遗憾, 我们
都没有及时调整.
赛后一直到现在, 我都在想为什么北京那么好的形势我们都做的这么差, 我一直
想等 Moonmist 能聚在一起坦诚的说明白我们有什么问题, 相互之间有什么猜忌, 要
如何解决. 但是一直没有这样的机会, 我也不想什么都没弄清楚就随便说, 还是希望
能在大家达成共识后说吧.
有一些问题是绝对要讨论的:
1. 我们为什么不做 H?
2. 我们在 H 的认识上有多少差距, 赛后我跟 moon 讨论才发现原来我跟他说 H
我的想法的时候他根本不知道我在说什么意思, 而我却以为他明白了我的想法
只是说不能实现.
3. 在比赛形势如此明朗的情况下还在对 A 进行无谓的乱猜?
4. 比赛还剩下一个半小时的时候我们为什么不及时调整策略?
问题的解答晚上回来再说吧, 我不想在队内都没达成共识的情况下说我们有什么
问题, 然后这些问题需要如何解决.
我在自己的日记里写到: 回来的火车上我看相机里拍的照片, 看见最后一张是定格
在我们才过 1 题时的 Ranklist 上, 难过填满心的每一个缝隙.
现在, 依然难过, 但是希望我们能在找到问题后找好解决问题的方法, 上海回来后
我们能昂头挺胸凯旋而归.