Topcoder SRM使用Python解题需谨慎

喜欢做Topcoder Single Round Match的Pythoners可能已经发现,Topcoder Arena已经允许参赛者使用Python完成SRM的题目了。

然而,在享受用Python做题带来的快乐感受时,有一点可能需要引起Pythoner们注意:

并非所有的SRM题目都保证一定可以用Python来完成,这很大程度上要归咎于Python竞赛引擎的效率问题。

在算法时间复杂度一定的前提下,使用C/C++甚至Java实现的程序执行效率要优于Python。

因此,在完成SRM的题目时,如果对于时间复杂度的要求较高时使用Python需谨慎,此时转而使用C++或者Java来完成或许是更好的选择。

笔者在参加SRM606时,尝试使用Python解答div2的500分题目,代码如下,在challenge阶段被同房间的选手挑战成功了。

系统测试完毕后,通过观察Divion Summary,笔者惊讶的发现使用Python解答500pts的选手中竟无一人通过系统测试,下面是div2 500pts的题目描述及解答:

Marco has a string S composed of lowercase letters. You are to reconstruct S from the given String[]s S1 and S2 as follows:
Concatenate in order all elements of S1 to make a string A.
Concatenate in order all elements of S2 to make a string B.
Finally, concatenate A and B to get S.
Return the number of palindromic substrings in S.

import math,string,itertools,fractions,heapq,collections,re,array,bisect,random

class EllysNumberGuessing:
  def isValid(self, num):
    return num >= 1 and num <= 10 ** 9
  def addCnt(self, cnt_dict, key):
    cnt = cnt_dict.get(key)
    if cnt is None:
      cnt = 0
    cnt_dict[key] = cnt + 1
  def getCnt(self, cnt_dict, key):
    cnt = cnt_dict.get(key)
    if cnt is None:
      cnt = 0
    return cnt
  def cntList(self, cnt_dict):
    cnt_list = []
    for key in cnt_dict:
      cnt_list.append((key,cnt_dict[key]))
    cnt_list = sorted(cnt_list, key = lambda k: k[1], reverse=True)
    return cnt_list
  def getNumber(self, guesses, answers):
    pairs = zip(guesses, answers)
    #print pairs
    cnt_dict = dict()
    suspect = None
    for pair in pairs:
      if self.isValid(pair[0] + pair[1]) or self.isValid(pair[0] - pair[1]):
        if self.isValid(pair[0] + pair[1]) and self.isValid(pair[0] - pair[1]):
          self.addCnt(cnt_dict,pair[0] + pair[1])
          self.addCnt(cnt_dict,pair[0] - pair[1])
          if suspect is not None and pair[0] + pair[1] != suspect and pair[0] - pair[1] != suspect:
            return -2
          cnt_list = self.cntList(cnt_dict)
          if len(cnt_list) > 1 and cnt_list[0][1] > cnt_list[1][1]:
            suspect = cnt_list[0][0]
          elif len(cnt_list) > 2 and cnt_list[1][1] == cnt_list[2][1]:
            return -2
        else:
          num = 0
          if self.isValid(pair[0] + pair[1]):
            num = pair[0] + pair[1]
          else:
            num = pair[0] - pair[1]
          self.addCnt(cnt_dict,num)
          cnt_list = self.cntList(cnt_dict)
          if suspect is None:
            if cnt_list[0][0] != num:
              return -2
            else:
              suspect = num
          elif suspect != num:
            return -2
      else:
        return -2
    cnt_list = self.cntList(cnt_dict)
    if len(cnt_dict) == 0:
      return -2
    if len(cnt_list) > 1 and cnt_list[0][1] == cnt_list[1][1]:
      return -1
    return cnt_list[0][0]
#Powered by KawigiEdit-pf 2.3.0!

本文链接:http://bookshadow.com/weblog/2014/02/15/topcoder-srm-python/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码