Google kickstart Round A 2020

经过了上次G轮的比赛，发现kickstart很好，题目质量也很高，大数据的测试用例能够帮助我发现一些效率上的问题。所以打算将2020年过往轮次补一下。

ALLOCATION

有N个房子在卖，手里有一些资金，问最多可以买多少个房子。

第一题比较简单，贪心的思路做一个排序。

T = int(input())


for case in range(1, T+1):
    N, B = map(int, input().split())
    prices = map(int, input().split())
    ans, left = 0, B
    for p in sorted(prices):
        if p <= left:
            left -= p
            ans += 1
    print('Case #{}: {}'.format(case, ans))

Plates

有N堆盘子，每堆盘都有K个盘子，每个盘子有不同的价格。拿取盘子时只能拿上面的一叠。我想取出P个盘子，问能取的最大值是多少。

这道题是个dp，思路上很快想出来了，但是写法上卡了很久。

一开始的写法。

T = int(input())
for case in range(1, T+1):
    N, K, P = map(int, input().split())
    stack = []
    for _ in range(N):
        stack.append(list(map(int, input().split())))
    dp = [[0] * (P+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, P+1):
            cur = 0
            for k in range(j+1):
                dp[i][j] = max(dp[i][j], dp[i-1][j-k]+cur)
                cur += stack[i-1][k] if k < K else 0
    print('Case #{}: {}'.format(case, dp[-1][-1]))

T2没有跑过TLE了，是的，没有考虑每堆拿完的情况，于是修改如下。

T = int(input())
for case in range(1, T+1):
    N, K, P = map(int, input().split())
    stack = []
    for _ in range(N):
        stack.append(list(map(int, input().split())))
    dp = [[0] * (P+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, P+1):
            cur = 0
            for k in range(min(j, K)+1):
                dp[i][j] = max(dp[i][j], dp[i-1][j-k]+cur)
                cur += stack[i-1][k] if k < K else 0
    print('Case #{}: {}'.format(case, dp[-1][-1]))

结果还是超时，于是我自己试了一些大的数据集，用Pycharm的profile分析了一下，也没有找到性能的瓶颈。并且看起来和题解中给的时间复杂度完全符合O(N*P*K)。又进行了一些微调

for j in range(1, P+1):
    cur = 0
    dp[i][j] = dp[i-1][j]
    for k in range(1, min(j, K)+1):
        cur += stack[i-1][k-1]
        dp[i][j] = max(dp[i][j], dp[i-1][j-k]+cur)

依然超时。。最后试了一下这样写，居然通过了。

T = int(input())
for case in range(1, T+1):
    N, K, P = map(int, input().split())
    stack = []
    for _ in range(N):
        stack.append(list(map(int, input().split())))
    dp = [[0] * (P+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, P+1):
            cur = 0
            it = iter(stack[i-1])
            dp[i][j] = dp[i-1][j]
            for k in range(1, min(j, K)+1):
                cur += next(it)
                dp[i][j] = max(dp[i][j], dp[i-1][j-k]+cur)
    print('Case #{}: {}'.format(case, dp[-1][-1]))

然后，经过几次不断的试验和对比，我发现了同样的代码得到了通过和超时两种不同的结果。想必是代码的运行时间卡在了超时的临界值导致的。

不过第一版的版本经过多次提交还是TLE，个人认为iter的迭代并没有提升性能，结果存在偶然性。

最后通过的代码：

import random
T = int(input())


for case in range(1, T+1):
    N, K, P = map(int, input().split())
    stack = []
    for _ in range(N):
        stack.append(list(map(int, input().split())))
    dp = [[0] * (P+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, P+1):
            cur = 0
            it = iter(stack[i-1])
            dp[i][j] = dp[i-1][j]
            for k in range(1, min(j, K)+1):
                cur += next(it)
                dp[i][j] = max(dp[i][j], dp[i-1][j-k]+cur)
    print('Case #{}: {}'.format(case, dp[-1][-1]))

更好的写法：

T = int(input())
for case in range(1, T+1):
    N, K, P = map(int, input().split())
    dp = [0] * (P + 1)
    for _ in range(N):
        a = map(int, input().split())
        new_dp = dp[:]
        s = 0
        for j, x in enumerate(a):
            s += x
            for k in range(P-j-1, -1, -1):
                new_dp[k+j+1] = max(new_dp[k+j+1], dp[k]+s)
        dp = new_dp
    print('Case #{}: {}'.format(case, dp[-1]))

今天闲来无事，将第二次没过的代码改了一下，用python2来写的，主要是为了能用PyPy解释器。结果。居然过掉了，难道以后因为这个要写python2了吗、

WorkOut

有个人指定了一系列的健身计划，健身计划的组数是递增的，一组健身计划的难度是最大的组间差。可以向原有计划中添加K次训练，使得难度变小。给你这样一组计划和K，问最小可以使难度降到多少？

方法一：我一开始想错了，用的贪心的思路和堆来做。其实是不对的，比如2,12之间，[2, 5, 8, 12]是小于[2, 4, 7, 12]的。此题用二分法。通过最小最大的难度，找到一个合适的，使得，所有组件差满足改难度后，需要添加的组数刚好小于等于K。

def check(d, K):
    need = 0
    for i in range(1, N):
        need += (sessions[i]-sessions[i-1]-1) // d
        if need > K:
            return False
    return need <= K


for case in range(1, int(input())+1):
    N, K = map(int, input().split())
    sessions = list(map(int, input().split()))
    lo, hi = 1, sessions[-1]-sessions[0]
    while lo < hi:
        mid = (lo + hi) >> 1
        if check(mid, K):
            hi = mid
        else:
            lo = mid + 1

    print_ans(case, lo)