badge-and-medal

live-ranklist

出发

浙大一行我、欧阳、moon姐、can哥加教务处魏老师一共五人。5月25日清早从紫金港去浦东飞三藩,在三藩机场停留了近半天,再飞奥兰多。整个旅程用了超过一天,而且我们出发也要比绝大多数队伍晚好几天,所以调整的时间不算富余。因为The Peabody Orlando定不到坑,我们前两天都住在Hilton Garden Inn。这两天can哥和魏老师都忙着shopping,而我除了第一天上午跟着出去了一趟,其余时间都宅在酒店。人人上看到各个学校都在美国各地玩,只有羡慕嫉妒恨了。临走前在酒店第一次通了东方红魔乡的Hard,虽然好多天没写代码了,看来状态应该还是不错的。

报到

由于两位老师在shopping,酒店check in是我们仨自己搞定的。晚上报到,拿到了很多东西,包括IBM的礼物,Peabody吉祥物。不知道ICPC daily的第一期是什么时候拿的,今年的ICPC daily我差第一期就集齐全套了 >_<

第一天玩的地方是Sea World,开始之前我们先把IBM 100周年的宣传视频二周目了一遍,然后是IBM宣讲。之后娱乐时间开始,首先是shamu表演,然后就是各自游玩。这一天玩得很开心,我们都觉得这一天才是我们到美国来的第一天……

试机

试机赛不再是原来的求1和N之间所有数的和了,似乎从去年开始就变成了3*4道水题。之前虽然有一场混乱的网上练习赛,不过这次才算我们第一次真正使用WF的OJ——KTH开发的KATTIS。因为KATTIS的文档写得比较详细,所以试机赛要测的东西就不是那么多了。试机赛还是以试机为主,慢慢悠悠的,也没有一题多交,所以排在很后面。

练习

练习赛全是往年的WF题的样子,其中最后两题是难题。练习赛我想拼一下手速,因为正赛求稳为主,所以想在试机赛抢个First Blood玩玩,不过没能如愿。欧阳写最后一题的时候状态有些糟糕,还好正赛完全没有问题。最后貌似我们抢了个第二,被台大踩了。

本番

个人觉得大赛前,良好的睡眠比什么都重要,所以到美国后几天,也有督促两位队友早睡不早起。比赛前一天更是早早睡了,美帝的早饭午饭和晚饭都很难吃,也就我能吃得稍微多一点。早饭时间,can哥给我们每人倒了杯咖啡,然后建议我们带上长袖到赛场上去,美帝的空调温度调得很低,我和moon姐不太习惯,欧阳倒是很喜欢的样子。赛前则依然是Bill的忽悠时间,表示听不懂haha point……

比赛开始,老套路,欧阳搞定登录,敲.vimrc。我拆题,然后moon姐从前往后看,我从E开始看,欧阳从后往前看。欧阳看了K,觉得算简单题,于是给我们讲了算法上机写。K没多久写完,我问了两个容易出bug的地方,欧阳表示没问题,于是提交K1y(19),还是算很快的。我看了EFG,然后欧阳上去写题的时候看了J,觉得很简单,就准备写。J一开始选择用vector<int>记方案,发现太慢,于是改成bool[][]记方案,中间打印检查了一下。欧阳和moon姐利用这个间隙也开始写C。随后J1y(49)C1y(60)。这时候刷了一下board,我们3题以罚时优势登顶了(虽然之后又被踩了下来)。E一开始我没有注意到dx和dy的范围都很小,所以觉得比较复杂,moon姐指出这一点后就发现其水题的本质了,我给欧阳讲了算法后交给他写。因为转换后的坐标范围搞错而WA了一次,E2y(88)。我们再次爬到了第一。

4题后一下子没题搞了,机器都空了下来,这时候board上A和H已经有队伍AC了。B题moon姐表示看不太懂,于是先放着。D和moon姐稍微讨论了一下,没有想到正确的算法,丢掉了。F题一时也想不到算法。G题我和欧阳讨论,确定了一个多边形的最优的情况应该是所有点共圆,但不确定会不会钝角的时候解反而更差,欧阳觉得通过二维DP肯定没问题,不过这样复杂度就是O(n^3)的了,加上二分半径求解,肯定要超时的。不过既然机器空着,就让欧阳先去写了二分的部分。我和moon姐讨论A,moon姐首先想到了枚举乘的次数,然后我在纸上推了一下,发现后面只要贪心就好了,于是我换欧阳上机写A。A打印调试之后才过sample,提交后WA,经过反复打印和测试,最后A4y(169)。A题其实就是三个小bug,但每次都只找到一个就交了,浪费了很多时间,吃了很多罚时,最后提交的时候都有点紧张了。我写A的过程中,moon姐和欧阳讨论出了H,并利用我debug A题的空隙写完并H1y(153)。因为A拖了后腿,从5题开始我们就掉下来的,不过还保持在金牌区,反而是清华强势的保持着第一,并且是封board时唯一的7题。

之后欧阳继续搞G。我和moon姐把DFI都讨论了一下,虽然清华华丽丽的过了F,不过我和moon姐讨论只能得到一些基本的结论,想不到正确的算法,或者说想到的都不可实现。接下来发现B题过的队伍也多了起来,于是我去重读B题,读完发现B题很水……于是三个人讨论了一下,确定了暴力枚举旋转+求线性变换算法的正确性。然后让欧阳先暂停手上的G,去搞定B的旋转部分,而我准备写求线性变换部分。旋转部分就是堆计算几何模块,线性变换部分不过是一些if-else讨论多种情况,虽然情况有各种组合,但想清楚了写起来很简单。B一开始没过sample,然后发现枚举360旋转和线性变换有重复,改成180度就好了。然后交给欧阳,把输出改成题目要求的格式,提交后B1y(260)。这时候也没怎么注意board,心里觉得应该是奖牌锁定,但夺金还要看RP吧。

接下来时间还算富余,于是集中攻G。G这时候二分的代码已经写好了,并且经过几次debug后过了第一个sample。然后才发现题目顺序是给定的,不需要自己排序,于是修改之。然后我觉得如果能组成多边形就组成,否则砍掉最大的边就是最优的。这样写完之后一提交,才发现代码原先一段O(n^3)复杂度的循环没注释掉,结果白白吃了个TLE,注释后再交得到WA。然后我开始测各种数据,测出来发现处理钝角情况的二分部分有bug,改过之后依然是WA。再后来我通过测试发现确实有可能钝角的时候解反而更差,于是把贪心改成DP,如果不能组成或组成钝角,那么就取直接构成多边形和砍掉最长边分成两部分的最大值,提交后G4y(290)。过了G以后,我的第一反应是我们金牌应该是十拿九稳了。结果刷了一下board以后,我发现大多数的队伍都只开了七题,于是我和我的队友们说,不会夺冠了吧。比赛的最后十分钟,我们就一直在激动的算各个队伍的罚时。

夺冠

比赛倒计时结束后,我们知道我们有很大的可能是夺冠了,所以兴奋的同时也非常紧张。一步一步揭晓ranklist的时候,我们也一直在祈祷。当唯一在理论上可能超过我们的Nizhny Novgorod State University的B挂掉的时候,can哥直接在全场平静的情况下失态的连喊了几句“好!”,站在后面的我表示略汗= =b 之后就确定夺冠了,不过最后时刻,看着ranklist上Zhejiang University的最后一个Pending由蓝转绿,跃居版首的时候,还是无比兴奋,欢呼雀跃……

凯旋

Ceremony Dinner是Harry Potter主题的,结束后大家去IBM包场的Universal Studio嗨了一把。除了过山车,所有开放的地方都去玩了一趟,非常赞。WF结束后我在酒店休息了一天,期间看到了大家在98、88、QQ、人人、twitter上的祝贺,非常感谢大家,因为比较多,所以没能一一回复。最后一天,也正是儿童节,于是去了一趟迪斯尼,似乎相比Sea World和Universal Studio不那么好玩的样子。6月2日凌晨,我们离开奥兰多经芝加哥中转,搭上了回国的航班。第二天一出浦东机场,就遇到了同我们一样开心,前来接机的QSes,压力山大。

结语

这次比赛,我们的发挥和配合虽然不是完美无瑕,但绝对称得上相当出色。除了K和J,每道题都有至少两个人的参与,最后的两道题B和G还是欧阳和我两个人各写一部分代码,全队共同yy和调试的。赛前我们也经过了不少的训练和调整,相识3年,磨合10月,才使得我们能有今天的表现。关于我们夺冠的根本原因,可能像asmn总结的那样,因为我们出发前bg了,于是我们过了最关键的B题和G题 ^.^

发信人: watashi (watashi), 板面: Algorithm
标 题: ArcOfDream出发前攒RP
发信站: 飘渺水云间 (Thu May 19 00:57:02 2011), 转信

时间:暂定下周一
地点:TBD
人物:共同训练,一起南征北战的QSes
辛勤劳动,指导训练带队的JLs
还有其他给与我们帮助和支持的童鞋
事件:ArcOfDream WF 出发前 bg

回复报名~

http://watashi.ws/

watashiはわたし それだけ

※ 来源:·飘渺水云间 zju88.org·[FROM: watashi]

前年,在Fire和hhanger的带领下,三名没有任何OI背景,第一次参加WF的队员组成的Zodiac创造了历史,结束了浙大ACM的奖牌荒,一举取得第六名银牌的好成绩。随后我的两名队友退役,而我选择了继续玩,当然我也暗自定下了更高的目标。去年,由于深感自身能力的不足,更担忧队友能力的不足,我选择了自降三队。can哥虽然不支持我的选择,但两次电话后还是尊重的我的决定,现在看来,can哥和我一定都会觉得这是一个英明伟大的决定。而今年,确定队员的人选也让我头痛了几天,直到我到了火车上,才给于指导、欧阳和moon姐打了电话。当时我也没有讲太多自己的想法,主要说的似乎只有“用力”二字。

随后ArcOfDream成立,这是继gensokyo, tsukimisakura和musoufuuin后取的第四个东方系列队名,也算是寓意最好的一个。ArcOfDream在平日的训练里虽然鲜有超一流强队的表现,但至少是准一流强队的水准。Regional出征杭州福州的表现都不太好,也是比较郁闷的一件事。虽然在越南实现了卫冕,但个人觉得题目不是太好,含金量有限。

至于到World Finals最终夺冠,这个确实很出乎意料,毕竟WF模拟训练里我们也只在出发前一周拿过一次半的冠军。夺冠这种事,梦想过无数次,也在出发前半开玩笑的说过很多次,但从来没有当作目标考虑过。我想应该有很多队伍都在WF模拟训练里都拿过冠军吧,这次比赛之后也有很多队伍会觉得自己和冠军失之交臂吧,但这样的机会被我们把握住了,站在了最高的领奖台。当年Zodiac训练的时候,基本都在奖牌区比较稳妥的位置,最后我们拿了银牌;今年ArcOfDream训练的时候,基本都能混进金牌区踩Zodiac,最后我们拿了冠军。Zodiac和ArcOfDream平时训练什么水平,到WF就能毫不保留的发挥出来,这点我还是有点稍稍得意的。

有人在我之前的日志里问我是否训练了10000小时。非常惭愧的说,虽然即便不到5000小时也相差不远,但远远不到10000小时。比赛前我就想过,如果这次比得不如Zodiac,那么反省的时候我就说最根本的原因是没有练够10000小时,回想过去四年,我还是浪费了太多的时间在*过度*的灌水和游戏上。最后拿了冠军,那我就换种说法吧,我们队三个人加起来的投入时间绝对有10000+小时了。当然时间!=实力,训练的方法和效率都是很重要的。最后当然还要说的是要有爱,有爱才有投入,有爱才会坚持,而且爱不能光挂在嘴上,得付诸行动才行。

96 Responses to “ICPC World Finals – Arc顶点 Dream成真”
  1. icek says:

    虽然好像有点晚了,不过还是来膜拜一下shi哥

  2. jayi says:

    都楼上,是来看题解,仰慕大神的

  3. LALAqq says:

    额 ,今天来看下有没有放出月赛题解,也来膜拜膜拜大神。那天晚上看着视频看到了大神的激动时刻…..

    • watashi says:

      ……最近几天都忙着浙大自己集训的事,还有其他一些事
      解题报告也许写了一半不到,最近都还比较忙,估计要拖一段时间

  4. creepyuncle says:

    原来shi哥这么辛酸。。我一直以为zoj的admin是shi哥。。。

  5. Strayer says:

    恭喜夺冠…高中OIer路过…

  6. conghavefun says:

    请问watashi,看了ZOJ1015判断弦图的题,想请教在哪里有弦图的判断方法证明.

  7. AH says:

    ArcOfDream和东方有什么联系?

  8. Branimir says:

    Oh, congratulations on winning.
    What book would you recommend to start?

    哦,祝贺获奖。
    你会推荐什么书开始?

    ああ、勝利、おめでとうございます。
    何本には開始するためにお勧めですか?

    Ah, enhorabuena por ganar.
    ¿Qué libro recomendaría usted para empezar?

    • watashi says:

      我自己也没什么特别的推荐
      我开始看的只是一些数据结构教材和一些奇怪的书。我起步主要是通过当时的集训。黑书似乎可以,不过那是一本需要反复看的书。

  9. xiaoshua says:

    大神是不是得了世界冠军,无心再管理OJ和月赛了啊。。

    • watashi says:

      ZOJ名义上一直根本就不归我管,我在去年连修改主页和添加月赛的权限都没有,但事情确全是我在做,对于这件事我一直是非常恼火的
      至于这个月月赛取消,其实就是因为我本本挂掉了,然后也没人站出来,没人干活,自然就没有月赛
      ZOJ过去两年来就是这种情况,无数人挂着职务,日常维护都只是曾今有hhanger,现在只有我在做,前一段OJ的改进还是由从未有过职务的hsys做的
      我在两年前就退出ZOJ Staff了,去年开始结果月赛完全是我自己吃饱了撑的,吃力不讨好
      前几天我向chenyue姐姐提意见了,也开了个相关的会议,至于是能够真的有所改观还是就此死掉,我也不知道

      • xiaoshua says:

        哦,原来shi哥也有这么多辛酸事。。。 原来浙大也有那么多务虚名的人。。
        其实我只是想说,虽然全世界有那么多的大学及OJ,但是却很少有人像你这样每次组织月赛,并且挂出解题报告和代码,这种方式对像我这种初级学者帮助真的很大,很感激。 (尽管你的代码风格和我不怎么兼容……)
        另外,shi哥辛苦了,希望浙大那些挂着职务的人能有所觉醒吧·~~

  10. Z.Blade says:

    基本上每篇都离不开东方。博主真的超有爱。

  11. Peter.MAK says:

    敢问一下,做acm的诀窍是什么?

  12.  
Leave a Reply