ACM/ICPC World Finals 2013 总结

回来在SNS看到满屏幕的宁波理工虐了浙大的消息简直是喜大普奔……
虽然很不想总结,但是毕竟是一场final,还是写一点什么吧。
先说一下我的视角里的比赛进程。

开场
我搞定登陆,默写了vimrc。
然后看了DEF,感觉D题是搜索但是复杂度非常难算,我向来不喜欢先做这种复杂度要跪不跪的题目,于是跳过。

刷下board发现F台大过了,我想了一会儿,YY出了二分然后dp的解法,上去写完交了一下,WA。
怀疑了一下算法,让zYc上去拍D,跟prowindy讲了一遍,在prowindy还在理解的这个算法的时候突然想起我自己代码中一个错误,改后过了。
F 48(2)

zYc开始继续拍D,prowindy跟我说C是图论题,让我去看。
于是我想了一会儿发现是最短路+max flow,看着zYc还在拍D,又走马观花地看了一些别的题。后来瞄到zYc在用gdb调D于是把他拍下来上去敲了,很快调过sample以后1Y。
C 114(1)

好像这时候zYc开始交D,TLE,TLE,TLE……
prowindy看着形势不对跑上去拍掉zYc开始敲A。
zYc喊我去帮忙看D,我说这样我们很容易在A题之后就没有题了,于是我去想H题。
想到了一个500^3的算法,犹豫了一下,看着4秒的时限,还是决定开搞。
然后等着prowindy交了A,WA……
于是我上去把H敲了,1Y。
H 189(1)

prowindy在我敲H的途中好像发现了A题一个错误,改了以后还是WA。
我感觉不能再让队友掉在坑里,于是回去帮忙debug,prowindy跟我说了一下A题题意以及做法,然后我第一反应就是做法不靠谱,也可能是他没跟我说清楚吧,感觉他说的那个长得不太像充要条件。我重新YY了一遍,每个接口拆成上和右两个点,dfs判环,发现过不了sample。瞬间反应过来dfs判环还是很麻烦的,我那么写是不对的,于是直接换成3个for的bellman-ford求最长路判环,敲完就过了sample,交上去就1Y了。
A 264(3)

这时prowindy已经把zYc的D题扔掉重写了一个,这回是WA, WA, WA了……
我也一起看D,但是还是看不出哪里能WA。
差不多也是这时候,zYc把J敲好了,但是直到比赛结束都死活过不了sample,赛后才发现是算扇形面积的时候少除了个2。

然后比赛就这样以4题结束了。

其实赛前我就一直说,我们队怎么样,全看zYc的发挥。
因为在平常训练里就看得出来,我是比较稳定的输出,zYc是非常不稳定的爆发性输出,prowindy则是出数据和debug能力比较强的辅助。
这回zYc从头卡到尾-_-b,也不是我所能控制的了……

总得来说今天我自己的手是比较稳的,交了5次,过了4题。策略上其实也是比较正常的,但是我帮别人debug的能力没有足够地强,导致也没能让队友打出状态……
如果今天只让我一个人coding,让zYc和prowindy推公式和想算法大概会好很多吧。
说实话这场比赛我感觉自己状态好一点的时候单挑都不止5题-_-b。
最后翻了翻board,发现在我们后面的再也没有topcoder rating总和比我们高的了,可见无论是主观上还是客观上来看我们的发挥也已经到达了不能更糟糕的地步了。

撇掉上面一些发挥上的原因,从客观上看我观察到的大概有这么几个原因:

  1. zYc写几何不用模板(我们整场比赛就没碰过那本模板- -b)
  2. zYc的编程习惯导致程序非常难懂且容易出错,一般要考虑很多情况才能明白他的代码到底有没有可能出错。这在problems比较tricky的final上是致命的……
  3. prowindy学长和final的风格不太match,学长强在乱搞,但是final的problems上思维陷阱到处都是,不扎实点一般是过不去的。
  4. 我帮别人debug的能力比较低下,编码速度和水平也没有足够高。作为队长,没有能调起队员状态……

想到什么再补充吧……

有梦好甜蜜


淅沥的雨思
像那六弦琴
它叮叮咚咚
是那么动听
斑驳的树影
像梦的森林
引领我走进
五彩的神秘
满天的繁星
掩藏我点点的密秘
胡:夏日的蝉鸣
鸣唱我对未来的希冀
dream dream
everyday has a dream has a dream
总觉得
有梦好甜蜜

满天的繁星
掩藏我点点的密秘
夏日的蝉鸣
鸣唱我对未来的希冀
dream dream
everyday has a dream has a dream
总觉得
有梦好甜蜜
满天的繁星
掩藏我点点的密秘
夏日的蝉鸣
鸣唱我对未来的希冀
dream dream
everyday has a dream has a dream
总觉得
有梦好甜蜜
Da da da da da……
有梦好甜蜜

写在2013的final前

跌跌撞撞地终于到了final前,终究是想写点什么。

  • 去年今日

    距离上一次去St. Petersburg的VK Cup已经快一年了。当时我还是一个充满热血的大一小朋友,而现在已经是快要搬去玉泉的老家伙了,想想真是令人潸然泪下。记得当时看到WJMZBMR、shangjingbo、7k+、squark、tourist等等神牛真是内心激动,难以言表啊。嗯,我还记得玩那个开车的AI大赛WJMZBMR用那个轮胎道具的一箭双雕,简直是炸天。然后我写的AI策略是假如有两个人比我离那个道具更近,就果断放弃去吃别的道具。然后这样的逃兵流搞法竟然还赢了tourist一场……最后好像还水进了半决赛。XD

    当时是第一次出国,看着外面的世界,越发觉得自己的渺小。手里的资本,大概就只有年轻了吧。

  • 队长

    暑期校队选拔以后半推半就地被骗进了1队……于是也顺理成章地当了队长。这绝对是改变我人生轨迹的一件事情。在此之前,OI和ACM的界限其实并没有那么明显,至多是术业有专攻,技能可以互补这样子。但是自从当了队长……就深切感受到原来真的随时可以1+1+1 < 1。不应该再像以前那样只关注自己手上的事情,谁手上卡着什么东西得主动去了解,要根据每个人的状态和情况去想现在该干什么,必要时果断打断队友/自己手头上的事情。确切来说就是关注的点从自己手头上的事扩散到了队友和别的一些东西上。

    有时候人和人之间的方法论和世界观的差异是巨大的,也正因为如此才有互补一说。当队长的判断和队员的判断不一致的时候,询问队员有多少把握往往是比较好的方法。但是一定要限定时间,因为只要是人,就可能有判断上的失误。如果一段时间以后感觉这样不对,就必须果断打断。

    很多时候人会舍不得自己曾经付出过的努力,总觉得已经付出了这么多,就差一点了,然而其实这一点所耗费的时间其实很可能是不可接受的。甚至从一开始就完全错了。浪子回头,为时不晚。

  • Regional

    其实据说我们是史上最圡的1队,因为别的1队从来没有在组队训练的时候被2队~5队都踩过:) (咱们这叫挥发度好吗T_T)
    在中大和复旦出题的赛区都季军了,但是两个北大的赛区金牌都没拿到,再次被2队~5队都踩成狗了……(= =b幸好都打星了)。这大概说明了我们基本功和模板真的不够扎实吧……

  • 胆量

    也许我就是这么一个谨慎(又名想太多)的人,已经不知道多少次我觉得铁定TLE苦思冥想结果被prowindy用最简单的方法直接搞过……Regional成都那一站,有一道就是因为算错复杂度(应该用积分算的555),自己骗自己,结果一个简单的枚举,搞得前面的队伍里面就我们到最后也没过。不然随便弄一个几行的枚举上去就亚军了,那一场其实是我们唯一一次可能夺冠的机会,因为我死磕磕出了一道冠亚军都没idea的字符串,但最后还是输给了胆量和基本功。

  • Regional之后

    1. 中俄对抗赛的发挥有点糟糕,但是被屠其实也是意料之中。意外地发现tourist和VK Cup上相比,憔悴了不少……顺便见识了中大场场翻盘的神奇能力。
    2. 抱着猛犸大腿终于把校赛和省赛的冠军撸到手了。
    3. 在杭州邀请赛上被hust屠了,亚军一个233,FattyPenguin确实厉害。人在抱怨之前,理应想想自己有没有什么地方不对…… 于是每次想抱怨的时候我都会想,我自己没有shi哥强,刷的也没人家多,所以也没有什么好抱怨的了吧。

最后装下文艺青年:今当远离,临表涕零,不知所言。

SRM 575

250pt
找规律……
比较瞎的是官方题解也是这么干的。
找规律,然后用数学归纳法证明这个规律的……

500pt
算期望的好题,用矩阵混过去的,2*10^7次double运算居然TLE了。
注意利用期望的累加性质和线性性质就好。

1000pt
经典的拆点网络流,题目给定了黑白格染色,然后再把白格按所在行的奇偶性再染色一次色,就可以流了。
-.-总之网络流或者最小割的关键还是于2这个数字。要么A要么B。