最近好多天都没更新，其实是跑去做比赛啦：20/20 Hack July

（又）是qoshi同学推荐的比赛，本来也想偷懒水水过去，但稍微做了下后发现还挺好玩。。。然后由于这比赛竟然持续9天，到后面就完全陷在里面无法自拔了。。。

hackerrank这个网站貌似是几个印度人办的，刚开张没多久的样子，不过界面做得好漂亮，很多设计也非常人性化，虽然BUG也不少，但总体来说在这里做题还是很享受的。

这次的20/20 Hack July比赛应该是类似月赛的形式吧，虽然不似codeforces、topcoder那么知名，但却也有不少神牛的（比如winger，09年ICPC世界冠军）。赛制是9天7题，包括5题算法题和2题GAME。其中算法题是按case给分的，没有罚时，没有提交惩罚。GAME则是提交AI程序，具体的内容包括两种，一种是单人，一种有对手的。

前3题都是比较简单的，第一题是输入一串字符，要求判断是否能构成对称字符串；第二题是输入一串字符，问总共能构成多少种对称字符串；第三题是问2^n的前k和后k个数字是多少，用了long double和2分后也是一下就过了。

第4题Computer Game则卡了3天。题意是输入n和两个int数组a[n]和b[n]，其中a[i]和b[j]间有边当且仅当它们非互质。问a[i]和b[j]两两配对，最多能有多少对？

这是一题典型的最大二分匹配。一开始我是建了一张大图，即边表里直接存a[i]到b[j]的边，过了几组小数据，后面都是超内存了（稠图的情况）。这个时候，Arios（又）来拯救我了……被告知可以考虑建两个边表，第一个存的是a[i]到p[k]，第二个存p[k]到b[j]，其中p[k]是某个素数。这样内存的问题解决了，开始TLE了。那几天里想了很多优化（大多没有用），又看了其他一些二分图匹配算法（也没比匈牙利好），也随便记录下吧就当是愚蠢的见证。。。说说最主要的优化点，其实就在于每轮匈牙利时，遍历边表时，由于边表是两重的，是可以从之前遍历到的位置开始继续遍历的，例如a[n]={2,4,7},b[n]={8,6,10}，a[0]、a[1]都通过p[0]=2与b[0]、b[1]、b[2]相连，在迭代的过程中，如果a[0]时已经遍历到了b[1]，那么到a[1]时直接检查b[2]就可以了，前面的元素都是已经在父迭代里遍历过的，这样可以将遍历复杂度降到O(9*N)，这个9是因为每个int最多有9个不同的素因子。另外就是再开了一个表，用来记录某素因子对应的第一个还没匹配的b[j]，每轮匈牙利时先尝试O（1）地匹配尚未匹配的元素。

另外还加了一堆稀里糊涂的scanf(“%d”)改getchar()，递归改非递归，按b[i]素因子个数小到大建表等等……也不知到哪个有用哪个没用，程序也写得一团遭，但总算是过了……这题最后就17个人拿了满分，应该也算本场最难的一题了吧。

第5题，这题我纯粹是利用规则漏洞了。主要是题目重复提交竟然不罚分，a、b的范围太小，时间复杂度卡得也不紧，直接O(lgN)试出test case然后O(9*10^10)离线算出结果就过了。Arios这题推出了数学解法，再次OTL一下。。。

第6题，单人GAME，这题大家分数都差不多了。

第7题Ultimate Tic Tac Toe，我觉得是本场最好玩的一题了。正如其名“最终井字棋”，它的棋盘分为大井字和小井字，大井字里每格是一个小井字，每个小井字的胜负判定和原本的井字棋相同，大井字根据小井字的结果来判断胜负，也即某方赢了某格小井字棋，就相当与在大井字里走了一步。这里有个先后手间的制约：先手如果走的是某个小井字的i,j位置，那么后手需要在第i,j个小井字里走；但如果第i,j个小井字胜负已定，那么后手可以选大井字中的任意位置。最后的胜负由大井字的结果决定。

规则还是很简单的……但要写出百战百胜的AI，也不是一件容易的事……根据Arios的说法，这种称为“博弈搜索”，即根据既定的盘面评估出自己最优的走法，然后分析对手最优走法以作修正，依次迭代迭代直到一定深度。

最后几天其实大家都已经拿完前面所有分了，因此排名也就全看这一题了。这题我的评分策略应该还是不准确，总是有几个人让我保持全败记录（winger貌似对所有人都轻松全胜…）。期间也出现过一些低级错误（交错语言直接扣4分啦，程序各种TLE判负啦）……最后排名第9，也还算过得去吧。

然后就是最后的global leaderboard了，虽然只是很小规模的比赛，但还是做得很开心。。。希望这次能收到T-shirt吧。。。