Topcoder Open 2007 Marathon Round 1 to 3

显然我还没有领悟marathon的真谛。

第一轮的题目大意是,有一座山,可以表示在101*101的方阵中,每一个方格要么为空,要么为山体。选手可在任意为空的两点作一次测量(从一点发射一束光到另一点),系统返回接收到的光束的强度。由于打穿了山体,所以光强有衰减。又由于测量仪器的问题,测出的值带有随机误差。经过有限次测量后,选手需返回第一小块山体中所含重金属的密度(这种重金属就是导致光线衰减的原因)。

根据题意简化之后,实际上就是求解一个方程组,其中每个方程形如:

其中,ki为山体编号的非空子集,X为所求密度,ai为光束穿过该山体的路径长度,b为测量所得的值。

网上查了一下,这种类型的方程叫做非线性方程,貌似还没有通用解法。我的解法是对于左边只有一项的方程,直接求出解,然后把解出的X代入方程组消元,再找左边只有一项的方程,以此类推,解到无法继续为止。但是后来发现,由于b是不精确的,所以迭代的次数越多,解出的值反而越不精确。由于是第一轮,参加人数少,晋级名额多,所以迭代一层的分数,已经足以晋级了,就没有详细研究下去。

第二轮的题目叫“TwoCardDraw”,牌类游戏,貌似是"FiveCardDraw"的简化版。大致规则是选手和系统双人游戏,一轮分为三个环节。上手各拿到2张牌,并各下1注做为底注,在第一环节中选手和系统都可以raise(加注)、check(跟注)和fold(放弃),raise不能超过三次,达到三次必须check或fold;若在第一环节没有人fold,则进入第二环节,在第二环节中,选手和系统可以换牌,换0、1、2张牌都可以,然后进入第三环节;第三环节的规则和第一环节一样。第三环节结束后,就各自亮牌比大小。对子>散牌,同为对子则比牌的大小,一样则平局,注码平分;同为散牌则看最大牌的大小,若一样则看次大牌的大小,再一样就平局,注码平分。非平局胜者赢取所有注码。在第一第三环节时,每次raise的注码为定值,bet1和bet2,游戏开始前就约定了。选手一开始有10000注,系统有无限注=.=,进行10000轮游戏,然后计算得分。

我对牌类游戏一直不擅长,看了一下sample的系统设定,发现是基于枚举变量的随机变法,即当XXXX情况时,有A%的机率raise,B%的机率check,C%的机率fold。然后我就模仿这种做法,并且扩展了枚举,然后得到了近300个变量,寒=.=,维护这么多变量真是件不容易的事。试了很多策略都不尽如人意,最后排在191名,有惊无险得出线。

比赛结束之后看了前10名的代码,发现他们大部分都是用我的方法做的,只是变量更多,多到需要进行编码压缩的地步了=.=

第三轮的题目与第一轮类似,讲的是一个养护工人要维护一片n*m的树林,树木种在方格内,人可以在方格线上走,并且可以在交点处观察。每次只能观察东南西北四个方向,于是可以得到左右两排树的信息,最近的两棵树一定是精确的,要么有虫害,要么没有。越远的树越可能有误差(有虫害的看成没有,没有的看成有)。每次观察,最近的两棵树,如果有虫害,就会被自动标记上。最终得分和被标记的数量有密切关系。但是由于时间有限,养护工人不得不在天黑之前回家(X-File?),而走路和观察都消耗时间,所以策略很重要。

基于第二轮结束得到的经验,这一轮我写了个自动测试工具,并且生成了100组数据,这样就可以对新的策略进行实时的评测了。但是策略都不太理想,一、最容易想到的是对每一棵树打分,分数最高的就是最有可能有虫害的。二、根据题目中地图的生成规则,有虫害的树比较集中,于是打分的时候,有虫害的树对周围的树有加权。三、在小范围区域尝试几次都命中后,直接跳转到其它区域。四、若分数最高的树离自己比较远,就一点一点移过去,而不是一下子过去,防止工人在两块区域之前走来走去。五、在标记一棵树的时候,先对两个方向(一个棵可以从两个方向被标记)做评测,然后观察能获得更多数据的方向。主要就是这些策略,不过得分最高一次只有26分,最终晋级需要30分,太郁闷了=.=

于是TCO07 Marathon就止步于第三轮了……

Topcoder / CSDN Competition

这比赛还真恶心。第一题可以用3个for解决,第二题用1个while+2 个for解决。前两题瞬间搞定了,一看时间才过了15分钟。然后打开第三题,看了5分钟,愣是没看懂题意。结合sample看了很久才大致看明白。这种情况还是ICPC好,可以直接问Judge,Topcoder上只好猜了。假设了N个条件后,总算写完了,过了所有sample就交了,也懒得查,题意越看越模糊。

悠闲地等了30分钟,期间看到2个红色名字的人重新交了第一题和第三题,于是仔细想前两题可能的陷阱,未果,重新看了一下代码,没啥写错的地方,也就没改。Challenge的时候不知道网络出啥问题,fetch problem总是超时,只cha掉一份代码,赚了50分。与此同时我的第三题被cha掉,排名从第三跌到2X,前三是没希望了。

等Sys Test的时候在祈祷,排在我前面的人都错2题=.=,结果Sys Test结束,第三题没人过,瞬间排名升到第5,奇迹出现了=.=。不过这么简单的第三题没人过实在说不过去,Judge肯定有问题。后来rejudge了,我的排名最终定在了11名,主要归功于我的打字速度=.=。后来看了zhuzeyuan的代码,才发现我第三题错在哪里,不过题目也没明说,每个人理解不一样罢了。

然后就等T-shirt寄来了,btw,我的T-shirt多得快装不下了,下次能不能送点别的=.=

TopCoder Marathon Match 4

题目改编自己经典游戏Battleship,原版的游戏是给出一个n*m的方格阵,里面有k条船,每条船的宽度都是1但长度不一,方向要么横着(纵坐标相同)要么竖着(横坐标相同),玩家每回合选择一个点丢炸弹,系统返回炸到与否。这道题目改了一些条件:给出一个n*n的方格阵,每次可以丢x个炸弹,系统返回炸到了哪些船和每条船炸到几个点,但不告之是哪些炸弹炸到的。要求程序在尽可能短的回合内,炸完所有的船。

看到题目,最初的想法是完全随机投点,这样做的好处是:1、使自己有个分数先,0分太难看了;2、这个算法保证能在规定时间内结束,可以用来测试程序的完整性和对题目理解的正确性。迅速写完之后提交,出乎意料拿了30多分(满分100),看来完全随机的效率还不错。

然后开始改进程序,虽然系统不返回哪个炸弹炸到了船,但是只要有船被炸到,那一回合的炸弹附近必然有船,下一回合就先炸那附近的点。这么一改,得分反而下降了,郁闷=.=,分析原因,可能是下一回合选取点的优先顺序问题,因为有多种情况可以估算可能有船的点,不同的if顺序就会导致程序效率的明显差别,于是继续改。

再然后就想到了给每个点都设一个可能度的值,每一轮炸完之后,都对相应的点的可能度进行评估,然后选出可能度最高的几个点进入下一轮。评估的条件有,如果一个点炸到了船,则它周围的四个点可能度提升;如果两个点炸到了船并且它们在一条直线上距离小于那条船的长度,则它们所在直线上相应点的可能度提升;如果一个点没有炸到船,则它周围点的可能度下降(这一条有争议,多次试验下来效果不好)。这样一改,分数一下子上到了50多分,效果非常好。

但是最高分有90多分,怎样继续优化是一个问题。这时我的程序已经分为2部分,一部分是初始化时,点的顺序,因为最初的几回合,可以获得的信息比较少,但这几回合非常关键,怎么安排最初炸的点是要好好考虑的;另一部分是怎样利用已知信息,计算点的可能度。这2部分的优化都很伤脑筋,而我的分数一直在50分左右徘徊,很郁闷。