2010 ACM Harbin Regional Contest总结

张文泰 posted @ 2010年10月05日 06:26 in Art of Science with tags acm , 3224 阅读

热身赛前一天晚上我和李晔晨在房间里面写Java的BigInteger类,以防第二天出现这种类型的题目。但是李晔晨写了一个程序一直RE,我不是很清楚其中的原因,然后看看已经1:30了,就直接睡觉了。

热身赛没什么特别的,我们做了基本上所有的试验,然后没有什么问题。唯一比较好玩的是清华的三个队伍座位都在我们前面,PKU的另外两个队伍也是如此,这样我们比赛的时候观察形势就容易了一点,不过第二天的比赛中长时间的卡题证明了这个座位几乎没起到什么作用。

正式比赛的那一天我感觉有点疲倦,可能是和我的生物钟不太一致,所以现场的状态一直不是很好。以后考虑是不是比赛的时候带点能够提神的东西。开始之后,我一如既往地先去找容易题给肖刘秒杀。结果反而是李晔晨先找到了一个F题AC了,这个时候我已经读题到E,就告诉肖刘ABE可做之后接着去看GHIJ。肖刘先想出了A,就先写了A。这时候脑残的事情发生了,我和李晔晨讨论之后发现B是一个“最大权匹配”,于是李晔晨上去拍了一个网络流的模板,TLE了。我们分析之后认为需要KM算法,但是由于A没写完,就暂时去想题了,期间我告诉李晔晨H的做法,李晔晨表示可以直接模板秒杀,然后就去研究GIJ。J被认为是可以做的,李晔晨就去推导I,我在帮肖刘调试A。A经过一系列的Debug之后终于AC了,然后李晔晨AC了H,继续去想I。关于I,李晔晨曾经有过心理阴影,所以没有选择积分,而是选择了一个近似算法。李晔晨认为I已经可以做了,就直接去想G。我由于把I这种数学题完全交给了李晔晨,结果没有去验证他的想法,这导致了我们在最后2个小时非常被动。

接下来,我们在经过一番讨论之后终于发现了B是一个弱智题目,被我秒杀。于是全场还有CDGIJ没做。我们对于GIJ都有想法,于是决定先写这三个题目。由于J比较稳,而我由于没有肖刘那么擅长写这种递推的程序,所以就交给了肖刘写,果然不负众望的AC了。然后写I,TLE之,当时我还没有感觉出来有什么问题,其实这个算法注定是错误的,关键在于精度不够。然后又写了G,由于这两个题目都是李晔晨负责的,所以在最后的一个半小时之内比赛变得非常混乱。虽然最后李晔晨不负众望过了I,肖刘也极尽所能的AC了G,但是我们这一阶段的安排确实很有问题。

9 北京大学 弓箭手 8 1664 金奖

我们队最后是8个题,但是由于G和I交了很多次,罚时较多,只有第9名。赛后得知C是模板题,被赖陆航他们恶搞过了,D是一个DLX,但是很难写。 我们这次比赛最大的失误在于题目分配不均衡,主要过错在于我没有能够完全发挥自身的能力。AEJ是肖刘写的,FGHI是李晔晨写的,我仅仅只写了一个很简单的B。在今后的比赛中,我们应该加强中间一段时间题目分配的均衡程度,确保不会有一个人做多个题的情况。前期还是可以让肖刘主写简单题,我看题,而且一开始就可以分配一些难题给李晔晨,这样可以防止后期乏力的问题。如果可以继续加强磨合,相信我们这支目前还算是比较稚嫩的队伍可以在今后的比赛中取得更好的成绩。


本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License
Answeror 说:
2011年3月12日 23:28

请问一下G具体是用什么方法呢?
现在已知的有Bellman-Ford(或者说SPFA)不到n轮提前跳出, 这是一个概率性的解法.
另一个办法是用所谓的深搜式的SPFA(就是一边DFS一边更新d数组, 遇到祖先d比自己大就说明找到环), 但是这样在最坏情况下复杂度是指数级的.
有没有一种非概率的, 最坏情况下复杂度多项式级的办法呢?

Avatar_small
张文泰 说:
2011年4月17日 18:58

@Answeror: 实际上G这个题目好像就是分析出何时跳出可以保证最优,具体的我也记不清了


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter