记08年北大ACM选拔赛

    早晨7:40的闹铃。到36楼下面见到了我的两个队友后,随便吃了点东西就出发了。
    计算中心门前特别热闹,N多人围在一张大桌子前,好像是在签到。我挤进去找了半天发现没我的名字,名单上全是信科的人。我抬头问,中文的在哪儿呢。一个美女姐姐用手指了远处的一个几乎没人的地方说“中文的在那边”,并说了一句“哇,中文的呀,太牛B了”。我顺着她手指的方向望过去,另一张小桌子前面贴了“中文”二字,桌子后面没有人,估计是交给了旁边负责数院和元培的人,让他们顺便管一下。从我目前所了解的情况来看,那张桌子应该是特别为我准备的,它在历史上很可能是第一次出现。

      
    第四题是做得最顺利的一道题。我把所有题粗略看了一遍后,首先决定就想这道题。题目描述巨简单,就是问你沿对角线把一个正n边形剖分成三角形和四边形有多少种方法。上图显示了n=5时所有的10种方法。熟悉组合数学的人都知道,三角形剖分方案对应的是Catalan数列,其递推公式的推导相当经典。设C(n)表示凸n+2边形的剖分方案数,枚举底边和哪一个点相连(下图左),容易看出C(n) = C(0)*C(n-1) + C(1)*C(n-2) + … + C(n-1)*C(0)。
    
    现在,如果剖分中允许有四边形的出现,又该怎么办呢?看看数据规模n≤5000,估计应该是叫我们寻找类似的递推公式。容易想到,我们可以枚举底边与哪一个点相连构成三角形,统计出底边属于某个三角形的剖分方案T(n)=ΣC(i)C(j), i+j=n-1;再枚举底边和哪两个点相连构成四边形,统计底边在一个四边形上的剖分数Q(n)=ΣC(i)C(j)C(k), i+j+k=n-2。但是,枚举四边形需要O(n^2)的时间,这样的话整个程序就是O(n^3)的了,n=5000绝对超时。那怎么办呢?两分钟后,我想到了一个具有决定意义的点子:计算Q(n)可以直接利用以前算过的T(i)。枚举四边形的两个顶点时,固定四边形的左边那个顶点,你会惊奇地发现右半部分的所有情况加起来正好就是一个T(i) (上图右)。因此,ΣC(i)T(n-i-1)就是我们所需要的Q(n)。
    一个有趣的细节是,这道题要求选手输出结果除以2^64的余数,不知道会不会有人想不到这个该怎么处理;事实上只需要直接用64位无符号类型来运算就可以了,超界了后计算机储存的本来就已经是2^64的余数了。


    Hanoi塔那道题也是一个有趣的数学问题。题目大意是说,如果允许Hanoi塔上有相同大小的盘子,最优解又是多少。输入数据给出盘子大小的种数和每种盘子的个数,叫你输出最优解的步数。我的第一想法就是,大小相同的盘子始终要在一起,移动时就排着队啪啪啪地挨个移动,总是保证大家一起行动。其实说穿了就相当于把大小相同的盘子当成一个整体,只是移动的时候有一个权值。这样,只需要考虑经典Hanoi塔中每个盘子需要移动几次就行了。但很快我们发现,这连样例都过不了。为什么就只有两个一样大的盘子时,输出会是3呢?再仔细看了一遍题目,发现麻烦了:一样大的盘子也是可以区别的,目标状态的盘子顺序必须与初始时一模一样。但我们很快发现,加上这个条件后对我们的原始想法影响并不大。在经典Hanoi塔中,第i大的盘子需要移动2^(i-1)次,除了最大的盘子只需要移动一次以外,其它盘子都要移动偶数次。而对大小相同的几个盘子整体转移一次后,盘子的次序正好完全颠倒,因此移动偶数次后次序不变。于是,我们只需要集中考虑最大的那种盘子该怎么处理。队友leimiaos做出了一个大胆的猜想,事实证明他是对的:把最底下那个盘子加大一号(最大的那种盘子就变成第二大的了,并且少了一个),这样就巧妙避开了多个最大号盘子的问题;这样做的结果显然是合法解,并且应该是最优的。

    第一题是所有题目中最科学的一道。给你一个有向图,给定它的起点和终点。每一条边都有且只有一段开放时间,其它时间里这条边是不允许通过的。给出每条边的开放起始时间、关闭时间和通过这条边所需要耗费的时间,问你从起点到终点最少需要多少时间。我和leimiaos同时想到,在这道题目中我们要尽可能早地到每一个点,可以用直接套用Dijkstra算法更新到每个点的最早时间。反正你早到了也不亏,如果接下来要走的边还没开放的话我等一下就是了。leimiaos很快写完了这道题,但连样例都过不了。仔细研究了一下样例,我们发现问题严重了:我们要求的不是到终点的最早时间,而是从起点到终点全程所需的最少时间。换句话说,我可以先在起点处等着不走,看着时机成熟后再出发,虽然到终点时间更晚,但路上花的时间更少。怎么办呢?枚举出发时间是一个好办法,但时间的范围很大,肯定会超时;二分出发时间?显然不行,这个问题不具有单调性(考虑从起点直接连到终点的多重边,且所有边的开放时间都不相交)。十分钟后,我一拍大腿说,至少存在一个最优解,使得整个路程在某条边上正好卡着时间进去或者卡着时间出来。如果整个路程中所有边上的实际通过时间都是“松”的,就把整个行程时间安排挪动一下,直到某条边上的通行时间正好碰到开放时段的端点。这样的话,我们只需要枚举整个行程时间卡在哪条边上,然后用刚才的算法顺着推出从这儿走完剩下的路到终点的最早时间,并且反着推出从这儿往回走能够得到的最晚出发时间。这道题太精彩了!!可惜后来时间不够,算法的代码没有完成,算法的正确性和效率也不得而知了。

    第二题是一道很难的数学题,很少有人做出来。因此我非常得意:) 说一个n阶的满Steiner树是指一个有2n-2个节点的无根树,其中n个叶子节点从1到n标号,另外n-2个节点(叫做Steiner顶点)连通了那n个点,并且每个Steiner节点的度都为3。你可以在这里看到n=3时的惟一一个满Steiner树,以及n=4时的所有三个满Steiner树。输入一个n(3≤n≤10^7),输出n阶的满Steiner树有多少个。要求用8.687E36这样的格式输出。
    随便把一个叶子节点砍掉,剩下的就是一棵正宗的二叉树,我们的问题实际上就变成了“有n-1个叶子节点的二叉树有多少个”,其中叶子节点带标号,并且二叉树不分左右。依据这个思路得到的递推公式就是( ΣC(n,i)F(i)F(n-i) )/2,那个C是组合数的意思,F(n)表示n阶满Steiner树的个数。但是n可能达到10^7,绝对不可能直接用我这个递推公式。我开始计算n=3, 4, 5, 6的情况,想看看有什么数学规律没。算出来的数是1, 3, 15, 105。然后牛B的事情就发生了,我眼睛突然一亮,发现它们间的比正好是3, 5, 7,也就是说F(n)=(2n-5)!!!(前两个叹号是双阶乘的意思,末一个感叹号是感叹号)。我立即写下一个程序,按这个公式计算F(30),发现它果然得出8.687E36,和样例一模一样!
    真正戏剧性的事情发生了:暴力计算双阶乘超时了。怎么办?注意到,(2n-1)!!=(2n)!/(2^n*n!)。leimiaos突然想到,在这个精度要求下完全可以用Stirling近似公式。我们可以让n到了一定大时利用Stirling近似公式直接输出结果。n的阶乘约等于根号下(2πn)乘以(n/e)^n,在比赛中我们发现这个公式的精确程度令人瞠目结舌。非常神奇地,π和e居然出现在了阶乘的近似公式中!

    发现Problem I是一道水题已经是很晚的事了,最后仍然没来得及把它调试完,太可惜了。前40名队伍中就只有我们没做这道题。Problem G据说也是水题,很多队伍都做了。Problem E也是一道相当科学的题目,我发现了一个nlogn的算法,但没时间写代码了。还有一道题目就是Zen Puzzle Garden游戏求解,一看就是BT的搜索,没一个参赛队伍做了那道题。Zen Puzzle Garden真的是个电脑游戏,就和尚扫地那个,网上都有下载的,还不错。另外两道题分别是一道简单的计算几何和一道简单的图论题。leimiaos顺利完成了那道图论题,计算几何那道题我们都不敢写。所有的题目都可以在这里看到。

    最后的结果,我们只AC了10道题中的4道。ACM果然是拼时间的,好多题目我们都会,就是没时间写了。我N多年没写过代码了,昨天绝大多数代码都是leimiaos写的。也好嘛,这次就是抱着玩玩的心态来的,也长了一些经验。明年赛前我可能真的会认真准备一下。还有三年的机会呢,慢慢来吧。
    整场比赛的第一名AC了8道题,其中5道都是一次通过。你们猜这个队伍是哪三个人?告诉你,牛大B了,真的牛大B了。三个人分别是唐文斌、郭华阳、王栋。这次比赛是允许外校队伍报名参加的。

    最后,非常感谢网友dahe_1984请我吃饭喝酒!昨晚的聊天非常愉快,喝得也很尽兴。

21 条评论

回复给 Xay 取消回复

  ×  8  =  32