荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: kaman (假如时间可以倒流....), 信区: ACMICPC
标  题: [zz]lrj的西安总结
发信站: 荔园晨风BBS站 (Fri Dec 22 15:05:24 2006), 站内

http://xiaonei.com/GetEntry.do?id=201302411
这段时间的连续奋战,昨天晚上算是告一段落了。很感谢这段时间以来帮助和关心我的所有
人。虽然因此而没有顾及到的事情产生了一些后果还需要承担,但是大多数的辛苦没有白费




考虑到这里有一些参加比赛的朋友,我来说一下这次西安赛区的情况。



这次比赛的十个题目,前九题是我出的(所以题目名称的首字母就是题目编号)。数据和程
序方面,除了我之外还有两个外国人,都当过至少三年的finals裁判。命题工作没有其他中
国人参与,也就避免了一些麻烦事。

原来设想的是第一名7题,铜牌分数线2题。后一个目标达到了,而前一个目标还差一点:
ltc他们没敢去做H,而他们的C遇到小的速度区间时结果一般都是错的,而数据中恰好有两
个故意设置的exact velocity。另一个队差点做出了Gargoyle,可惜他们误以为最小流量对
应最小费用,稍微改改就能对了。



总的来说,这次的题目我设计得比较与众不同:虽然最简单的题目是E(最后有93支队伍通
过此题),但是半小时以后才有人发现这一点,在这之前已经有两支队伍通过了B。第40分
钟时,虽然第一名只有一道题目,但B,E,J都已经有队伍通过了,说明简单题的平衡性还是
不错的;事实上H也是一道简单题,但却需要选手十分细心。事实上,快2小时的时候才有人
通过H,而cici他们队虽然是并列冠军,但到了最后也没能通过H -- 题目中有三个细节容易
被忽略,他们只注意到两个。事实上,如果通过了BEHJ,只要罚时不太多的话,金牌是没有
问题的。这四道简单题目的数据已经被大大简化了,E只有两个数据,H只有5个(而且不包
含特殊情况),J只有二十个(原来是12000个)。B也只有20个(原来是40个)。这四题的
tiemlimit都是标程runtime的50倍以上,结果最后还有至少5支队踩着timelimit通过的B,
呵呵。B的timelimit主要是让mn^2算法或者带高精度的dp也可以通过(标程是不带高精度的
nm),毕竟本题的idea才是最主要的;J的timelimit是考虑到比较慢的预处理或者完全盲目
的search也有机会通过.



下面简单说说D。做D是需要勇气的,因为不管是先预处理出所有good puzzle还是直接搜,
运算量都是不容乐观的。我的实验结果是直接搜1秒左右,先预处理的话3秒左右,所以时限
定的30秒。这样子只要方法正确是不会因为常数项超时的。最后结果证明,做出D的队伍都
是基础比较好的,基本上都拿到了金牌(即使因为种种原因而没有过掉某些更简单的题。



其他题目就不说了,留给大家想一想吧 呵呵。这次我故意把大部分题目弄得不太常规,因
为我不鼓励题海战术,所以也不希望一个只是“见多识广”,做过很多题,而思维和创新能
力很一般的队伍获得太好的名次。毕竟比赛不是水平考试,变化是发展的必要条件。


--

     Science is what we understand well enough to explain to a computer.
     Art is everything else we do.

                                                 ———— Donald E. Knuth



※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.14.224]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店