Pick's Theorem

今天做到某题(POJ 2954),题意是求一个顶点坐标均为整数的三角型内整数点的个数,不含三角型边上的整数点。

Pick's Theorem,大意是:任何平面上顶点坐标均为整数的简单多边形,满足以下公式:

A = I + B / 2 - 1

A是多边形的面积,I是多边形内的整数点的个数,B是多边形边上整数点的个数。

Pick's Theorem可以推广到多维的情况,见:Ehrhart polynomials

理论和题目配合得相当完美……汗啊……

TopCoder Marathon Match 4

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

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

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

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

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

8/14 ZOJ 比赛小结

12:50 到场,和xhz讨论了一下策略,这次比赛只有3小时,预计题量在6道左右,而且名称为“Kill in Seconds”,想必难度不大,于是约定我从头、xhz从尾开始看,先看内容短的,看到简单题就丢给我做。

比赛开始后,xhz很快发现1007非常简单,他叙述了一下题意之后,我立刻开始敲代码,由于容器选择不合理,浪费了一点时间,在13分钟时1Y。然后xhz和我说了一下1008的题意,讨论下来觉得题意不明确,暂时放着。然后看到1003很短,看了一下题目,最优解问题,数据规模10000,肯定是贪心,很快讨论出了算法,可惜第一次少打了个“=”,贡献了一次WA,32分钟时2Y。过这题的时候,xhz已经看完N道了,只能用一台机器真是不爽T_T。接下去很快又过了1004,49分钟时1Y。

接下去开始敲1005,由于牵涉到对称,即除2和+1 -1的问题,我就头大了,代码调了蛮长时间才过sample,但是交了几次都是WA,没想通哪里错了,然后让xhz开始写1001,一道模拟题,除了坐标设定要仔细看之外,没什么难点。后来我把1005中判断的代码重写,糊里糊涂得就过了,2小时4分钟6Y。然后xhz继续写1001,由于重名变量问题一直没过sample,调了很久才发现,然后1Y。这时候已经是2小时37分了,剩下1002:题意不明确,当时还没有人过;1006:一道算法很简单,输入很复杂的题,20分钟内肯定写不完;1008,暂时没搞清算法。于是最后20分钟成为垃圾时间……

这次比赛前期发挥还算正常,只是出1005的速度太慢了,后来回忆时想到是if后面少加{}了,导致浪费了半个多小时,要不然可能可以写完1006。最终排名是36,还算满意。