显然我还没有领悟marathon的真谛。
第一轮的题目大意是，有一座山，可以表示在101*101的方阵中，每一个方格要么为空，要么为山体。选手可在任意为空的两点作一次测量（从一点发射一束光到另一点），系统返回接收到的光束的强度。由于打穿了山体，所以光强有衰减。又由于测量仪器的问题，测出的值带有随机误差。经过有限次测量后，选手需返回第一小块山体中所含重金属的密度（这种重金属就是导致光线衰减的原因）。
根据题意简化之后，实际上就是求解一个方程组，其中每个方程形如：
网上查了一下，这种类型的方程叫做非线性方程，貌似还没有通用解法。我的解法是对于左边只有一项的方程，直接求出解，然后把解出的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就止步于第三轮了……
您还可能感兴趣的日志：