LeetCode Biweekly Contest 97の解法

問題ページはこちら。

2553. Separate the Digits in an Array

与えられた数値を１桁ずつ返す問題。

整数で与えられるので、文字列として解釈して１文字ずつ解を得ればOK。

class Solution:
    def separateDigits(self, nums: List[int]) -> List[int]:
        ans = []
        for num in nums:
            for char in str(num):
                ans.append(int(char))
        
        return ans

2554. Maximum Number of Integers to Choose From a Range I

小さい値から貪欲に取っていく。

bannedはリストで与えられるが、重複があるかもしれないのと、x in bannedは計算量がO(N)で遅いのでsetに直す。

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned = set(banned)
        
        ans = 0
        
        for i in range(1, n+1):
            if i in banned:
                continue
            
            if maxSum >= i:
                maxSum -= i
                ans += 1
            else:
                break
        
        return ans

2555. Maximize Win From Two Segments

ある範囲が与えられ、長さk以下の区間を2個選んだ時に得られる個数の最大値を答える問題。

左右から尺取法をしていって答えを求める。

[0, i]と[i+1, n]のそれぞれの最大値の和が最大になれば良い。

答えを求めるための最後のループは配列外参照に注意。

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        
        left = [0] * n
        left[0] = 1
        j = 0
        for i in range(1, n):
            while prizePositions[i] - prizePositions[j] > k:
                j += 1
            
            left[i] = max(left[i-1], i-j+1)
        
        right = [0] * n
        right[n-1] = 1
        j = n-1
        for i in range(n-2, -1, -1):
            while prizePositions[j] - prizePositions[i] > k:
                j -= 1
            
            right[i] = max(right[i+1], j-i+1)
        
        ans = 0
        for i in range(n):
            ans = max(ans, left[i] + (right[i+1] if i != n-1 else 0))
        
        return ans

左からの尺取でO(N）、右からの尺取でO(N)、答えを求める計算がO(N)かかるので、計算量はO(3N)=O(N)となる。

ここで、尺取を1回行うだけで解けないか考えてみる。

[left, right]が1つの候補に挙がる時、もう1つの候補は[0, left – 1]で得られる最大値を足せば良いことに気づく。

i番目までに得られる最大値をdp[i]とすると

尺取中の範囲[left, right]　＋　dp[left – 1]が答えになる。

0-indexで+1するかどうか注意しながら実装。

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        dp = [0] * (n + 1)

        ans = 0
        l = 0
        for r in range(n):
            while prizePositions[r] - prizePositions[l] > k: 
                l += 1

            dp[r + 1] = max(dp[r], r - l + 1)
            ans = max(ans, r - l + 1 + dp[l])

        return ans

O(N)1回分の計算量で解くことができた。

2556. Disconnect Path in a Binary Matrix by at Most One Flip

グラフの1箇所だけを通れなくして、ゴールまでたどり着けるかどうか判定する問題。

ゴールまでたどり着くには複数の経路があるはずだが、全ての経路で共通して通る1マスが存在しているかどうか見つければいい。

その1マスを通れなくすれば、全ての経路でゴールまでたどり着けなくなる。

前処理として、そもそもゴールまで到達可能かどうか調べる。

class Solution:
    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
        m = len(grid)
        n = len(grid[0])

        reachable = [[False] * n for _ in range(m)]
        reachable[0][0] = True
        for i in range(1, m):
            reachable[i][0] = reachable[i-1][0]
        for i in range(1, n):
            reachable[0][i] = reachable[0][i-1]

        for i in range(1, m):
            for j in range(1, n):
                if grid[i][j] == 1:
                    reachable[i][j] = reachable[i-1][j] or reachable[i][j-1]
        
        if not reachable[m-1][n-1]:
            return True

その後はBFSをしていく。

全てのマスで共通して通る1マスがあれば、キューにある座標が1個だけになるはずである。

ただし、スタートとゴールがキューにあると同じく個数が1個になるので注意する。

        visited = set()
        visited.add((0, 0))

        q = deque()
        q.append((0,0))
        
        while q:
            if len(q) == 1 and q[0] != (0,0) and q[0] != (m-1, n-1):
                return True
            
            for _ in range(len(q)):
                row, col = q.popleft()
                for i, j in [(1,0),(0,1)]:
                    if row + i == m or col + j == n:
                        continue
                    
                    if grid[row+i][col+j] == 1 and (row+i, col+j) not in visited:
                        q.append((row+i, col+j))
                        visited.add((row+i, col+j))
        
        return False

別解として、ゴールから逆算する方法を考える。

スタートからゴールに行けるということは、ゴールからスタートにも行けるはずである。

ここで、スタートから座標(i,j)に到達する経路の数をforward[i][j]、ゴールからの経路の数をbackward[i][j]、全ての経路の数をtotalとする。

BFSを使った解法と同じく、もし全ての経路が共通で通る1マスが存在する場合、total = forward[i][j] * backward[i][j]が成り立つことを利用する。

噛み砕いて考えると、A→Bに行く方法が2通り、B→Cに行く方法が3通りであれば、A→Cに行く方法は6通りになる、という計算と同じになる。

二次元配列で添字が増えるとややこしいが、アイデア自体は単純なはず。

class Solution:
    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
        m = len(grid)
        n = len(grid[0])
        
        forward = [[0] * n for _ in range(m)]
        forward[0][0] = 1
        for i in range(m):
            for j in range(n):
                if i > 0 and grid[i][j] == 1:
                    forward[i][j] += forward[i-1][j]
                if j > 0 and grid[i][j] == 1:
                    forward[i][j] += forward[i][j-1]
        
        backward = [[0] * n for _ in range(m)]
        backward[m-1][n-1] = 1
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if i < m-1 and grid[i][j] == 1:
                    backward[i][j] += backward[i+1][j]
                if j < n-1 and grid[i][j] == 1:
                    backward[i][j] += backward[i][j+1]
        
        total = forward[m-1][n-1]
        if total == 0:
            return True
        
        for i in range(m):
            for j in range(n):
                if forward[i][j] * backward[i][j] == total:
                    if (i,j) != (0,0) and (i,j) != (m-1,n-1):
                        return True
        
        return False