Leona+ Dream for future

Astar 2008 初赛

好久没做比赛了……Topcoder时间太晚，POJ速度太慢，sigh......

百度之星蛮好，同一个时区，题目也没那么BT，很适合我，嘿嘿……

5月初就报好名了，但是一直没练习，到了30号，不练习不行了，只好爬到POJ上去做简单题，顺便调试一下机器环境，毕竟很久没用过了。一晚上做了5题，感觉还不错，然后群里就有了这么一段对话：

“一晚上切了5题，状态恢复了……”
“你做的是A+B吧”
“估计是A*B。”

看来大家都很了解我么=.=

31号晚上，吃了晚饭过来看题。题目见内。

第一题很简单，O(n)搞定，不过为了保险，我还是检查了N遍才交的……

第二题一看是中文题，马上扔掉。做完了3、4之后再回头看，GBK的编码还是比较简单的，而且重点不在这里。不过那个DP有点恶心，假设了一个条件，然后就写了……反正过一个test case就有分，能拿几分是几分，嘿嘿

第三题也没什么想法，随便写了个暴力的骗分。群里两个人在讨论线段树，我听得完全莫名，唉，老了……感觉LJ同学说的变异RMQ可能是对的……不过来不及写了……

第四题么，二分答案+随机投点，也就随便骗点分吧……贴吧里的几个数据，我都没过=.=貌似是有很牛的数学解法的，不过当时头有点晕，也就懒得想了……

其实我是把重点放在第二场的，因为按Topcoder的惯例，越往后晋级的可能性越大，嘿嘿。

然后1号早早地吃了中饭，安安心心地等比赛开始……（貌似没人贴题目出来）

第一题，上手就是中文题，比较郁闷，还好题目简单……

第二题，纯几何题，俺数学不好，先跳过……然后发现第三题更难，只好做完四再回来做二，郁闷地不行，好久没碰几何了，公式都快忘了……都最后也没过sample，丢脸了=.=

第三题，看上去貌似是最小费用流，没有模板，交了个骗分的代码了事……

第四题，又是BT题，没什么想法，只好暴力了，速度写完之后，就开始抉择二和三的事了=.=

貌似第二场还没第一场做得好，郁闷了，这次astar悬了……

不过话说回来，复赛的时候我正好在黄果树，有没有时间比还不确定……今年的免费旅游不乐观啊=.=

百度之星决赛

到达宾馆的当天晚上就有试机时间，坐定之后我赫然发现桌面上有CS1.6和CS1.5的图标=.=，然后就在我开始找有哪些IDE和可用资源的时候，主持人说：接下来我们开始分组打CS吧。巨寒……然后我们就按分组打CS了，我所在的1组由于实力非常牛，轻轻松松割掉了对面的2组。玩的时候有几个其它的客人在WTommy后面讨论：“你说他们这是在干什么那”，“游戏比赛嘛”，“不对，门口的牌子上面写的是‘程序设计比赛’”，“哦，他们在编程打CS”……由下文看来，这段话印证了一条古语：旁观者清，当事者迷。

第二天早上，比赛正式开始，题目上写着：实现一个CS1.5的Bot。于是大家都明白了，第一天的比赛是有原因的……然后下载了一个压缩包，包括MinGW的编译器、一个make程序、Half Life和Podbot的SDK，压缩包有27M，其中可以修改Podbot中的两个文件，每个文件包含5个函数，用于T和CT的买枪、枪械瞄准、手雷瞄准和一个基于A*的寻路算法（只允许改其中的g、h函数）。玩过CS的人都知道，这5个函数并不能实现CS的常规策略。对T而言，最简单的策略是全部冲向一个雷区，由于CT要分守两边，以多打少的胜率会相当大，实现这个策略需要对那个寻路算法和CS的路点机制非常了解，在比赛时间内做到这一点基本不可能；对CT而言，面对T的冲击，需要队员之间的通讯才能更好地防守，而CS的通讯机制我基本没看懂=.=

比赛中没有提供任何的API文档和说明，程序框架只能自己看代码，核心代码至少有几千行，我研究了2小时左右发现看懂框架不是5小时能完成的任务，于是放弃，只找有用的API。而且测试起来非常麻烦，一个完整的测试过程是：先把源代码make成dll，然后覆盖掉原来的文件，启动CS，开一个新游戏，加bot，观察bot行为，结束之后完全关闭CS。基本上主要的时间不是用在写代码上，而是在看bot打架和开关CS上。

原始压缩包中的代码是可以通过编译并且正常运行的，只不过运行出来的bot比较傻，但是只要在代码上修改一个参数，就可以使bot在三枪之内杀死一个人（某些威力极小的枪除外），由于CS的对战原理，这样的bot在1v1的情况下，谁先开枪谁赢，而且根据CS对bot的控制，“谁先开枪”是随机的。另外，评测的三个地图中有两个是埋雷地图，由于CT近乎弱智的拆雷AI，导致了CT唯一的赢面是在T没埋雷之前把带雷包的T干掉，然后守雷包，而CT能不能和带雷包的T相遇，基本上也是随机的。综上，评测的结果带有很大的随机性，多运行几次测试结果就很有可能改变，换句话说，决赛是拼RP的比赛。

比赛过程中最不爽的一点是主持人在不停地讲解比赛规则和透露代码细节，使我不得不边写代码边竖起耳朵听，还不能去洗手间，生怕漏掉点什么。比赛规则显然是可以在赛前就公开的，没必要放在比赛过程中说，貌似比赛组织者认为比赛毫无秘密可言，各种细节可以被选手猜出来，从初赛开始，很多问题都无法在赛前获得定论，比如STL的使用问题。而在比赛过程中透露代码细节，更是莫名其妙，比赛一开始主持人就说：这次比赛，阅读代码的能力也是考察范围之一。但是之后又不断的透露关键代码内容，看上去潜台词就是“一定要按我的思路走”。

颁奖典礼被放在了第三天的晚上，冠军是来自SJTU的某同学，据说是复赛第50名=.=。颁奖典礼除了颁奖就没其它的了，连个决赛的录像都没，难道选择CS做为比赛平台不是为了演示？只是在典礼结束的时候应广大选手的要求重新模拟了几场比赛，而比赛的结果也证实了其不可预料性。

比赛之外的活动还是相当不错的，滑雪、高尔夫、游泳，虽然我一个都不会=.=。滑雪的教练不错，很详细地讲解了各种细节，基本上滑雪过程中没出什么大问题。高尔夫就比较挫了，电视里看别人打高尔夫是非常休闲的运动，我们一上去就变成了体力活，要么打空，要么打到地上，相当地累=.=。游泳就不提了，说是说XX海洋世界，本以为会像热带风暴那样，结果就是一个水池，玩的东西都没有=.=。

第三天的时候还去参观了百度公司，见到了老Boss李彦宏。我不常用百度的产品，也就没提出什么有新意的问题，不过百度在中国的人气是不言而喻的，Google在中国的市场一时半会还无法和百度抗衡，曾经听说有人上百度之前先要上Google搜百度的网址，然后再去用百度搜索。不过百度的外文搜索能力比较差，就我个人而言，经常要搜索一些英文资料，百度显然是不能胜任的，而且大多数专业都是英文文献比较多，所以百度要想占领高端市场的话，还是要加强外语的搜索能力。

总体而言，决赛的组织和安排工作做得很周全，看得出一些细节方面是经过研究的，只不过经常拖时间，有点印度的感觉=.=。明年争取继续进决赛，争取拿熊^_^

百度之星 2007 复赛

8小时的比赛，好BT……

第一题求一个交通系统中一点到另一点的最短路。先要求出任意两条线段的交点，然后求目标点到每条线段的最近点，然后用最短路算法求出答案。纯模板题，一共300行左右，自己写的大约只有40行不到，其它都是模板……

第二题求URL是否满足给定的规则。规则巨麻烦，题目中给出的说明不足以说明问题，于是管理员在贴吧上给出了更详细的说明，但还是不全面。跟着感觉做吧=.=

第三题给出N个人，每个人有一些属性，要求选出一些属性，使每个人的选出的属性值之和中最小值最大。咋看之下没啥想法，直接随机化解=.=

第四题求K个工程队修好N个公司的最小损失。有点像Topcoder Marathon LumberjackExam那场比赛的题目，不过时间不够了，而且给出的模拟器没有图形界面=.=，没有仔细优化，只有写了个可行解，拿几分算几分吧……

总体来说，第一题模板题、第二题英文阅读题、第三、四题marathon题，如果能保证前2题拿高分，进决赛应该没啥问题吧……希望能进，嘿嘿……

百度之星 2007 初赛

百度之星又来了，规则还是和以前一样恶心，中文题，只允许C和C++，不告之硬件环境和编译选项，不公布测试数据……最无语的是，热身练习的代码是不运行的，这样限制代码的运行时间就完全没有意义了，谁知道你的CPU是PII的还是双核的……

今天发现进了复赛，于是过来写报告，以免像去年那样，写完解题报告，发现没晋级=.=

我做的是第一场，第二场没时间做……

第一题暴力并查集，蛮简单的，数据规模也小，不过郁闷的是逻辑写错了一点，会把一部分“Yes”判成"No"，还好只错了3个Case。

第二题数学题，看完题目没有想法，然后发现Case有简单和困难之分，于是目标变成过前5个Case。然后发现只过了1个Case，回去看了一下代码，规则2的枚举里把一个"10"写成了"9"，郁闷=.=

第三题看上去像二分匹配，当时时间不够没有细想，时间快到的时候发现输出都是0和1，于是交了一个随机输出0和1和代码，果然一个Case都没过=.=

第四题是个分析SQL查询的题，不过由于WHERE子句里只有=和AND，所以只要找出所有的WHERE子句，然后联立即得查询条件。交了代码之后发现，由于写得匆忙，前半段用了scanf，后半段读整行用了istream，晕……最后只过了2个Case。

最终得分22分，不算高但还是进了复赛……

关注了几天的贴吧，发现部分参赛选手是初学者，类似ACM/ICPC的输入已经算是比较麻烦的了，还加入了中文，据说gets也不能用，输入的难度就一下子上去了……建议百度可以借鉴ICPC或者Topcoder的模式，赛前多给选手一些条件测试系统，题目里降低一些算法无关的复杂度，赛后公布一下数据或者至少说一下未通过的原因吧……

IPSC 2007

昨天从学校里回来之后，看到群里有人说IPSC是“今天下午”，顿时寒，完全忘记了这事，还好群里有提醒。然后去IPSC的网站看了一下，报名还没截止。本来想叫Ray和flyingdog一起做，但发现他们两个都不在线，于是注册了一个单人的帐号。顺便看了一下历史成绩，发现中国的高中生们真牛，从99年到06年，8次比赛拿了5次高中组冠军，不过总排名上还没有中国人拿冠军，悲哀=.=赛后ACRush说他是第4年第二了，汗……

比赛是8点开始，7点吃好饭发现Ray和flyingdog都在，于是把他们拉上一起比赛，还把队名改成了CSPI=.=。

一共12道题，由于题目名称事先公布了，看到F是关于Sudoku的，于是很感兴趣（因为我有Sudoku模板=.=）。比赛开始之后，我先看了F，flyingdog看B，Ray看L。F的确是求解Sudoku，但是三个Sudoku的联合求解，就是每个Sudoku之间有一些格子的值是一定要相等的，我一开始没法估计时间复杂度，就先放弃这道题，而且后来也一直没去做这题（赛后看了题解之后发现，easy input可以对每个Sudoku依次独立求解，真郁闷=.=）。Ray看了L之后发现是概率题，直接放弃。flyingdog看了B之后发现在英语阅读题，也放弃，汗……然后发现A和E已经有人过了，然后我看A，flyindog看E，Ray看了B。A是简单题，几分钟就写完过了，然后转向I。flyingdog看了E之后发现easy input可以手工做掉，而hard input需要图像识别……Ray发现B的easy input有规律，也可以做。flyingdog把E1过了之后失踪了一会，回来之后和我们说接到Google的面试通知，时间是今天早上9点，于是放弃了比赛，BS之=.=。然后没过多久，Ray也收到了面试通知，不过还好时间是下午的，还能继续比赛，Ray把B1过了之后就在研究B2，经过很长时间之后也过了。这时候我I已经基本搞定了，题意比较复杂，但是简化之后实际上是两次floyd_warshall，实现起来蛮简单的，而且没精度问题。然后把所有的题目扫了一遍，发现G1可以做，就做掉了，其它的题目都没什么想法。花了点时间看排名，发现排在第一的队叫“Moscow SU X13”，后面还跟了“(with coach)”，非常寒，巨牛的队啊……还有个队名叫“SnapDragon Fan Club”=.=，还看到“Save the cheerleader, save the world”=.=，都是很强的队。

之后的时间基本是垃圾时间了，很久没有连着几个小时做题了，有点不太习惯了。而且IPSC的赛制和ACM有一点点不一样。easy input有时候可以用暴力解掉，所以还要分析数据，不像ACM看完题就知道能不能做。

最后一共拿了11分，排在99名。05年的时候我做过一次IPSC，拿了4分排到2XX名，好怀念啊……不知道明年还有没有机会继续玩……

Topcoder Open 2007 Algorithm Round 2

又是1点的比赛，真累=.=

上手第一题就卡了，蛮简单的一道题，枚举就可以了，结果想了半天才想到，交了之后只剩下半小时了。然后打开第二题发现是动规=.=，立即放弃，不过证明了贪心是错的之后，challenge的时候顺利cha掉一个，嘿嘿。但是最后总分只有166T_T，如果再能cha对一题就能晋级了，唉，75刀啊……

challenge结束的时候，有人跑到我的房间里说，去Room 27看看，第一题全被cha了，好奇地跑到Room 27，场面真壮观，100多个人，都在仰慕Egor大牛的challenge水平，这个房间除Egor之外所有人的第一题都被cha了，很多人在问Egor有什么特殊的数据，后来Egor说是一个非法的数据，但是通过了系统的检查，自然是能cha掉所有人了。

但后来Egor同学的命运发生了戏剧性的变化。challenge结束的时候，Egor同学成功地cha了15个人，拿了50*15分，总分爬到第二名，仅落后于Petr。然后admin发现了系统有问题，修正了bug之后，Egor同学的challenge自然是失败的，那也就是说他拿到的50*15分不算，还要倒扣25*15分。最有意思是，sys test之后，Egor同学的第一题还挂了，没进前300名，也就是不能出线=.=

不过再后来有很多人为Egor打抱不平，说这是系统问题，如果Egor第一次cha的时候，系统就说它失败，那他就不会cha之后的几次，所以后面几次的失分不能算在他头上。这个争论一直持续了7个多小时，admin总算接受了这个方案。不过我到现在都没收到不能进下一轮的通知信，说明admin那里还有很多事情没有搞定。

Topcoder Open 2007 Marathon Round 1 to 3

显然我还没有领悟marathon的真谛。

第一轮的题目大意是，有一座山，可以表示在101*101的方阵中，每一个方格要么为空，要么为山体。选手可在任意为空的两点作一次测量（从一点发射一束光到另一点），系统返回接收到的光束的强度。由于打穿了山体，所以光强有衰减。又由于测量仪器的问题，测出的值带有随机误差。经过有限次测量后，选手需返回第一小块山体中所含重金属的密度（这种重金属就是导致光线衰减的原因）。

根据题意简化之后，实际上就是求解一个方程组，其中每个方程形如：

Topcoder Open 2007 Algorithm Round 1A

本来以为凌晨的比赛中国和东欧的选手会少一点，没想到注册完发现Petr和ACRush都在，我的排名是倒数的，郁闷了，无奈只有硬着头皮上了。

第一题一开始以为是贪心，敲完之后发现连sample都过不了，然后才发现贪心是错的，于是想到了二分答案，这种策略没用过几次，每次都不能一下子反应过来，再加上写得不太熟，浪费了很多时间，交了之后只有174分。

第二题乍看之下觉得比较复杂，后来发现只要枚举就可以了，不过我对矩阵一直很头痛，调试了很久才过sample，拿了283分。

两题之后已经50分钟过去了，看了下排名189，觉得晋级应该没问题了，第三题也没仔细研究。题目读了很长时间，发现貌似可以用搜索做掉，写了半天发现写错了=.=，于是放弃，开始想test case。

challenge的时候我们房间异常安静，没有人被cha掉，由于第一题太简单，第二题代码太复杂，我都没想出很好的test case，于是就去看总排名了。Petr真牛X，coding结束的时候落后ACRush10分，challege瞬间超过了ACRush 100多分=.=，于是跑到他的房间瞻仰一下，看到他房间挤了4X个人，都在看他的代码=.=

system test结束，2道题都过了，最终排名122，顺利晋级^_^