如何解决“超出CPU限制”的问题？

Question

我正在试图解决"Aaj Kemon Bodh Korcho" problem on Toph：

There is a match between Barcelona and Real Madrid. [...] There is a GOAL in each and every second of the match. All the goals may not be valid i.e. some of the goals can be done from OFF SIDE which is out of the rules.

[Output] “Aaj Kemon Bodh Korcho” (without quotes) if Barcelona won the match, “Hala Madrid” (without quotes) if Real Madrid won the match or “Meh :\” (without quotes) if there is no winner.

[...] The goals that are done from OFF SIDE are belongs (sic) to a famous series [...]:

0, 1, 1, 2, 3, 5, 8 …, …, …, …, …, n^th term

Input

You’re given an integer number T which denotes the number of test cases (T <=100). In (sic) each of the T line contains a string (S) of following characters (B, M). The maximum length of the string will not be greater than 10⁵. Note that, the starting index will be 0.

Here,
If the i^th character is B then it denotes a goal is done by Barcelona at i^th second.
If the i^th character is M then it denotes a goal is done by Real Madrid at i^th second.

Output

For each of the T lines you have to print the case number first according to the format Case #X where X is the case number. Then you have to print Aaj Kemon Bodh Korcho if Barcelona won the match or Hala Madrid if Real Madrid won the match. Otherwise print Meh :\ . For more clarification see the samples below.

Sample

Input   Output

2
BBMMMM  Case #1: Hala Madrid
MMBBBB  Case #2: Aaj Kemon Bodh Korcho

这是我的密码：

f=[0,1]
num_of_testcase = int(input())
store_2 = []
for i in range(num_of_testcase):
    numbers = input()
    store_1 = list(numbers)
    for x in range(len(store_1)):
        f.append(f[x]+f[x+1])
    f = sorted(set(f), key=f.index)
    for y in f:
        try:
            del store_1[y]
        except:
            store_2.append(store_1)
    if store_1.count("B") > store_1.count("M"):
        print("Case #" + str(int(i+1)) + ":" + " Aaj Kemon Bodh Korcho")
    elif store_1.count("B") < store_1.count("M"):
        print("Case #" + str(int(i+1)) + ":" + " Hala Madrid")
    else:
        print("Case #" + str(int(i+1)) + ":" + " Meh :\\")

当我提交代码时，它显示在第二个测试用例中超过了CPU时间。如何使代码运行得更快

Answer 1

有几件事会减慢代码的速度：

• 从0开始使用x，以复制您已经为上一个测试用例生成的相同斐波那契数。你应该只生成那些你还没有的
• 由于上一点，您需要通过应用set来消除重复项，然后必须对该集进行排序。如果只生成唯一的斐波那契数，则不必执行这些操作
• del不是一个常数时间操作。您根本不需要删除列表元素。你真正需要做的就是数数
• 在一个测试用例中，您可能会调用count方法四次，而它应该足够只执行一次计数

您可以保存更多信息：

• 实际上，不要将斐波那契数存储在列表中，只需将最后两个值保留在内存中，并在索引达到当前斐波那契数时生成下一个值
• 保持一个平衡，当马德里得分更多时，它将变为正，当巴塞罗那得分更多时，它将变为负

下面是它的样子：

num_of_testcase = int(input())
for i in range(num_of_testcase):
    goals = input()
    balance = 0
    # Fibonacci pair
    a = 3
    b = 5
    # Don't bother looking at index 0-3: they are to be ignored
    for j in range(4, len(goals)):
        if j < b:
            balance += 1 if goals[j] == "M" else -1
        else:
            a, b = b, a+b # Up to next Fibonacci number
    if balance < 0:
        print("Case #{}: Aaj Kemon Bodh Korcho".format(i+1))
    elif balance > 0:
        print("Case #{}: Hala Madrid".format(i+1))
    else:
        print("Case #{}: Meh :\\".format(i+1))

Answer 2

在您的程序中，有一行del store_1[y]。这是根据here的O（n）操作。因此，您的代码在O中工作（n²）。这就是为什么超过了CPU时间的原因

维护2个计数器b=0和m=0。遍历给定的字符串并查找给定的索引是否是集合的一部分，如果是，则不执行任何操作。否则请检查它是B还是M。相应地，增加计数器，最后进行必要的检查

此外，您可以实际生成一次斐波那契数列，并在测试用例中反复使用结果，而不是多次生成斐波那契数列