又是一年校赛

acm_zju_logo

又是天气预报不准的一天,又是一年的ACM校赛。

自从来到大学,我其实不想参加acm这样的比赛。在我看来,这样的比赛要取得好成绩需要高强度的、义无反顾的、不成仙便成仁练习。另一方面,Linux里面乱七八糟五花八门的好玩的东西迅速吸引了对Windows赶到乏味的我,一度到了难以自拔的地步。

现在,不再生疏Linux的我,对这一领域的热情慢慢降温,对Windows的抗拒也逐渐麻木。当我在这样一个中立的位置的时,对于各种事情,都以“大不自多,海纳江河”的态度来对待,自然对于acm这样的比赛也不要存在抗拒或者畏惧,去参加就好了。

这次校赛必须是三个人组队才可以参加,校队成员在内部自己组完了队,我有幸和楼梯男与pluskid(按年级排序)组成一队。各种各样的队名彰显着参赛人员的良好创意,我们队一致认为pluskid想到的“foobar”这个词比较好,就用这个当作队名了。正如这样一个词,是说不出来具体是什么意思一样,我们参赛的目标也是说不清楚的吧(我们队实际上只能算作是业余队,我自己已经很长时间没有做题目了,楼梯男似乎是和我一开始提到的那种想法相近吧,pluskid一直没有在算法竞赛这方面专业练习过)。也许这就是所谓的“有容乃大,无欲则刚”,我真的很喜欢这种感觉呢 :-)

由于学长们都在住在玉泉校区,上午的签到和抽签是我去的,不幸地抽到了三楼的机器,内存大小和CPU速度都是二楼机器的四分之一,显示器是CRT型的,相比之下,二楼的大分辨率LCD机器真是很好啊。编程工具虽然有很多,但是大多比较旧,没有Visual Studio .NET,我们最后是使用Dev-cpp来写程序的,只有必须要跟踪调试的时候才会用VC6。

下午比赛从1:30开始,4个小时9道题目。我读前三题,陆续觉得都可以做,第三题忽略了测试数据的强度,错了几次才对,前两题都写一遍就对了。我觉得自己写程序这么长时间,最好的感觉就是代码稳定可靠性好,写出来之后不用改来改去的,有时候程序写出来就达到预期效果,自己都感到惊奇。

虽然是一个队,但是三个人之间有些做法是不同的。我条件反射似地看完三道题再开始做,沿袭以前很久以前比赛的习惯。殊不知ACM比赛提前搞定些题目还是划算的,楼梯男则关注所有队的进展,从最容易的题目开始做起,也很快搞定了两道题。这次比赛有一道比较难的几何题,涉及到浮点数,解方程计算等等。我最不喜欢有浮点数的题目,pluskid对计算机图形学方面有些研究,最后完成了这道题 :-)。

后来我们还尝试了另外的两道题,结果因为时间不够用而留下了遗憾。不过已经排到了第四位, 不错的位置了,前三队都是校队成员。我觉得这次比赛,我们队配合得挺好的,也有一些幸运的因素,最后结果也挺好的,还留下了快乐的记忆 :-P

对这次比赛不太关心的同学,文章到这里就结束了。下面转载一份解题报告,是HHanger写的:

校赛解题报告精简版 by HH

A Square Root Day 现场赛36.13% (155/429)/同步赛42.27% (290/686)
秒杀题,但是在题意方面出了一些问题,一种理解是日和月必须相同,于是一年最多只有一个Square Root Day,一年有一个Square Root Day当且仅当该年的最后2或3位是1-12的平方,这12个完全平方数中的一个。还有一种理解是日和月可以不相同,可以一个是后三位的平方根,另一个是后两位的平方根,于是会多几个日子,比如1225年5月15日。因为题意不清,所以最后两种理解都算过。

B Number of Containers 现场赛4.46% (32/717)/同步赛20.73% (102/492)
中等难度题,n可以很大,所以O(n)的算法显然是会TLE的。首先可以发现,f(n, x) = (n – x) / x,也就是n / x – 1,所以求解F(n)就是i从1到n,对n / i进行求和,最后再减去n就是答案。考察n / i随着i增大时候的情况,可以发现i越增大,n / i这个值变化得越小。于是可以把整个求和过程分成两块,对以1 <= i <= sqrt(n),直接求每个f(n, i)进行累加;而对于sqrt(n) < i <= n,他们的n / i的取值范围为1 – sqrt(n),也就是说,这个范围数虽然多,但是至多只有sqrt(n)种取值,于是我们改成枚举每种取值,求对应该取值的i的个数。这样两块的复杂度都是sqrt(n),可以满足时限要求。还有一点是最后的结果会超出int范围,需要使用long long类型。
题目因为被修改了一下,所以也有个地方没说清楚,不过应该不会误导人,只是理解起来有点费力。比赛的时候被放到了B题的位置,结果N多的队伍直接就来个直接暴力的,下次这种题目应该靠后一点放……

C Rounding or Truncation 现场赛2.12% (7/330)/同步赛7.55% (34/450)
中等难度题,有不少的trick。主要要解决的问题就是通过一组m和p的值,来推测在两种策略下,文件总数可能的取值范围。可以解决这个的话,只要对每组m 和p对应的区间求交然后判断交是非为空即可。对于Rounding模式,p可以上下分别浮动0.5个百分点,其中往上的浮动是刚好取不到的(否则就向上进位了)。对于Truncation模式,p可以向上浮动小于1个百分点。这里还有一个问题是p等于0和等于100的时候要特别处理下,p等于0的时候,文件总数的上限是无数;p等于100的时候,因为没有向上浮动的空间了,所以对于Rounding模式,只能向下浮动,对于Truncation模式则完全不能浮动,只能是确定的100。有了p的取值范围就可以去根据m来计算文件总数的范围了,可以用double直接计算,但是处理不好很可能会有误差,推荐直接用整数处理,对p乘以10后,浮动的百分点数也就是整数了。能处理好上面的各项后,应该就能AC了。

D Elune’s Arrow 现场赛8.95% (12/134)/同步赛8.02% (11/137)
中等偏难的几何题,不是很好想到解法。题目的模型就是用一个固定速度的圆去撞击一个朝固定方向进行匀速直线运动的圆,要选择角度从而尽可能早撞到移动的圆,输出最早撞到的时间。所谓圆撞到圆,就是圆心距离等于半径和,这里可以作一个模型转换,把逃跑的圆看成一个点,把它的半径加到追击的圆上。于是现在就是一个圆去追击一个匀速直线运动的点,依然不是很好处理。因为圆可以向所有角度发射,所以假设圆初始半径为r,速度为v,则在某个t时刻,圆可能触碰到的位置为一个半径为r+vt的圆。于是模型又可以这样转化:一个有初始半径的圆以速度v扩大半径,求何时能碰到一个直线运动的点。因为刚撞到的时候恰好是点在圆上的时候,因此可以立一个关于t的一元二次方程,最后求解方程,如果两个解都小于0则无解,否则输出最小的正解。
PS,这题也可以用其他ws的方法来解决,比如我用枚举角度+三分过了。

E Beverages for Sale 现场赛0.00% (0/2)/同步赛0.00% (0/1)
压轴题。题目给出的是这样一个模型:有一个可分割货物的集合A和购买者的集合B,每个购买者有各自拥有的钱的数量,而每种货物也有各自的数量。其中每个购买者只会购买A的某一个子集。购买者对货物的种类不关心,只想获得最多数量的货物。购买者只会购买他感兴趣的货物中价格最便宜的那些。题目要分析出这样一个模型的稳定状态,也就是说确定各种货物的价格,使得所有货物都卖完,所有购买者的钱也都用完。
我们可以构这样的一个图,所有货物和所有对它们感兴趣的购买者之间连边,流量为无穷(如果某一个货物或者某一个购买者没有任何边,则直接输出Impossible)。对于每个购买者,向一个汇点sink连一条边,流量为他们各自的钱数。然后从一个源点source向每一种货物连一条边,边的流量为货物的价格x。我们首先假设所有货物的价格都是一样的,我们需要二分这个价格x,使得所有的货物刚好可以全部被卖出去,也就是说确定最大的x,使得(source, A B sink)是图的一个最小割。然后考察假设这个时候的残余网络,假设在残余网络中可以到达sink的节点集合为W,设S=A-W,则集合S的所有潜在购买者(对S中任意一个货物感兴趣的购买者)都已经用完了他们的钱,如果再增加x,则会导致S的货物剩余。于是我们可以把所有集合S中的货物价格设置为x。接着,我们把集合S和S的所有潜在购买者集合从网络中去除,提高剩余货物的价格继续前面的步骤,如此循环往复,就可以把所有货物的价格确定下来的。

F Calculate With Abacus 现场赛39.59% (118/298)/同步赛60.00% (240/400)
描述有点长的简单题。已经保证了输入的算盘都是合法的,于是只要计算出算盘所代表的数字即可。其中一种方法就是看每一列的上下部分的|位置,就可以推算出该列代表的数字。这次也没有trick,一般只要读懂题就可以写对了。

G Number Game 现场赛5.36% (11/205)/同步赛13.52% (43/318)
中等难度题。有三个数字,每次可以去掉一个,然后加上剩下两个的和减一。问是否可以从给定的三个数得到给定的另外三个数字。可以发现,如果正着推的话,每次有三种选择,无法有效判断最终的三个数字是否可达。于是考虑逆着推,已知当前的三个数,其中最大的那个一定是新加的,而次大的那个一定是再前一次新加的,于是可以推算出被擦掉的那个数为次大数加一减最小数。这样一来,可以有唯一确定的方法递推回去。不过需要注意的是,正推的第一步,因为当前的三个数不一定满足a+b=c-1这样的等式,所以逆推的时候是无法确定被擦掉的数是多少的。所以,可以对初始的三个数枚举第一次擦掉的数为哪个,得到三种满足等式的情况。于是逆推的时候,一旦能匹配其中的一个就可以了。还有一点就是,只有当三个数满足等式才可以逆推。
赛前JJ曾说这题可能比F还简单,结果不知道什么原因大家都不敢碰。。

H Cover the String 现场赛0.00% (0/13)/同步赛2.43% (1/41)
中等偏难的动态规划题,需要好好优化才能把复杂度降下来。我的做法是:首先用所有的tiles构造一个trie。用s[i, j]表示原串从i到j的子串。然后考虑从后往前用tile来覆盖串,根据规则,每次放的串起始位置要在上一个之前,结束位置也要在上一个之前。dp[i] [j]表示覆盖原串从第i位开始到最后的子串,且最后一个使用的tile覆盖了s[i, j]的方法数。还有一个sum数组,sum[i]表示当前所有的覆盖中,最后一个tile开始于原串第i位或者之前,结束于第i位之后数量。
for i from n – 1 to 0
for j from i to n – 1 // 考虑覆盖s[i, j]
dp[i][j] = (number of tiles cover s[i, j]) * sum[j];
for j from n – 1 to i + 1 // 更新sum数组
sum[j – 1] += Sum(dp[i][j] .. dp[i][n – 1]);
最后Sum(dp[0][0] .. dp[0][n – 1])就是解。其中number of tiles cover s[i, j]可以用trie在O(1)时间内得到,Sum(dp[i][j] .. dp[i][n – 1])这块可以用一个临时变量累加来优化成O(1),因此整个dp过程复杂度为O(1000^2)。考虑到子串的长度最多为200,因此可以把j这层循环变成tile的长度,这样复杂度变成O(1000*200),不包括前面建trie的时间。
如果不想使用trie,可以用kmp算法来预处理,同样可以在O(1)时间得到number of tiles cover s[i, j]。

I Nine Interlinks 现场赛28.29% (116/410)/同步赛37.54% (202/538)
简单的动态规划题,应该不难找到递归方程,就算不会动规,应该也能找到规律来求解。要把前n个变成on,首先把前n-1个变成on,然后把前n-2个变成 off,然后把第n个变成on,然后把前n-2个变成on。所以dp[1] = 1, dp[2] = 2, dp[i] = dp[i – 1] + dp[i – 2] * 2 + 1。

其中的B题,可以不用Sqrt分成两段。下面的f(n)是对上面提到的f(n, i)累加的结果,也是对于一个n,最终要输出的答案:

long long f(int n) {
    long long s = 0;
    for (int i = 1; i < n; i++ ) {
        int t = n / t;
        s += (t - i + 1) * (n / i - 1);
        i = t;
    }
    return s;
}

3 thoughts on “又是一年校赛

  1. 今年校赛奖金变少,保研名额又似乎名存实亡,而且强制要求必须三人组队,我觉得这样的大环境下,ACM校赛传统意义上的“争上游”的意味大幅减弱,愿意来参赛的或多或少有着各种各样有意思的目的(同步赛的提交次数与现场赛持平就很能说明问题)。 我觉得比赛,或者OS选择的争论之类的问题,还是要尽量不被“主流”的想法或者“主流”的争论所干扰,按照自己的想法来面对。

  2. @houshui: 观察起来,NOIP也取消了保送资格,各方面的动作都是自然选择的结果。尽管如此,acm比赛仍然有它的意义,还是会有人会去的。人各有志,经验建立起的价值观不同,最终的选择还是自己做出的。就拿我自己来说,虽然现在能够欣然各种不同的事物,但是还是有自己偏好的,比如相比GTK,我更喜欢用Qt写程序,不排斥GTK主题,甚至Qt中也用了GTK主题 :-) 至于这次acm比赛,说参加完全没有目的也是不切实际的,只是目标不强,而参加是必要的,这是我自己坚信的,不是人云亦云的结果。

  3. Pingback: Rest Valley » Blog Archive » 校赛又一年

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>