Category Archives: ACM

ZOJ Problem Set – 3020 – Puzzle Quest

不知道多少人玩过 Puzzle Quest 这个游戏。这是个有日式画风,用宝石方块的对战方式来进行的RPG。一般的游戏模式需要进行消去,同时使用得到的宝石攻击对手。而怪物捕捉模式需要玩家将一块特定布局的棋盘上的宝石全部消去(GameFAQs 上有所有谜题的解答)。 ZOJ 3020 就是要求程序自动解这类的消去全部宝石的谜题(除去了爆炸骷髅这种宝石)。 最简单的解法当然就是深度优先搜索。流程代码还是比较简单的,就是检查每一种可能的操作和计算操作的结果,如果结果通过剪枝的话就迭代继续搜索。初步的剪枝算法也很简单,只要棋局中出现只有单个或两个的同种类宝石,就已经无解了。 深度优先搜索在比较简单的谜题上是没问题的,但是对一些复杂的谜题(一些需要10步以上操作的)就非常慢了。当一个谜题跑了10分钟还没结果的时候我放弃了,光靠优化算法的效率和使用更有效的复杂剪枝算法看来已经没法控制时间复杂度了。(之后看到别人给的代码,在深度搜索中加入了 hash表 作为棋局的缓存(类似动态规划了),能在3秒左右完成ZOJ的测试数据,但是在我的数据上仍然跑了1分钟多。) 于是对算法作了改动,改用启发式的最优最先搜索,由当前优先级最高的棋局继续搜索。这需要一个额外的判断棋局优先级的启发式算法(“看起来更有希望”的棋局有更高的优先级)。调查了几个花时间最长的谜题,加入两个条件,一个是棋局中剩余的宝石种类越少优先级越高(一是种类少一般剩余的宝石数量也少,另外也更方便接下去的消去操作),另一个是孤立的宝石距其它能凑成3个的宝石越远优先级越低(宝石分开的远的话很有可能在接下来的操作中没法把这些宝石凑在一起消除,鼓励程序优先消去这样的孤立宝石)。这样使程序的时间复杂度有了戏剧性的提高,能在1秒内跑完我全部的测试数据。 最后的成果是ZOJ上300毫秒的运行时间,之前ZOJ记录中最快的也需要2秒。 C++ 代码: 这类用程序自动解益智游戏的题还是相当有趣的。 Advertisements

Posted in ACM, Science | Tagged , | Leave a comment

DOMjudge结构简介

最近在公司里架了个 DOMjudge。简单介绍下它的结构吧。 DOMjudge 是一个自动化的编程竞赛的判定系统,由一个 DOMjudge server 和复数个 Judgehost 构成。 DOMjudge server 给用户、评委、管理员提供网页界面。它是一个典型的 LAMP 网络应用的架构,运行于 Linux 操作系统,Apache 提供网页服务,PHP 作为 CGI 脚本,MySQL 存储数据。用户界面主要显示队伍、排名、文件提交和提交状态;评委界面是管理员界面的子集,主要用来查看队伍的答题情况,可以显示提交的源代码、测试例的输出比较等,以便评委和进行验证。管理员界面用来管理竞赛、队伍、题目等配置,大多数的配置也可以通过直接编辑 domjudge 数据库中的 configure 表进行。 Judgehost 负责编译和运行队伍提交的源代码,给出判定结果。鉴于性能考虑,Judgehost 可以有复数台,且一般不和 DOMjudge server 运行于同一台服务器。它通过守护进程连接 DOMjudge server,通过轮询的方式检查 server 是否有需要判定的代码,如有,则编译运行代码,并做出判定。有趣的是,除了编译运行的部分,Judgehost 的结构和 server 的结构非常相似。守护进程仅仅是一个 PHP 脚本,而每次轮询贯彻了 … Continue reading

Posted in ACM, Computer and Internet, Operation System and Linux | Tagged , , | Leave a comment

ZOJ Problem Set – 2629 – Cover More Circles

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2629 又抽中一道要做两次变换的题。 化简后的题目差不多就是:用一个给定半径的圆去覆盖平面上的点集合,最多能覆盖多少点。 第一次变换比较明显。把大圆覆盖小圆的问题变换为圆的相交问题。这样问题就转化为找平面上被圆覆盖次数最多的点。 第二次变换有点微妙。一方面,虽然判断一个点被多少个圆覆盖非常简单,但在实数平面上的搜索还是不太现实的。另一方面,直接判断数个圆是否有公共交却相当复杂,即使只是3个圆的公共交。最终路线还是第一条(我在第二条上费时无数),但不是考虑平面上的任意点,而是考虑圆上的弧(一些情况下会收缩到点)。可以看到,能在平面的点上达到的最大覆盖数,同样也能在某一个圆上的弧上达到。于是算法的实现就是把圆上的弧按照该圆和其它圆的交点进行分割,然后找到被覆盖次数最大的那段。再在所有圆上取该值的最大便是结果了。

Posted in ACM, Science | Leave a comment

ZOJ Problem Set – 3265 – Strange Game

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3265 这道题相当不错,把图论问题伪装成数论了。 首先要看出来,其实这只是二分图的匹配问题。左边是ticket,右边是prize,那个公式只是用来连线的。那么自然而然想到的解法就是 最大流最小割 的 增广路算法 了。 其次,虽然题目的时间/空间复杂度并不如看上去的那么高,但显然直接把整个图构造出来也是不现实的。需要一边计算增广路,一边构造需要的那部分图。于是表现图的数据结构也和一般的稍有不同。 最后当然就是代码实现了。 前面都简单 & 顺利。然后我就在 增广路算法 那儿悲剧了。虽然知道一般用的是广度搜索(Edmonds-Karp 算法),不过为了偷懒还是上递归用深度搜索。然后无数时间没写过图的搜索算法的恶果显现。 第一次尝试,直接用了树的,然后循环了,递归堆栈跑穿直接 Segmentation Fault。修完这个,再上,然后因为没做剪枝(说白了,就是顶点着色没实现全)于是又 Time Limit Exceeded。最后加上完整的顶点着色的代码后终于 Accepted 的时候已经两个小时过去了。。。sigh

Posted in ACM, Science | Leave a comment