Monthly Archives: May 2011

武装神姫2 OP

CG和歌曲的素质极高啊,索性动画化吧。 http://www.tudou.com/programs/view/EFiEPpyjIJQ/#

Posted in Entertainment, Game | 1 Comment

The Fall of Hyperion

算是 Hyperion 两卷的解谜篇了,把视角从上卷的 Hyperion 星球上的巡礼者切到了整个 Hegemony —— Hegemony 的覆灭,人类的惨胜。 量子级的可能性之神的概念还算有趣了。 不过 Shrike 就比较破灭了。上卷好不容易营造起来的恐怖神秘形象,随着剧情发展,最后发现它不过就是个工具罢了。只是建立在功利和理性层面上的恐怖的话这东西完全比不上无处不在而又能完美预测未来的 TechnoCore 的AI群了。 果然营造恐怖氛围还是克苏鲁神话中的那种无法理解的怪物才好啊。

Posted in Book, Entertainment | Leave a comment

WHITE ALBUM2 ~introductory chapter~

Visual novel。在硬盘上放了一年,最近才通掉。只是两部曲的前半,不过也是足够完整的故事了。 虽然说是 visual novel,但是全篇一个选项都没有还是有些出乎意料的。不过也因为单线的原因,游戏的完成度堪称完美,可以说没有一句话是多余的,没有一个场景可以错过。 画面的演出算是最近看过的此类游戏的最高峰了,点睛的雪花纷飞的场景,吉他和钢琴音乐的切入,以及高潮时 no-skip 部分的演出,气氛渲染极佳。残念的是CG数量太少了。 声优的演出也无可挑剔,生天目仁美 的 冬馬かずさ 尤其出色,言不由衷的细微之处,感情爆发时压抑着的激动,表现的淋漓尽致。 情节么,就不剧透了。用尾声时的那段话说,开始是三个人,后来两个人走到了一起,然后一个人离开了,最后留下来一个人、和一个人。 三人的个性和情感纠葛演绎的非常到位,相互间敏感的感情交织表现在每一个表情和语气中。而这些时而细微时而高涨的感情和互异却随着相互交往而稍稍改变着的个性和心意,作用在每个偶然和必然的事件上,顺理成章又出人意料的推动着故事的发展,直到最后令人扼腕但却无可避免的悲剧。 游戏时间大约8小时,推荐数天内分段完成,因为细节之处的回味同时需要记忆力与集中力。 继续期待年末的 closing chapter 吧。先转战同样是去年差不多时间发布的 素晴らしき日々 了。 顺便,为啥OST还不出啊啊啊!!!

Posted in Entertainment, Game | 1 Comment

算法信息论 与 Kolmogorov复杂度

Shannon信息论 是建立在概率论的基础上的。算法信息论 则更接近 Turning 的可计算理论。其复杂度的定义不是基于概率,而是算法。 不太正式的说,一段字符串的 Kolmogorov复杂度 是在某一描述语言下最短的能够描述这一字符串的程序的长度。这里的“某一描述语言”定义比较含糊,可以把图灵机看作代表,其它图灵完备的描述语言都与其等价。 两个例子: π 是无限长的无理数/超越数,但其 Kolmogorov复杂度 只是常数。简单的如 Gauss-Legendre算法 可以完全的描述 π。 一段随机生成的字符串的 Kolmogorov复杂度 是它的长度。我们所能想到的描述它的方式只是 print [string]。(在算法信息论,这才是随机字符串的定义。) 有时学科的深邃程度可以用其涉及的悖论来衡量。与 Kolmogorov复杂度 相关的是 Berry悖论:“最小的不能用20个以内的汉字描述的正整数”。其结果是 Kolmogorov复杂度的不可计算性和 Chaitin不完备定理。 Kolmogorov复杂度 是描述方面的一种复杂度的计量。在上面的两个例子看来,其解释是有点反直觉的。显然 π 要比什么意义都没有的随机字符串要“复杂”的多。如果从一个方面,即从计算复杂度的角度来看,π 的复杂度则要高的多,就是说,从其(压缩后的)描述/程序来重新构造它所需要的时间要比那个随机字符串长的多。这是 Charles Bennett 更一般性的 逻辑深度 的想法。 一个应用是 Ray Solomonoff … Continue reading

Posted in Science | Leave a comment

信息论在 ACM Online Judge 中的应用

可惜不是解题的作用,是信息论在获取用于 Online Judge 的 test data (只包括输入部分)的作用,如果你不介意这一过程中无数的 WA 和反复的提交的话。 从系统角度看,信源是 Online Judge 的 test data;信道是从提交程序的运行,到 Online Judge 的判断,最后判断结果通过网络到达本机的整个信息通道。 首先,看下一次提交能获得的信息量。从 Online Judge 的返回数据中,拥有最大信息量的是哪些呢?是 run time 和 run memory!前者一般可以提供大约 6bit 的信息量(10ms ~ 1s,10ms 的分辨率,可以通过空循环控制),而后者提供的信息量超过 20bit (数百kB ~ 32MB,4B 的分辨率,可以通过内存分配控制)。不过需要注意的是这两者都不是完全精确的。 接下来,看下作为信源的 test data … Continue reading

Posted in Science | 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