ZeroJudge 解題筆記：r579.10365 - Blocks

作者：王一哲
日期：2026年9月7日


ZeroJudge 題目連結：r579.10365 - Blocks

解題想法

這題用窮舉法，但是要縮小測試的範圍，如果數量為 $n$，當長方體 $3$ 個邊長越接近時表面積越小，假設邊長為 $a, b, c$ 且 $a \leq b \leq c$，則 $a$ 的上限 $amax = \sqrt[3]{n} + 1$，第一層 for 迴圈跑 $a = 1$ 到 $a = amax$，如果 $a$ 不能整除 $n$ 就跑過；邊長 $b$ 的上限 $bmax = \sqrt{n/a}$，第二層 for 迴圈跑 $b = a$ 到 $b = bmax$，如果 $b$ 能夠整除 $n/a$，則 $c = n / (a \times b)$，表面積 $area = 2 \times (a \times b + b \times c + c \times a)$，更新答案 $ans$ 為新的最小值。

Python 程式碼

使用時間約為 21 ms，記憶體約為 9.4 MB，通過測試。

m = int(input())
for _ in range(m):
    n = int(input())
    ans = float('inf')  # 答案
    amax = int(n**(1/3))  # a 的上限為 n 開 3 次根號
    for a in range(1, amax + 2):  # 測試 a = 1 ~ amax + 1
        if n % a != 0: continue  # 不能整除，跳過
        bmax = int((n // a)**(1/2))  # b 的上限為 n/a 開根號
        for b in range(a, bmax + 1):  # 測試 a ~ bmax
            if (n // a) % b == 0:  # b 可以整除 n/a
                c = n // (a * b)  # c 的值
                ans = min(ans, 2 * (a*b + b*c + c*a))
    print(ans)

LeetCode 解題筆記：940. Distinct Subsequences II

作者：王一哲
日期：2026年9月7日


LeetCode 題目連結：940. Distinct Subsequences II

解題想法

困難題。題目給一個字串 $s$，要找出 $s$ 可以組合成幾個不重複的子字串，由於答案可能很大，要對 $10^9 + 7$ 取餘數。這題要用動態規畫解題，定義一個長度為 $26$ 的陣列 $dp$，$dp[i]$ 代表以第 $i$ 個字母結尾的子字串數量，依序從 $s$ 讀取字母 $c$，先取 $c$ 的索引值 $idx = ord(c) - ord('a')$，可以將 $c$ 接在原有的子字串後面或是自己獨立成新的子字串，因此更新方式為 $$ newdp[idx] = \left ( \sum_{i = 0}^{25} dp[i] \right ) + 1 \pmod{MOD} $$ 但是這樣的寫法每次更新時都要重新計算 $dp$ 的加總，速度不快。另外定義一個變數 $total$ 用來記錄 $dp$ 的加總，每次更新 $dp[idx]$ 時將 $dp[idx]$ 的值存到另一個變數 $prev$，更新方式改為 $$ dp[idx] = (total + 1) \pmod{MOD} $$ 接下來更新 $total$ $$ total = (total + dp[idx] - prev) \pmod{MOD} $$ 如果用 C 或 C++ 解題，為了避免在上一行相加時溢位以及相減時變成負數，要改成 $$ total = ((total + dp[idx]) \pmod{MOD} - prev + MOD) \pmod{MOD} $$

Python 程式碼

Runtime: 7 ms, beats 89.58%. Memory: 19.32 MB, beats 46.35%.

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        MOD = 10**9 + 7
        dp = [0] * 26  # 以各個小寫字母結尾的子字串數量
        total = 0  # 目前的子字串數量
        for c in s:  # 依序讀取字母
            idx = ord(c) - ord('a')  # 轉成 dp 串列索引值
            prev = dp[idx]  # 檢查到前一個字母時的值
            dp[idx] = (total + 1) % MOD  # 可以接在之前的子字串後面，或是自己獨立成新的子字串
            total = (total + dp[idx] - prev) % MOD  # 更新 total
        return total

LeetCode 解題筆記：115. Distinct Subsequences

作者：王一哲
日期：2026年9月6日


LeetCode 題目連結：115. Distinct Subsequences

解題想法

困難題。題目給兩個字串 $s$、$t$，要計算 $s$ 的子字串之中有幾個等於 $t$，字串長度最長為 $1000$，要用動態規畫解題。

假設 $s$ 的長度為 $m$，$t$ 的長度為 $n$，開一個長度為 $(m+1) \times (n+1)$ 的二維陣列 $dp$，初始值先設為 0，$dp[i][0] = 1$，$dp[i][j]$ 代表檢查到 $s[i-1]$ 及 $t[j-1]$ 時，$s[0]$ 到 $s[i-1]$ 共有幾個子字串等於 $t[0:j]$。用兩層 for 迴圈更新 $dp$，外層跑 $i = 1$ 到 $i = m$，內層跑 $j = 1$ 到 $i = n$，如果 $s[i-1] == t[j-1]$，$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$；反之，$dp[i][j] = dp[i-1][j]$。由於更新時只需要用到前一次的狀態，可以用滾動陣列節省記憶體。由於答案很大，如果用 C 或 C++ 解題，$dp$ 的格式要用 unsigned long 才不會溢位。

Python 程式碼

二維陣列。Runtime: 419 ms, beats 49.82%. Memory: 75.56 MB, beats 56.33%.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # 動態規畫，dp[i][j] 代表 s[0:i] 範圍內可以組合出等於 t[0:j] 的子字串數量
        m, n = len(s),  len(t)
        dp = [[1] + [0]*n for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]

滾動陣列。Runtime: 213 ms, beats 85.86%. Memory: 19.53 MB, beats 82.38%.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # 動態規畫，prev[j] 代表 s 之中等於 t[0:j] 的子字串數量
        m, n = len(s),  len(t)
        prev = [1] + [0]*n  # 前一個狀態，prev[0] = 1，空字串
        for c in s:  # 由 s 依序取出字母
            curr = [1] + [0]*n # 現在的狀態 curr[0] = 1，空字串
            for j in range(1, n+1):  # 掃過 t 的每個字母
                if t[j-1] == c:  # 如果 t[j-1] 等於 c
                    curr[j] = prev[j-1] + prev[j]  # 長度為前一個狀態索引值 j-1, j 相加
                else:  # 反之，繼承 prev[j]
                    curr[j] = prev[j]
            prev, curr = curr, prev  # 交換資料
        return prev[-1]  # 答案在 prev 最後一項

LeetCode 解題筆記：3904. Smallest Stable Index II

作者：王一哲
日期：2026年9月5日


LeetCode 題目連結：3904. Smallest Stable Index II

解題想法

中等難度題，3903. Smallest Stable Index I 的加強版，題目的敘述及要求都一樣，但是測資範圍變大，改成 $1 \leq nums.length \leq 10^5, 0 \leq nums[i] \leq 10^9, 0 \leq k \leq 10^9$，基本上用前一篇 LeetCode 解題筆記：3903. Smallest Stable Index I 的寫法就能通過，只需要將 C 語言程式碼中的 $rmin$ 長度開成 $100001$ 就好。

Python 程式碼

Runtime: 127 ms, beats 91.82%. Memory: 33.26 MB, beats 23.64%.

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)  # 數量
        # 由右向左找每個位置的最小值
        rmin = [0] * n  # 每個索引值對應的右側最小值
        curr = float('inf')  # 目前的右側最小值
        for i in range(n-1, -1, -1):
            curr = min(curr, nums[i])
            rmin[i] = curr
        # 由左向右找 stable index
        lmax = 0  # 目前的左側最大值
        for i in range(n):
            lmax = max(lmax, nums[i])
            if lmax - rmin[i] <= k:
                return i
        return -1

LeetCode 解題筆記：3903. Smallest Stable Index I

作者：王一哲
日期：2026年9月4日


LeetCode 題目連結：3903. Smallest Stable Index I

解題想法

簡單題。題目給一個長度為 $n$ 的陣列 $nums$ 及整數 $k$，如果索引值 $i$ 符合 $max(nums[0..i]) - min(nums[0..n-1]) \leq k$，則 $i$ 是穩定的 (stable)，題目要找出最小的穩定索引值。先建立一個陣列 $rmin$，$rmin[i]$ 為 $i$ 到 $n-1$ 之中的最小值，再由左到右找 $0$ 到 $i$ 的最大值 $lmax$，如果 $lmax - rmin[i] \leq k$ 回傳 $i$，如果最後沒有找到符合條件的索引值則回傳 $-1$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 71.43%.

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)  # 數量
        # 由右向左找每個位置的最小值
        rmin = [0] * n  # 每個索引值對應的右側最小值
        curr = float('inf')  # 目前的右側最小值
        for i in range(n-1, -1, -1):
            curr = min(curr, nums[i])
            rmin[i] = curr
        # 由左向右找 stable index
        lmax = 0  # 目前的左側最大值
        for i in range(n):
            lmax = max(lmax, nums[i])
            if lmax - rmin[i] <= k:
                return i
        return -1

LeetCode 解題筆記：3876. Construct Uniform Parity Array II

作者：王一哲
日期：2026年9月3日


LeetCode 題目連結：3876. Construct Uniform Parity Array II

解題想法

中等難度的題目，3875. Construct Uniform Parity Array I 的加強版。題目給一個長度為 $n$ 的陣列 $nums1$，從 $nums1$ 依序出數字組成全為奇數或偶數的陣列 $nums2$，而要必須符合以下 2 項要求的其中一項：

1. $nums2[i] = nums1[i]$​​​​​​​
2. $nums2[i] = nums1[i] - nums1[j], j \neq i, nums1[i] - nums1[j] \geq 1$

我一開始的解法比較直接，先將 $nums1$ 之中的奇數、偶數分別存入串列 odd_nums、even_nums，如果所有的數字都是奇數或偶數回傳 True；反之，每個偶數要找到一個比自己小的奇數，如果找不到回傳 False，如果所有的數字都能找到一個對應的數字，回傳 True。但是這樣的解法速度有點慢，後來發現這個要求可以簡化成 $nums1$ 的最小值是奇數，或是所有的數字都是偶數。

Python 程式碼

Runtime: 135 ms, beats 13.41%. Memory: 36.14 MB, beats 6.71%.

from bisect import bisect_left

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        # 讀取測資，奇數、偶數分別存入串列
        n = len(nums1)
        even_nums = []
        odd_nums = []
        for num in nums1:
            if num % 2 == 0:
                even_nums.append(num)
            else:
                odd_nums.append(num)
        
        # 特例，全是奇數或偶數
        if len(even_nums) == n or len(odd_nums) == n:
            return True
        
        # 一般狀況，每個偶數要找到一個比自己小的奇數
        odd_nums.sort()
        m = len(odd_nums)
        for num in even_nums:
            idx = bisect_left(odd_nums, num)
            if idx == m: idx -= 1
            while idx >= 0 and  odd_nums[idx] > num:
                idx -= 1
            if idx == -1:
                return False
        return True

Runtime: 9 ms, beats 92.68%. Memory: 36.29 MB, beats 73.17%.

from bisect import bisect_left

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        # 如果最小的數字是奇數或是全為偶數，回傳 True
        return min(nums1) % 2 == 1 or all(num % 2 == 0 for num in nums1)

ZeroJudge 解題筆記：s216.三仙鬥法 (Competition)

作者：王一哲
日期：2026年9月2日


ZeroJudge 題目連結：s216.三仙鬥法 (Competition)

題目 pdf 檔連結：三仙鬥法 (Competition)

解題想法

題目是多筆測資。每筆測資第一列是一個整數 $R$，代表共有 $R$ 輪比賽；第二列有 3 個正整數 $a, b, c ~(1 \leq a, b, c \leq 10^{18})$，代表 3 個學院派出的選手靈氣值。每回合行動時，靈氣值最低的選手恢復 1 點靈氣值，較高的 2 個選手各減 1 點靈氣值；如果有多個選手的靈氣值最低，每個選手皆有相同的機率恢復 1 點靈氣值；不斷執行直到同時有 2 個選手的靈氣值歸零，此時靈氣值還沒有歸零的選手獲勝。題目要回傳每回合獲勝選手代表的學院，A、B、C 其中一個字母；如果三個學院獲勝機率相等，回傳 A B C。

由於這題的靈氣值很大，如果真的模擬比賽過程一定會超時，要找數學規律解題。由於 3 個選手其中 2 個的靈氣值減 1，另 1 個選手靈氣值加 1，所有選手的靈氣值都會加 1 或減 1。如果其中 2 個選手的靈氣值為來是偶數、另 1 個選手的靈氣值原為奇數，經過 1 個回合之後 2 個人的靈氣值同時變為奇數、另 1 個人的靈氣值變為偶數，因此只有這 2 個人的靈氣值同時歸零才會結束這輪比賽，一定是另 1 個選手獲勝。如果 3 個選手的靈氣值皆為偶數或奇數，經過多個回合之後 3 個人的靈氣值會相等，獲勝機率相同，答案是 A B C。因此這題不需要模擬比賽過程，只要用 $a, b, c$ 的奇偶性就可以直接輸出答案。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 11.4 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for token in line.split():
                yield int(token)
    
    tokens = get_tokens()
    result = []
    while True:
        try:
            R = next(tokens)
        except StopIteration:
            break
        
        for _ in range(R):
            a = next(tokens) % 2
            b = next(tokens) % 2
            c = next(tokens) % 2
            if a == b == c:
                result.append("A B C\n")
            elif b == c:
                result.append("A\n")
            elif a == c:
                result.append("B\n")
            elif a == b:
                result.append("C\n")
        
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3875. Construct Uniform Parity Array I

作者：王一哲
日期：2026年9月2日


LeetCode 題目連結：3875. Construct Uniform Parity Array I

解題想法

簡單題，直接回傳 True。如果 $nums1$ 的數字皆為奇數或偶數，直接複製 $nums1$ 到 $nums2$ 就能符合條件。如果 $nums1$ 的數字同時有奇數及偶數，一定能將 $nums2$ 全部湊成奇數，有兩種狀況：

1. $nums1[i]$ 是奇數，直接複製到 $nums2[i]$。
2. $nums1[i]$ 是偶數，一定能找到一個是奇數的 $nums1[j]$，將 $nums1[i] - nums1[j]$ 複製到 $nums2[i]$。

結論：題目的要求一定成立。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.23 MB, beats 47.47%.

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        return True

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 30.46 MB, beats 7.23%.

class Solution {
public:
    bool uniformArray(vector<int>& nums1) {
        return true;
    }
};

ZeroJudge 解題筆記：s215.紙膠帶 (Tape)

作者：王一哲
日期：2026年9月1日


ZeroJudge 題目連結：s215.紙膠帶 (Tape)

題目 pdf 檔連結：紙膠帶 (Tape)

解題想法

題目是多筆測資。每筆測資第一列是代表紙膠帶長度的整數 $N$，第二列有 26 個正整數代表每種動物（字母）數量上限，第三列是代表紙膠帶圖案的字串。題目規定一段連續的漂亮紙帶必須符合以下 2 個條件：

1. 紙帶上正好有 3 種動物
2. 紙帶上最多只能有 1 種動物數量超過上限

這題要找符合條件的連續子字串，很適合用滑動視窗 (sliding window) 解題。不過麻煩的地方在於計分方式有 2 種：

1. 紙帶上沒有動物超過數量上限，以 3 種動物的最大數量計分。
2. 紙帶上正好有 1 種物物超過數量上限，以超過上限的數量計分。

為了保證滑動視窗取對範圍，要分別對 2 種計分方式各跑一次滑動視窗，因為可能在一段較短的視窗內正好有 1 種物物超過數量上限，但是這個數量很大，分數反而可能很高。

Python 程式碼

使用時間約為 0.8 s，記憶體約為 10.9 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for token in line.split():
                yield token
        
    tokens = get_tokens()
    
    result = []
    while True:
        try:
            N = int(next(tokens))
            limits = [0] * 26
            for i in range(26):
                limits[i] = int(next(tokens))
            s = next(tokens)
        except StopIteration:
            break
        
        def get_score(max_exceed):
            # 自訂函式，用滑動視窗取連續子字串分數，代入可以有幾個字母超標
            left = 0  # 視窗左端點
            imax = 0  # 最高分數
            curr = set()  # 視窗中的字母索引值
            exceed = set()  # 超標的字母
            cnt = [0] * 26  # 視窗中的字母計數器
            for right in range(N):  # 右端點 0 ~ N-1
                ri_idx = ord(s[right]) - ord('a')  # 右端點字母索引值
                curr.add(ri_idx)  # ri_idx 加入 curr
                cnt[ri_idx] += 1  # ri_idx 數量加 1
                # 如果 ri_idx 超標，ri_idx 加入 exceed
                if cnt[ri_idx] == limits[ri_idx] + 1: exceed.add(ri_idx)
                # 左端點向右滑，直到視窗內字母種類等於 3 且超標數量等於 max_exceed
                while left < right and (len(curr) > 3 or len(exceed) > max_exceed):
                    le_idx = ord(s[left]) - ord('a')  # 左端點字母索引值
                    left += 1
                    cnt[le_idx] -= 1
                    # 如果 le_idx 降回數量上限，exceed 移除 le_idx
                    if cnt[le_idx] == limits[le_idx]: exceed.remove(le_idx)
                    # 如果 le_idx 降回數量歸零，curr 移除 le_idx
                    if cnt[le_idx] == 0: curr.remove(le_idx)
                
                # 依照 max_exceed 計分
                score = 0
                if len(curr) == 3:  # 有 3 種字母才有分數
                    if max_exceed == 1 and len(exceed) == 1:  # 只有一種超標，這個字母數量是分數
                        score = cnt[list(exceed)[0]]
                    elif max_exceed == 0 and len(exceed) == 0:  # 沒有字母超標，curr 之中 3 個字母數量最大值是分數
                        score = max(cnt[idx] for idx in curr)
                # 更新最高分數
                imax = max(imax, score)
            return imax
        # 用兩次滑動視窗找最高分
        ans = max(get_score(0), get_score(1))
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3568. Minimum Moves to Clean the Classroom

作者：王一哲
日期：2026年9月1日


LeetCode 題目連結：3568. Minimum Moves to Clean the Classroom

解題想法

中等難度題。題目給一個長度為 $m$ 的陣列 $classroom$，其中包含 $m$ 個長度為 $n$ 的字串，字串中只包含以下的字元：

• S 代表這格是學生的初位置
• L 代表這格有垃圾
• R 代表可以恢復能量的格子
• X 代表這格有障礙物，學生不能走到這格。
• . 代表空格

另外給一個整數 $energy$ 代表學生一開始的能量。假設學生每走一格消耗 1 點能量，如果能量歸零時不是位在 R 的格子上，學生無法再移動。如果學生走到 L 的格子上，可以撿起垃圾。如果學生走到 R 的格子上，會將能量補到起始值 $energy$。題目要問學生撿起所有垃圾時需要移動的最少步數，如果無法撿起所有的垃圾則回傳 $-1$。

這題的下方有提示，要用 BFS 解題，待走訪佇列放入的資料為 (x 座標, y 座標, 已撿起的垃圾狀態 mask, 目前的能量 e, 已走的步數 step)，並用一個三維陣列 bestEnergy 代表走到座標 (x, y) 時、狀態為 mask 的最高能量，並用 bestEnergy 剪枝。由於這題的垃圾數量上限為 10 個，可以先將每個位置的垃圾編號，用二進位制記錄這個編號的垃圾是否已被撿起來。詳細的 BFS 過程請參考程式碼中的註解。

Python 程式碼

Runtime: 1511 ms, beats 91.23%. Memory: 24.54 MB, beats 94.74%.

class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int:
        m, n = len(classroom), len(classroom[0])  # 教室尺寸 m*n
        # 1. 先找到起點 S 的位置、垃圾 L 的位置
        xi, yi = 0, 0  # S 的位置
        litter_pos = dict()  # 特定位置垃圾對應的編號
        litter_idx = 0   # 垃圾的編號
        for i in range(m):
            for j in range(n):
                ch = classroom[i][j]
                if ch == 'S':
                    xi, yi = i, j
                elif ch == 'L':
                    litter_pos[i, j] = litter_idx
                    litter_idx += 1
        
        total_litters = litter_idx  # 垃圾數量
        fullMask = (1 << total_litters) - 1  # 拿到所有垃圾的狀態
        
        # 特例，如果沒有垃圾，回傳 0
        if total_litters == 0: return 0
        
        # 2. BFS，待走訪佇列放入 (x 座標, y 座標, 狀態, 能量, 步數)
        que = deque([(xi, yi, 0, energy, 0)])
        # bestEnergy[x][y][mask] 代表走到 x, y, mask 狀態時最高的能量，預設為 -1
        bestEnergy = [[[-1] * (1 << total_litters) for _ in range(n)] for _ in range(m)]
        bestEnergy[xi][yi][0] = energy  # 起始狀態能量全滿
        # BFS
        while que:
            x, y, mask, e, step = que.popleft()
            # 如果 能量 e 為 0 且不在 R 上面，無法再移動
            if e == 0 and classroom[x][y] != 'R':
                continue
            # 四方位檢查
            for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nx, ny = x + dx, y + dy
                # 如果沒有出界也沒有遇到障礙物 X
                if 0 <= nx < m and 0 <= ny < n and classroom[nx][ny] != 'X':
                    ne = e - 1  # 能量減 1
                    if ne < 0: continue  # 能量不足
                    nxt_mask = mask  # 新的狀態
                    if classroom[nx][ny] == 'L':  # 撿垃圾
                        nxt_mask |= (1 << litter_pos[nx, ny])  # 更新狀態
                    elif classroom[nx][ny] == 'R':  # 能量全滿
                        ne = energy
                    
                    # 如果 nxt_mask == fullMask，找到答案，回傳 step + 1
                    if nxt_mask == fullMask: return step + 1
                    
                    # 如果 ne 大於之前走到 [nx][ny][mask] 的能量，才將下一步加入 que
                    if ne > bestEnergy[nx][ny][nxt_mask]:
                        bestEnergy[nx][ny][nxt_mask] = ne
                        que.append((nx, ny, nxt_mask, ne, step + 1))
        # 如果走完 BFS 還沒有找到 fullMask，無法達成目標，回傳 -1
        return -1