这次趁自己给自己放假的时间，参加了 Google Code Jam 比赛，那是一个程式设 计比赛，里面有全世界的怪物参加。 我那时候参加的动机是，想试试看自己有多少能耐，看看自己能走到哪一步，虽然 我大概知道自己是到不了後面的比赛的，但是还是想试试。 在他还没比赛之前，有开放几题的练习题给大家做，我做之後的感想是，这是数学 与演算法的比赛，演算法方面我还算 OK，可是针对 Dynamic Programming 方面，我看到 题目真的是没有什麽直觉可以快速组织出如何使用 DP 演算法，毕竟上次使用 DP 大概是 快五、六年以前，感觉似乎已经流失了许多，我看到许多可以使用 DP 的题目，但却没有 感觉如何写。所以比赛之前，我就猜到我应该会死在这一类的题目上面，因为有使用 DP 跟没使用 DP 而使用最笨的方法解题，无论在解题时间或是执行时间上面都是差很多的。 再来，我在练习题中，发现每三题之中一定会出一题以上的数学题目，像是求机率 ，求方程式...等等。 哎呀！ 我又知道了，我大概 95% 也会死在这种题目上，我以前在 数学上没有下太多功夫，所以会死在数学题目上是应该的，只能碰碰运气，看看能不能碰 到正好会的。 我稍微简单的介绍一下他进行的方式，给你三题，英文出题，题目会跟你讲输入资 料的格式是什麽，也会规定输出资料的格式。他的输入资料是给你下载的，其中又分小资 料集档案跟大资料集档案，小资料集档案一旦你开始下载，就开始计时，计时四分钟，你 必须把你所下载的档案内容用某种方式输入到你的程式中 ( 例如读档 )，然後输出他所 规定的格式的结果出来，放入一个档案中，然後上传你的输出档案与程式码。而大资料集 档案，是你下载之後，给你八分钟的时间，时间内也是一样，把结果与程式码上传。大资 料集跟小资料集，顾名思义，就是一个是资料量比较小，另外一个资料量比较大，资料量 比较小的让你可以先不用考虑最佳化，而资料量比较大的就一定要考虑最佳化，不然有机 会会没办法计算出结果。 但是我这次的经验是，一开始最好就要考虑最佳化，不然你大 概也没时间考虑了，第二个经验是，一定要先写好读写资料的程式框架，这样才可以节省 时间。 喔！对了，大资料集的正确性只有在比赛结束之後，你才会知道，而小资料集是在 你上传之後就会跟你说正确与否。 资格赛没多久就到了，他的时间给你 24hrs 来解三题，两题演算法、一题数学题 ，演算法都可以使用贪婪方式解决，可是数学题目是几何机率问题... @.@ 我一开始连 机率都有点忘记，还要去看图形，时间很快的过去，我解完了两题演算法题目，然後最後 一题数学题就在一头雾水中没做。不过资格赛只要你有做完任何一题的小资料集与大资料 集，且结果正确，就可以参加下次的比赛 Round 1。 很高兴，我成功的通过了资格赛，不过看到那题数学题，我大概就冷了一半，所以 我把志愿放在希望能走到 Round 2 就好了。 Round 1 要开始的那段期间，我正好也要考驾照，所以大部分的时间都花在练习开 车以及准备笔试上面，再加上早上跟晚上都有英文课程，所以那段期间没什麽在准备，不 过我知道，准备了也没用，这种东西临时抱佛是没什麽用的。 Round 1 分成三个时段，参赛者可以选择两个时段参加，也就是说，你有两次机会 ，第一次没成功，还有第二次，每个时段挑选 840 名参赛者出来。 我选择了礼拜六的早上跟礼拜日的晚上，也就是第一场跟最後一场，我个人认为， 个人认为啦，没精算过，第一场应该是最多人参加，但是可能题目会比较简单，而最後一 场，由於前面两场把精英都挑走了，所以第三场应该是最有机会晋级的，为什麽我会强调 个人认为呢？因为我发现国外论坛也有讨论参加哪场是最好的，还有人开始在上面用机率 来精算，有个人看到了大家开始拿数学公式狂讨论机率，就发表了「大家果然都是数学的 狂热分子，大家加油吧！」，唉，我看到却是心凉了一半。 Round 1 A 终於来临了，第一题是个送分题，两个向量相乘，要怎麽排列才能算出 最小的乘积，这题很简单，题目我也看懂了，但是在做的时候，不知道哪根筋不对，人家 明明说两个向量的数量相同，我却到後面在思考数量不同的情况，最後才突然想到不需要 考虑这个，浪费了许多时间。第二题题目英文对我来说有点艰难，我在题目看不太懂的情 况下，没办法写出演算法，因为有一个地方我一直没弄懂他题目的意思，而这个会影响到 最後结果。当然，最後我就在这种情况下，只解完了第一题，然後第一轮失败。 在 Round 1A 结束後，我研究了别人的解法，才了解题目的意思， 「The minimum possible number of batches are malted. 」 意思是加麦芽口味的数量要最小 化，而我当时以为他的意思是 「加麦芽口味的当成最小值」，差很多，所以当然解不出 来。 再来， Round 1B 是礼拜六晚上开始，不过我没参加，但是我还是跑上去看了题目 ，顺便试做，然後我还挺庆幸我没参加 Round 1B 的。 因为，第一题最少分的就是一个 类数学题，而且最重要的是，我题目也有一点看不太懂，我事後来看整个三轮的正确率， 也是 Round 1B 的正确率最低，这一轮打击了我不少自信。 Round 1C 在礼拜日晚上五点，终於到了，第一题计算手机按键上面的字母如何配 置可以让按的数量最小，这题虽然挺简单，但是我还是花了 30 分钟，而最快的人只花了 5 分钟...第二题是计算 Ugly Number，老实说，我看到这题我大概猜的出来是要使用 DP，但是我实在没什麽感觉要如何使用，最後只好用暴力解法，只是暴力解法就是又花 时间又慢，而且我中途还一度脑袋打结，最後，没在时间内完成，而我进入 Round 2 的 希望也破灭了。 不过我最後还是把那题用暴力法写完，大概是因为不甘心吧，只是暴力法只能解小 资料集，碰到大资料集大概就无能为力了。 比赛对我来说已经结束了，老实说心中有一些沮丧，不过也感觉理应如此，因为演 算法跟数学对我来说，一个是很久没碰 (在公司里面顶多用用简单的演算法，而不会用 DP )，一个是更久没碰而且也没强过。 而 Google 的比赛比较像是数学家的比赛，感觉 跟 ACM 、 TopCoder 很像。 如果我还想参加的话，我大概要把以前没拥有过的数学认识非常多下，然後狂做 ACM 跟 TopCoder 的题目，把演算法的那种直觉抓住。就我的感觉，这种比赛是可以训 练以及准备的，训练的方式就是一直做题目，然後数学也一直做，而参加这种比赛最好的 时机就是你在当学生的时候。出去工作之後，东西很容易在一不小心的情况下流失。 不过 也许这只是我的藉口吧！ 这种比赛精英真的很多，这次我还特别选了优势比 C++ 大的 Ruby 来做，不过我 看到上面高手大部分是使用 C、C++、Java，所以我输也没什麽藉口，只能说实力就是这 样。 不过这次在上面也看到一些很有趣的现象，还有人用 SQL 来解题，也发现有人每一 题都用不同的语言来解，可能是想跟别人与众不同吧！ 在参加比赛还能有这种闲情逸致 ，真的是高手。不过也可能是这种比赛大部分都是演算法正确就没问题，所以重点不在语 言上面。 但是我觉得语言还是有优势存在，因为我使用 Ruby 就不太需要担心大数的问 题，可以专心在演算法上面。 比赛对我来说虽然结束了，心中也有一些失落，但是也激起了我想要把数学搞懂以 及想要做题目的慾望，我要大喊！ 「Google Code Jam! 我明年一定要进入 Round 2!!」 XDrz --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 202.151.55.252 ※ 编辑: redray 来自: 202.151.55.252 (07/28 23:39)