LeetCode 解題筆記：3635. Earliest Finish Time for Land and Water Rides II

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


LeetCode 題目連結：3635. Earliest Finish Time for Land and Water Rides II

解題想法

3633. Earliest Finish Time for Land and Water Rides I 的加強版，由於測資數量大很多，不能用簡單版的寫法，速度太慢。

Python 程式碼

Runtime: 778 ms, beats 7.27%. Memory: 39.98 MB, beats 12.73%.

from bisect import bisect_right

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        n, m = len(landStartTime), len(waterStartTime)
        # 合併開始、經過時刻，組成 (開始時刻, 經過時間) 
        land = list(zip(landStartTime, landDuration))
        water = list(zip(waterStartTime, waterDuration))
        land.sort()  # 依照開始時刻排序
        water.sort()
        
        # 取出排序後的開始時刻，用於二分搜尋法
        landStart = [s for s, _ in land]
        waterStart = [s for s, _ in water]

        # 前綴最短持續時間
        landDurationMin = [0] * n
        landDurationMin[0] = land[0][1]
        for i in range(1, n):
            landDurationMin[i] = min(landDurationMin[i-1], land[i][1])
        
        waterDurationMin = [0] * m
        waterDurationMin[0] = water[0][1]
        for i in range(1, m):
            waterDurationMin[i] = min(waterDurationMin[i-1], water[i][1])
        
        # 後綴最早結束時刻
        landFinishMin = [0] * n
        landFinishMin[-1] = land[-1][0] + land[-1][1]
        for i in range(n-2, -1, -1):
            landFinishMin[i] = min(landFinishMin[i+1], land[i][0] + land[i][1])
        
        waterFinishMin = [0] * m
        waterFinishMin[-1] = water[-1][0] + water[-1][1]
        for i in range(m-2, -1, -1):
            waterFinishMin[i] = min(waterFinishMin[i+1], water[i][0] + water[i][1])
        
        # 先去 land 再去 water 的最早結束時刻
        ans = float('inf')  # 答案
        for landS, landD in land:
            landF = landS + landD  # 結束時刻
            # 用二分搜尋法從 waterStart 之中找分界點 idx
            # idx 左側，已開放，可以直接玩
            # idx 右側，尚未開放，要等一段時間
            idx = bisect_right(waterStart, landF)
            currMin = float('inf')  # 目前的最短時間
            # 狀況1，可以直接玩已開放的設施，取 landF 加上 0 ~ idx-1 最短持續時間
            if idx > 0:
                currMin = min(currMin, landF + waterDurationMin[idx - 1])
            # 狀況2，等待還沒有開放的設施，取 idx ~ m-1 最早結束時刻
            if idx < m:
                currMin = min(currMin, waterFinishMin[idx])
            # 更新 ans
            ans = min(ans, currMin)
        
        # 先去 water 再去 land 的最早結束時刻
        for waterS, waterD in water:
            waterF = waterS + waterD  # 結束時刻
            # 用二分搜尋法從 landStart 之中找分界點 idx
            # idx 左側，已開放，可以直接玩
            # idx 右側，尚未開放，要等一段時間
            idx = bisect_right(landStart, waterF)
            currMin = float('inf')  # 目前的最短時間
            # 狀況1，可以直接玩已開放的設施，取 waterF 加上 0 ~ idx-1 最短持續時間
            if idx > 0:
                currMin = min(currMin, waterF + landDurationMin[idx - 1])
            # 狀況2，等待還沒有開放的設施，取 idx ~ n-1 最早結束時刻
            if idx < n:
                currMin = min(currMin, landFinishMin[idx])
            # 更新 ans
            ans = min(ans, currMin)
        # 回傳答案
        return ans

LeetCode 解題筆記：3633. Earliest Finish Time for Land and Water Rides I

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


LeetCode 題目連結：3633. Earliest Finish Time for Land and Water Rides I

解題想法

簡單難度的題目。我先將合併開始、經過時刻，組成 (結束時刻, 開始時刻) 串列。測試兩種可能性，找出先去 land 再去 water 的最早結束時刻 t1，以及先去 water 再去 land 的最早結束時刻 t2，回傳 t1, t2 較小者。可以過關但速度不夠快，還可以再改進。

Python 程式碼

Runtime: 155 ms, beats 52.33%. Memory: 19.29 MB, beats 86.05%.

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        # 合併開始、經過時刻，組成 (結束時刻, 開始時刻) 
        landFinishTime = [(s + d, s) for s, d, in zip(landStartTime, landDuration)]
        waterFinishTime = [(s + d, s) for s , d in zip(waterStartTime, waterDuration)]
        # 先去 land 再去 water 的最早結束時刻
        t1 = float('inf')
        for landF, _ in landFinishTime:
            for waterF, waterS in waterFinishTime:
                t = waterF  # 預設為 waterF
                if landF > waterS:  # 如果 landF 大於 waterS，需要多等一段時間
                    t += landF - waterS
                if t < t1: t1 = t
        # 先去 water 再去 land 的最早結束時刻
        t2 = float('inf')
        for waterF, _ in waterFinishTime:
            for landF, landS in landFinishTime:
                t = landF  # 預設為 landF
                if waterF > landS:  # 如果 waterF 大於 landS，需要多等一段時間
                    t += waterF - landS
                if t < t2: t2 = t
        return min(t1, t2)  # 取 (t1, t2) 較小者

不合併資料，用兩層 for 迴圈掃過串列，速度反而慢很多。Runtime: 355 ms, beats 5.23%. Memory: 19.38 MB, beats 56.98%.

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        n, m = len(landStartTime), len(waterStartTime)
        # 先去 land 再去 water 的最早結束時刻
        t1 = float('inf')
        for i in range(n):
            for j in range(m):
                t = waterStartTime[j] + waterDuration[j]  # 預設為 waterF
                if landStartTime[i] + landDuration[i] > waterStartTime[j]:  # 如果 landF 大於 waterS，需要多等一段時間
                    t += landStartTime[i] + landDuration[i] - waterStartTime[j]
                if t < t1: t1 = t
        # 先去 water 再去 land 的最早結束時刻
        t2 = float('inf')
        for i in range(m):
            for j in range(n):
                t = landStartTime[j] + landDuration[j]  # 預設為 landF
                if waterStartTime[i] + waterDuration[i] > landStartTime[j]:  # 如果 waterF 大於 landS，需要多等一段時間
                    t += waterStartTime[i] + waterDuration[i] - landStartTime[j]
                if t < t2: t2 = t
        return min(t1, t2)  # 取 (t1, t2) 較小者

LeetCode 解題筆記：2144. Minimum Cost of Buying Candies With Discount

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


LeetCode 題目連結：2144. Minimum Cost of Buying Candies With Discount

解題想法

簡單難度的題目。題目的意思是糖果買二送一，如果買兩顆糖果，其中較低的價格為 $p$，則可以免費拿一顆價格小於等於 $p$ 的糖果。題目會給一組糖果的價格，要計算得到所有糖果的最低成本。我的作法是將所有價格由高到低排序，再用一個 while 迴圈，從索引值 $i$ 開始往後處理到所有的糖果數量 $n$。假設總成本為 $total$，在 while 迴圈之中，每次先加上第 $i$ 個糖果的價格，然後將 $i+1$；如果此時 $i < n$，加上第 $i$ 個糖果的價格，然後將 $i+1$；如果此時 $i < n$，因為可以免費取得這顆糖果，直接將 $i+1$。跑完 while 迴圈之後直接回傳 $total$。

Python 程式碼

Runtime: 0 ms, beats 100%. Memory: 19.35 MB, beats 15.37%.

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(reverse=True)
        ans = 0
        n = len(cost)
        i = 0
        while i < n:
            ans += cost[i]
            i += 1
            if i < n:
                ans += cost[i]
                i += 1
            if i < n:
                i += 1
        return ans

LeetCode 解題筆記：2126. Destroying Asteroids

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


LeetCode 題目連結：2126. Destroying Asteroids

解題想法

中級難度的題目。我看到題目時最直接的想法，是先將小行星的質量由小到大排序，再依序讀取小行星的質量 a，如果行星質量 mass 大於等於 a，將 mass 加上 a；反之回傳 False。如果測試完所有的小行星質量都不會回傳 False，最後則回傳 True。

後來又想到，既然每次都要取出所有小行星質量之中的最小值，應該也可以用最小優先佇列解題。先將所有的小行星質量存入最小優先佇列 pq 之中，再用 while 迴圈取出 pq 之中的最小值與 mass 比較，但這樣寫多了掃過所有小行星質量花費的時間，反而比直接排序慢。

那如果稍微修改一下寫法，先掃過所有小行星質量一次，如果行星質量 mass 大於等於這個小行星質量 a，將 mass 加上 a；反之將 a 加入最小優先佇列 pq 之中，時間複雜度 $O(n)$。最後再用 while 迴圈取出 pq 之中的最小值與 mass 比較，pq 插入、刪除資料的時間複雜度為 $O(log n)$，由於 pq 之中的資料數量一定小於測資給的小行星數量，速度比前兩種寫法還快。

Python 程式碼

排序。Runtime: 71 ms, beats 73.70%. Memory: 34.01 MB, beats 30.13%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        for a in sorted(asteroids):
            if mass >= a:
                mass += a
            else:
                return False
        return True

heapq。Runtime: 269 ms, beats 5.37%. Memory: 30.22 MB, beats 93.86%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        heapq.heapify(asteroids)
        while asteroids:
            a = heapq.heappop(asteroids)
            if mass >= a:
                mass += a
            else:
                return False
        return True

只存部分資料到 heapq 之中。Runtime: 62 ms, beats 95.20%. Memory: 33.66 MB, beats 90.21%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        pq = []
        for a in asteroids:
            if mass >= a:
                mass += a
            else:
                heapq.heappush(pq, a)
        while pq:
            a = heapq.heappop(pq)
            if mass >= a:
                mass += a
            else:
                return False
        return True

ZeroJudge 解題筆記：d282. 11015 - 05-2 Rendezvous

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


ZeroJudge 題目連結：d282. 11015 - 05-2 Rendezvous

解題想法

這題考 Dijkstra's algorithm，先找出以節點 $k$ 為中繼點，從節點 $i$ 走到節點 $j$ 的成本，更新 $i$ 到 $j$ 的最低成本。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    ca = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        if n == 0 and m == 0: break
        ca += 1
        # 讀取名字
        names = []
        for _ in range(n):
            names.append(data[ptr])
            ptr += 1
        # 初始化距離矩陣
        dp = [[float('inf')]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0
        for _ in range(m):
            u = int(data[ptr])
            v = int(data[ptr+1])
            w = int(data[ptr+2])
            ptr += 3
            u -= 1
            v -= 1
            dp[u][v] = w
            dp[v][u] = w
        # Dijkstra's algorithm
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        # 找最低成本
        ans, imin = 0, float('inf')
        for i in range(n):
            cost = sum(dp[i][j] for j in range(n))
            if cost < imin:
                imin = cost
                ans = i
        result.append(f"Case #{ca:d} : {names[ans]}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d281. 10499 - The Land of Justice

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


ZeroJudge 題目連結：d281. 10499 - The Land of Justice

解題想法

不論切成幾等份，整個球外側的表面積皆為 $4 \pi r^2$。如果切成 $n$ 等份，$n \geq 2$ 才會有新的切面，每一等份會增加表面積 $\pi r^2$，因此答案為 $$ \frac{n \pi r^2}{4 \pi r^2} \times 100\% = 25n \% $$ 題目中的四捨五入根本用不到。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n < 0: break
        if n == 1:
            result.append("0%\n")
        else:
            result.append(f"{n*25:d}%\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d279. 00280 - Vertex

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


ZeroJudge 題目連結：d279. 00280 - Vertex

解題想法

這題有兩個奇怪的地方。 第一個是起點不算可以走到的點，例如範例測資的圖，節點1可以到節點2，節點2只能走到節點2，節點3可以走到節點1、2；輸出節點1無法走到的節點數量及編號才會是 2 1 3。 第二個是實際測資與中文的題目敘述不合，但其實是中文翻譯錯誤，多張圖之間沒有用一行單獨的 0 分隔，只有在全部的測資都結束後才會有一行單獨的 0。英文版題目在此，原題敘述是

If there are no more graphs, the next line of the file will contain only the integer ‘0’.

Python 程式碼

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

import sys

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    """ 讀取測資，建立圖的關係 """
    graph = [[] for _ in range(n+1)]
    for row in sys.stdin:
        if row.strip() == "0": break
        arr = list(map(int, row.split()))
        u = arr[0]
        for v in arr[1:-1]:
            graph[u].append(v)
    """ 讀取要檢查的起點 """
    data = list(map(int, sys.stdin.readline().split()))
    m = data[0]  # 起點數量，用不到
    for start in data[1:]:  # 依序測試每一個起點，用 BFS 找連通的節點
        que = [start]
        head = 0
        visited = [False]*(n+1)
        while head < len(que):
            u = que[head]
            head += 1
            for v in graph[u]:
                if visited[v]: continue
                visited[v] = True
                que.append(v)
        ### End of BFS ###
        ans = [i for i in range(1, n+1) if not visited[i]]  # 無法走到的節點
        result.append(f"{len(ans):d} " + " ".join(map(str, ans)) + "\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d796. 區域調查

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


ZeroJudge 題目連結：d796. 區域調查

解題想法

這題理論上可以用線段樹解題，但是程式碼非常長，我只寫了二元索引樹版本，0.3 s 過關，Python 會超時。

Python 程式碼

測資 #0 50%，4.7s，90.3 MB。測資 #1 開始超時。如果把二維串列攤平成一維串列，應該還可以再快一點。

class BIT2D:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.arr = [[0]*(m+1) for _ in range(n+1)]
        self.tree = [[0]*(m+1) for _ in range(n+1)]

    def _lowbit(self, x):
        return x & (-x)
    
    def _update(self, x, y, delta):
        i = x
        while i <= self.n:
            j = y
            while j <= self.m:
                self.tree[i][j] += delta
                j += self._lowbit(j)
            i += self._lowbit(i)
    
    def _query(self, x, y):
        total = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                total += self.tree[i][j]
                j -= self._lowbit(j)
            i -= self._lowbit(i)
        return total

    def update_val(self, x, y, val):
        delta = val - self.arr[x][y]
        self._update(x, y, delta)
        self.arr[x][y] = val

    def query_range(self, x1, y1, x2, y2):
        if x1 > x2: x1, x2 = x2, x1
        if y1 > y2: y1, y2 = y2, y1
        return self._query(x2, y2) - self._query(x1 - 1, y2) - self._query(x2, y1 - 1) + self._query(x1 - 1, y1 - 1)

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        Q = int(data[ptr+1])
        ptr += 2
        bit = BIT2D(N, N)
        for i in range(1, N+1):
            for j in range(1, N+1):
                v = int(data[ptr])
                ptr += 1
                bit.update_val(i, j, v)
        for _ in range(Q):
            op = int(data[ptr])
            ptr += 1
            if op == 1:
                x1 = int(data[ptr])
                y1 = int(data[ptr+1])
                x2 = int(data[ptr+2])
                y2 = int(data[ptr+3])
                ptr += 4
                ans = bit.query_range(x1, y1, x2, y2)
                result.append(f"{ans:d}\n")
            else:
                x = int(data[ptr])
                y = int(data[ptr+1])
                v = int(data[ptr+2])
                ptr += 3
                bit.update_val(x, y, v)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d794. 世界排名

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


ZeroJudge 題目連結：d794. 世界排名

解題想法

d788. 排名順序 的加強版，分數 $M$ 改成 $1 \leq M \leq 2^{64} - 1$。 由於分數差異極大，而且不是每個分數都有人，還要再加上離散化，用分數由小到大的順序當成新的編號，用編號存入線段樹或二元索引樹之中解題。這題理論上可以用線段樹解題，但是 Python 的速度太慢，即使程式碼邏輯正確仍會超時，改用二元索引樹才過關。

Python 程式碼

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

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)

    def _lowbit(self, x):
        return x & (-x)
    
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += self._lowbit(i)

    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= self._lowbit(i)
        return total

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        ptr += 1
        scores = list(map(int, data[ptr:ptr+N]))  # 讀取 N 個成績
        ptr += N
        sorted_unique = sorted(set(scores))  # 去重並排序
        rank_map = {val: rank for rank, val in enumerate(sorted_unique, start=1)}
        bit = FenwickTree(N)
        for i in range(1, N+1):
            rank = rank_map[scores[i-1]]  # 分數轉成順序
            bit.update(rank, 1)  # rank 的人數加 1
            result.append(f"{i - bit.query(rank-1):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d788. 排名順序

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


ZeroJudge 題目連結：d788. 排名順序

解題想法

這題理論上可以用線段樹解題，但是 Python 的速度太慢，即使程式碼邏輯正確仍會超時，改用二元索引樹才過關。用分數當作 tree 的索引值，tree[i] 的值代表這個分數的人數。假設每次加入討論的人分數為 x，先執行 bit.update(x)，再計算 bit.query(x-1)，也就是分數比自己低的人數，則自己的名次 = 總人數 - bit.query(x-1)。

Python 程式碼

線段樹，超時。

# --- 自訂線段樹類別，單點修改 ---
class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.data = [0]*self.n  
        self.tree = [0]*(4*self.n)  # 長度開 4 倍確保不會出界
        # 由於本題一開始 self.data, self.tree 皆為 0，省略 _build

    def _update(self, node, start, end, target, val):
        if start == end:
            self.tree[node] = val
            self.data[target] = val
            return
        mid = (end - start) // 2 + start
        if target <= mid:
            self._update(2*node + 1, start, mid, target, val)
        else:
            self._update(2*node + 2, mid + 1, end, target, val)
        self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]

    def _query(self, node, start, end, left, right):
        if end < left or start > right:
            return 0
        if left <= start and right >= end:
            return self.tree[node]
        mid = (end - start) // 2 + start
        lsum = self._query(2*node + 1, start, mid, left, right)
        rsum = self._query(2*node + 2, mid + 1, end, left, right)
        return lsum + rsum

    # --- 外部呼叫函式 ---
    def update(self, target, val):
        self._update(0, 0, self.n - 1, target, val)

    def query(self, left, right):
        return self._query(0, 0, self.n - 1, left, right)

def solve():
    import sys
    
    maxn = 100001
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        st = SegmentTree(maxn)  # 分數 0 ~ 100000 是否有人
        for i in range(1, n+1):
            m = int(data[ptr])
            ptr += 1
            st.update(m, 1)
            # 分數 m 的名次 = 總人數 - 分數 0 到 m-1 的人數
            result.append(f"{i - st.query(0, m-1):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()