Jasmine's Team Blog
2011“TCL杯”程序设计邀请赛简记 by IwfWcf

因为对之前的省赛和阿里巴巴个人赛颇感憋屈,兼之最近两场TC都保持了Raitng的递增,自觉Coding状态颇为不错,因此对这场比赛颇有期待。另外针对之前省赛的一些失误我在开赛前提了两点本场比赛的注意事项:

  1. 开赛阶段注意及时刷榜
  2. 将题目模型和大意写下来

开赛后wiza很快跟我说了一下C的题意,找一个序列中最大和最小值之差符合上界和下界限制的最长连续子序列长度。很快就想到了可以用ST算法+二分在O(nlogn)的时间内完成预处理和查询,于是马上上手敲ST模板。敲完后可能因为太久没写二分,居然花了大概15分钟才改出了二分的正确写法,第一次提交WA,大概40分钟时改了一个小错误后2Y。之后wiza上手敲H,我继续看题以及和CC讨论题目,很快将B的做法想出,简化版的表达式求值,并将G的做法和CC讲了一下,加了一点限制条件的斐波拉契数列,决定由他去敲高精度。wiza敲完H后我上手敲B,第一次提交WA,将函数的返回类型改成__int64后再交还是WA,检查发现函数内的一个循环语句中少了一个修改变量值的语句,3Y……接着CC去敲G,高精度用的是我的Pascal模板,敲完调了好一会后提交,WA……打印代码出来后换wiza去敲A,不久AC之。而我和CC则一起Debug G,因为我重新读了题目后怀疑可能要考虑前缀0的情况,提出一个修改方案让CC去改,CC对我的思路似乎并不完全理解以致实现有些问题,于是我自己上手去改,改好后再交还是WA,于是3人一起出各种数据来cha G的程序,但都通过了。为了验证高精度的正确性我又特意写了个朴素的用__int64实现的程序来对拍,也没能发现错误。之后wiza怀疑前缀0的情况是我想多了,让我去掉该处理后重新交一次,依然WA……于是我暂时放弃这题,辗转于D和I,wiza则尝试去写J。期间想到一个D的暴力方法打算去水一下,但敲的途中发现空间无法承受,而空间可以承受的纯粹模拟式暴力方法我觉得时间上的复杂度根本连水的价值都没有,遂放弃……I则推出了一个错误的规律,敲出来提交后返回WA……wiza的J似乎没有写完,其曾经打算用Java重写一次G,但也因觉得高精度不可能出错而作罢……于是最终只出了4题,排在第13位……

赛后得知G用__int64就可以水过,一开始怀疑是数据错误,但后来得知有队伍用高精度也过了,于是至今依然错得莫名其妙后来wiza告知是对题意理解有误差(不过对wiza引用的RJ的那个对前缀0的情况解释我依然觉得非常牵强)……对于当时一开始没有让wiza用Java去写真是悔之莫及,不过以后凡是涉及到高精度的题目还是用Java去写方便很多……而D则是用那种被我认为水的价值都没有的纯粹模拟式暴力方法就能过的,RJ表示之所以判断出可以用暴力过的依据是很多排名靠后的队伍都过了这题……E则是要用矩阵乘法+快速幂来优化DP……

本场比赛其实可以算是Jasmine组队以来表现最好的比赛之一,特别是我赛前提到的注意事项中的第二点做得很好,非常有效地缩短了读题时间耗费。而本场除E外实际上第二难的C我早早地在40分钟就过掉了,在罚时上本应因此而占有优势的,无奈因为对G的题目描述问题开G时的决策错误(没有让wiza用Java来写以致于引发了后面耗费的那么多时间)以及比赛中看榜经验的不足而让这一次离奖金最接近的机会擦肩而过……虽然对计科如此恶心的数据规模以及题目描述的怨念也非常之多……

GDCPC 2011简记 by IwfWcf

话说不知道在哪里得来的印象,我一直以为省赛是在珠海举行,于是乎我满怀着也许会偶遇某人的期待迎接省赛的到来。但在试机的前一天我才知道原来省赛是在中大的大学城校区举行……于是试机当天我没有多少兴致,要不是因为是第一次去省赛,原本是准备不去的(嘛,后来才知道我对试机的轻视原来那么无知,按照某牛的说法,试机的题目对比赛的难度有提示作用)。试机似乎预示了我们明天比赛并不会太顺利,A题我看不懂题意,让wiza看了后才知道是水题,于是wiza上手秒掉。B题是求环状最大连续子序列和,我想当然地认为只需按一般的环状DP般将序列长度拓展为2n来处理即可,但敲完后才发现这样处理存在一个非常明显的错误,于是按wiza的方法求一次最大连续子序列和后将序列元素取反再求一次后比较前者与总和减后者之大小,取较大值输出。第三题正好是和早上周赛做过的一题非常类似的BFS,不过因为拓展节点顺序的处理比较复杂(后来狮凶提示后才想到可以先预处理),我错误地认为可以用记忆化搜索解决,于是折腾到最后都没做出来……

回程的路上我跟wiza和CC说明天最重要的是要保证水题不卡题,并且今晚要休息好,三人雄心勃勃地打算绝对不要重蹈珠海赛午饭之后就没再过题的覆辙。

省赛当天,在开赛前选手等候的空地,昨天惊鸿一瞥的省赛吉祥物出现了。于是迎来了选手一轮又一轮的合照热潮,而且经常有某些选手手贱地去戏弄该吉祥物……为那位穿着吉祥物衣服的女生哀叹……到了赛场后发现居然有纪念品送(3个Badge和一个鼠标垫,后来才知道鼠标垫是每年的常规赠品)。wiza在10分钟时1Y了本场最水的A,然后CC上手去敲I,敲好之后发现思路有误,换我去敲F,因为之前做过类似的题目,因此建图模型一眼就看了出来,虽然看数据范围(n<=2000)觉得很大,但一来没有别的建图思路,二来觉得网络流的实际复杂度一般都会远小于理论复杂度,于是还是上手将Dinic的模板敲了出来并提交。返回TLE,之后又加了两个优化再提交了两次,但依然TLE……赛后在自己的Laptop上跑了一下极限数据,我的Dinic要65s才能出解,而CC给我的ISAP则要80s才能出解,因此否定了是算法效率的原因,但无奈至今未想到正确的建图方法……因为F过不了我开始去看其他题目,发现K也是一题水题,简单地规划了一下后就上手去敲,结果一直莫名其妙地WA,直到183分钟才因为CC帮我看到了代码里一个循环的结束值限定条件有误改后3Y……之后CC推出了G的规律,214分钟3Y……之后的时间里我和CC想I,wiza想E,我很肯定CC的I的Hash会有冲突,因此改用map+预处理优化来实现,很自然地没能水过。在距离比赛结束40分钟时我想到可以用Trie来做,于是马上上手敲,但因为受CC之前的代码思路影响,建树的选取有所失误,依然TLE,赛后才想到更优的建树方案(虽然没机会验证是否能AC)……赛后得知I是一题纯粹的模板题—AC自动机,无奈3人都只闻其名不知其理,自己的模板库又没有这一模板,于是就这么杯具了……而wiza的E最终也没能及时搞出来……

于是省赛我们遭遇了组队以来的最差成绩,100名……成绩之所以会如此糟糕,一方面固然是实力不济,其他队轻松过掉的I却连正确的模型都不知道,应该可以搞的C却连题意都没理解……但同样也和我们的开题策略以及水题通过速度有关,没有及时刷榜以致敲完了3题才发现K是本场的第二水题,G的算法其实非常直觉,我一读完题就想到了,但因为心思还一边放在F上而没有全力尝试去证明,以至于拖到214分钟才过……省赛的打击让我们非常清楚地看到了自身实力的短板,为未来计,也未尝不是一件好事,希望通过到9月份之前的时间的恶补,能让自身知识结构的漏洞大量减少,争取有机会能代表学院参加区域赛。

2011 ACM-ICPC 珠海区域赛简记 by IwfWcf

我从初二开始就每天都在互联网上进行翻墙运动,不过一直没有尝试过物理翻墙,虽然高中一直想要了却此夙愿,却苦无机会(每次校运会都和NOIP复赛日期重叠……),于是尽管这次珠海赛SCUT的日程很让人无语(早上6:10在宿舍楼下集合),但却也给了我一个完成这一遗憾的机会。

话说上了大学后,我就一直在筹划着我的翻墙计划,经过一番考察拟定了三个方案:

  1. 借助一楼的防盗网和二楼的栏杆完成翻墙
  2. 借助花坛和辅导员办公室窗口上面的平台完成翻墙
  3. 借助前门的扶手和二楼的平台完成翻墙

其中第一种方案被我认定为技术难度和风险系数都是最低的,不过到了真正要实行的时候,因为自己没有经验,因此也不敢妄下定论,于是就被翻墙经验非常丰富的CC童鞋给带去实践第二种方案。CC童鞋非常驾轻就熟地完成了翻墙工作,整个过程行云流水、身轻如燕。不过到了我和wiza去尝试的时候却发现远非看起来那般轻松,翻到辅导员办公室窗口上的那个平台就让我非常小心翼翼,姿势非常不雅观。到了平台后发现距离地面大概有两米,wiza童鞋一个不甚,落脚点没有计算好就杯具地以臀部着地。有了前车之鉴我就更加谨慎,继续用刚才那种不雅观的姿势保持悬挂的稳定性,然后为了避免重蹈wiza的覆辙,我用脚踹踏窗户借力纵深下跳着地。嘛,着地的套路和姿势看着应该都还不错,不过效果却并不甚好,我从落地开始一个星期脖子都处于落枕般的状态……

比赛开始后CC非常给力,瞬秒了A和B,我也很快发现K是对字符串的所有子串排一次序输出最大子串的水题,但因为脖子的原因自己不想去敲代码,于是把做法跟wiza说了一遍后让他去敲。wiza通过STL只用了20行代码就敲完了,不过第一次提交时因为某个低级错误返回TLE,我坚信算法没错,CC看了一会代码找了错误,改后2Y。很快我又发现F是一题中学骗分时写过N次的暴力DFS,想着虽然今天状态不好但应该不可能会写错就直接上去敲,谁知道我的状态真是杯具到了无以复加的程度,居然在敲完后调了近半小时才AC。之后wiza把E也搞了出来,此时比赛大概过了一半的时间。因为罚时比较理想,大概排在第10名左右。

之后的半场比赛就完全酱油了,吃过午餐后再也没有出题……C题我在高中时曾经在一场模拟赛里见过,不过当时不求甚解地没去搞清楚做法,于是这次杯具地没看出是DP……D题模型非常清晰,我也知道可以用后缀数组优化,但无奈不会写后缀数组……G题是全场没有队过的非常复杂的模拟题;H题是一题几何题,这块是我们队的弱项,没有人有信心写出;I题是这场比赛的分水岭,基本上过了6题的队伍都是过了这一题,因此后半场一直想把这题搞出来,但无奈因为没有看出正确的模型最终还是过不了,赛后听讲评得知是线段树;J题没做出来也是本场的一大遗憾,我没有留意到其中一个条件可以进行一个巧妙的转化,而觉得是一题很复杂的图论题。

虽然因为后半场没能再出题而在题数上无法和其他队伍拉开差距,三人对于本场比赛的表现都不甚满意。但因为罚时的优势,最终的排名却是Jasmine成立以来那么多场里成绩最好的一场—Rank 24。因此我认为本场比赛还是有值得重视的成功经验的。首先是开题策略非常正确,基本上没有造成机时的浪费。其次是过题速度和通过率都还不错,没有在水题上卡太长时间。

本学期6场比赛,我们队在每一场都有留下遗憾,但相对来说这场比赛的遗憾是最少的且成绩也是最好的,我想一个很重要的原因就是以上提到的两点成功经验。对算法的涉猎面不够广和不够深,对常见题目模型的了解不够多是我们队一个很明显的劣势,因此在题目梯度区分比较合理的比赛我们队在题数上比较容易被拉开差距。但在题目梯度区分不合理的比赛,如果能做好以上提到的两点,其实我们的成绩也可以达到一个比较理想的排位的(至少前两次的校赛应该能拿到奖金)。此外这两点对于比赛的心态的影响也是非常重要的,如果在水题上卡题,那心态就会变得急躁,一来影响了后面题目的思考时间,二来影响思考效果,因此在注重算法学习提高能力的同时我们也不应忽视这个学期积累下来的比赛经验和技巧。