上个月报名的Google Code Jam，原本我以为第一轮的比赛是7月26才会进行的，想不到这 两天上网才发现在台湾时间7月17日早上七点到7月18日早上七点有举行一次资格考，必须 要在这24小时之内，完成三道题目，并且在时间内上传到Google，当然，还包括原始码， 每个题目都包括小输入和大输入两个部份，完成小输入可以获得5 分，完成大输入可以获 得20分，要通过资格考的成绩是25分。 小输入可以上传不限次数（不过失败的纪录会被记录下来），在下载完小输入之後，必须 在四分钟内执行程式，获得输出之後把输出的档案和原始码上传，如果超过时间就算失败 。每次的失败，都会让小输入重新产生，所以每次所下载的小输入都会不一样，上传的结 果会马上知道。 而大输入就不一样了，大输入的输入值不但比小输入既多且长。也许还会藏一些小输入没 有的陷阱也说不一定，而且大输入上传的结果不会马上知道，而要等到比赛结束之後， Google才会去检查大输入的上传是否正确，当然，他也会验证你所上传的程式码是不是真 的能够产生出这样的输出值。 里面的题目其实都不太简单，原来连资格考的题目都这麽靠北了，那第一轮的题目可不是 更难吗？ 而且我在完全没有心理准备的状况下，我本来想要用.net来作题目的，结果因为种种原因 ，我没有办法及时在我的电脑上安装Visual Studio（最近才换成Ubuntu），只好改换 Eclipse来写Java，但是想一想最後我还是用PHP来完成的，PHP这种松散结构的语法在 处理这种需要短时间完成的问题时非常有威力，非常快。 如果我要是用.net或是Java，恐怕花在定义类别和资料结构上所花的时间，就会耗掉我半 条命吧。 最後我只解出来两题，但是大输入的结果目前都是对的，理论上有50分，前面两题都算 是我比较擅长的演算法题，一题考「可预知未来的最短路径」（我是指它的精神，实际 的出题内容不是这样子），另外一题则是两点的排程问题，这两题都我比较擅长的演算 法，但是第三题是几何题，计算苍蝇拍打中苍蝇的机率，这对我来说实在是太难了，我 现在的几核能力退化到我连圆面积的计算公式都要靠Google来帮我找。 看到榜上前几名的一堆强者，半小时内就搞定了第一题和第二题，第三题虽然比较久，但 是还是在一个多小时之内疚可以完成，我实在太佩服了，我第一题花了3个小时，第二题 则花了4个小时，合计做完题目的时候已经花了10个小时了（我九点多才开始解） 由於第三题完全没有头绪，所以只好放弃了。原来写程式也有在考几何学的，偏篇几何就 不是我擅长的项目。 不过看到这些高手，我觉得我的第一轮还是当作磨练好了。 谈一下第一题的题目吧，我想大部分的人都应该解得出来第一题，我是用比较蠢的暴力 破解法，把每个搜寻引擎都丢进Query里面试，哪一个能连续处理的Query最多，就用那 个当作是选择的Search Engine，然後看能处理到第几个才会遇到不能处理的Query， 就换其他的搜寻引擎重复这样的过程一次，并把$n++，等全部的Query处理完，就知道 总共要切换几次。 是计算两个点兼第二题稍微难一点，是计算两个车站间班次表，两个站点必须在一天 内最少准备多少火车，才能满足所有的班次发车都不延误，火车到了以後必须等待 一个转换时间（0-60分钟，大样本，0-5分钟，小样本）才能再发车，0表示马上就 可以发车，一台车可以在两地之间来回多次，这一点就使得在考虑的时候必须同时 考虑A地跟B地的状况，我原本只是单纯的比较depA（从A出发的时间） 跟ariA（ 到达A地的时间，即B站班表中的到达时间)，结果上传了三次都是错的，才知道这 一点会有很大的影响，於是只好改用模拟的方式，计算每个时间点各站的状况。 我建立了一组资料结构： $schedule = array( $time => array( 0 => array( "TYPE" => ["DEP"|"ARI"], "PLACE" => ["A"|"B"]) ) ) 来纪录每个时间点发生的事情，比如： $schedule = array( '07:10' => array( 0 => array( "TYPE" => "ARI", "PLACE" => "A"), 1 => array( "TYPE" => "DEP", "PLACE" => "A"), 2 => array( "TYPE" => "DEP", "PLACE" => "B") ) ) 就是说在07:10的时候有一台火车到达A地，有一台火车从B地出发，有 一台火车从A地出发。而ARI的顺序一定在DEP之前，因为当T=0的时候， 火车可以到达後马上出发，如果不先纪录到达，就会发生错误。 接下来再用两个资料结构： $trainAvail = array("A"=> string, "B"=> string)在A站或是B站可以 发车的火车时间，这是火车到达时间+T，当有火车到达的时候就写进这个 资料结构，当有火车离开的时候先检查这个资料结构理面试不是有小於发车 时间的火车，如果有，把这个资料元素从资料结构移除。如果没有，则修改 另外一个资料结构： $trainCount = array("A"=> int, "B"=> int)，把从A地或B地出发的火车 +1，表示站内没有可以发车的火车，必须多准备一台火车。 把我有的时间点跑玩之後，$trainCount就是答案。 第三题的话就真的难倒我了，我知道方向，也知道是计算洞（苍蝇可以闪过 拍子的面积/拍子的面积），但怎麽去计算边缘的那些不完整的方形.... 完全不知道，就请高手解答罗。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 123.204.5.99