周赛 Weekly Contest 410

https://leetcode.cn/contest/weekly-contest-411/

3248. Snake in Matrix

class Solution:
    def finalPositionOfSnake(self, n: int, commands: List[str]) -> int:
        i, j = 0, 0
        operations = {
            "RIGHT": [0, 1],
            "DOWN": [1, 0],
            "LEFT": [0, -1],
            "UP": [-1, 0]
        }
        for c in commands:
            ops = operations[c]
            i += ops[0]
            j += ops[1]
        return (i * n) + j
            

3249. Count the Number of Good Nodes

WA

class Solution:
    def countGoodNodes(self, edges: List[List[int]]) -> int:
        d = dict()
        for e in edges:
            if e[0] not in d:
                d[e[0]] = [e[1]]
            else:
                d[e[0]].append(e[1])
            if e[1] not in d:
                d[e[1]] = [e[0]]
            else:
                d[e[1]].append(e[0])
        print(d)
        @cache
        def getNodeDeep(preNode, nodeI):
            l = 0
            if nodeI in d:
                for j in d[nodeI]:
                    if j == preNode:
                        continue
                    else:
                        # judge
                        l += getNodeDeep(nodeI, j)
            return l 

        ans = 0
        for i in range(len(edges)+1):
            isGood = True
            if i not in d:
                isGood = True
            else:
                rNodes = d[i]
                cnt = -1
                print(i, cnt)
                for j in range(len(rNodes)):
                    print(i, j, rNodes, getNodeDeep(i, rNodes[j]))
                    if rNodes[j] == i:
                        continue
                    elif cnt == -1:
                        cnt = getNodeDeep(i, rNodes[j])
                    elif cnt != getNodeDeep(i, rNodes[j]):
                        isGood = False
                        break
            if isGood:
                print(i, isGood)
                ans += 1
        return ans

3250. Find the Count of Monotonic Pairs I

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        # i, j, k
        # lessI = 0
        # mx = max(nums)
        # if nums[0] != mx:
        irMx = nums[-1]
        jlMx = nums[0]
        mxIs = []
        cMx = 0
        for j in range(len(nums)-1, -1, -1):
            mxIs.append(max(cMx, nums[j]))
        mxIs = mxIs[::-1]
        # print(mxIs)
        @cache
        def dp(i, j, k):
            if k > len(nums) - 1:
                return 1
            res = 0
            if i > nums[k]:
                return 0
            for i2 in range(i, nums[k] - j +1, 1):
                if nums[k] - i2 > j:
                    continue
                elif i2 > mxIs[k]:
                    break
                elif k < len(nums) - 1 and nums[k + 1] < i2:
                    continue
                elif irMx < i:
                    # print("skip")
                    break
                elif k == len(nums) -1:
                    res += 1
                else:
                    res += dp(i2, nums[k] - i2, k + 1)
            return res
        res = 0
        for i2 in range(min(nums[0] + 1, irMx+1)):
            # print(i2, irMx)
            if i2 > mxIs[0]:
                break
            else:
                res += dp(i2, nums[0] - i2, 1)
        return res % (10**9 + 7)

3251. Find the Count of Monotonic Pairs II

TLE

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        # i, j, k
        # lessI = 0
        # mx = max(nums)
        # if nums[0] != mx:
        irMx = nums[-1]
        jlMx = nums[0]
        mxIs = []
        cMx = 0
        for j in range(len(nums)-1, -1, -1):
            mxIs.append(max(cMx, nums[j]))
        mxIs = mxIs[::-1]
        # print(mxIs)
        @cache
        def dp(i, j, k):
            if k > len(nums) - 1:
                return 1
            res = 0
            if i > nums[k]:
                return 0
            for i2 in range(i, nums[k] - j +1, 1):
                if nums[k] - i2 > j:
                    continue
                elif i2 > mxIs[k]:
                    break
                elif k < len(nums) - 1 and nums[k + 1] < i2:
                    continue
                elif irMx < i:
                    # print("skip")
                    break
                elif k == len(nums) -1:
                    res += 1
                else:
                    res += dp(i2, nums[k] - i2, k + 1)
            return res
        res = 0
        for i2 in range(min(nums[0] + 1, irMx+1)):
            # print(i2, irMx)
            if i2 > mxIs[0]:
                break
            else:
                res += dp(i2, nums[0] - i2, 1)
        return res % (10**9 + 7)